首页 > 代码库 > 2015 ccpc 南阳国赛

2015 ccpc 南阳国赛

A 2*2矩阵  问可不可以通过旋转 得到另外个

直接模拟

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>

using namespace std;

#define ll long long
#define inf 1000000007
#define MAXN 10000100

int x[5],z[5];

int main()
{
    int t;
    scanf("%d",&t);
    int ca=1;
    while(t--)
    {
        scanf("%d%d%d%d%d%d%d%d",&z[0],&z[1],&z[3],&z[2],&x[0],&x[1],&x[3],&x[2]);
        int ok=0;
        for(int i=0;i<=3;i++)
        {
            for(int j=0;j<=3;j++)
            {
                int cnt=0;

                for(int k=0;k<4;k++)
                {
                    if(z[(i+k)%4]==x[(j+k)%4])
                        cnt++;
                }
                if(cnt==4)
                    ok=1;
            }
        }
        if(ok==1)
            printf("Case #%d: POSSIBLE\n",ca++);
        else
            printf("Case #%d: IMPOSSIBLE\n",ca++);
    }
    return 0;
}
View Code

B给你n个数 求取其中几个  求乘积最大 

排序 然后 负数 取偶数个 正数都取  

技术分享
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

long long a[70];
int b[3];

int main()
{
    int t, n, i, j;
    scanf("%d", &t);
    while(t--){

        scanf("%d", &n);
        for (i = 0; i < n; i++){
            scanf("%lld", &a[i]);
        }
        sort(a, a + n);

        for (i = 0; i < 3; i++)b[i] = 0;
        for (i = 0; i < n; i++){
            if (a[i] < 0)b[0]++;
            else if (a[i] == 0)b[1]++;
            else b[2]++;
        }
        long long ans = 1;
        for (i = 0; i < b[2]; i++){
            ans *= a[n - i - 1];
        }
        for (i = 0; i < b[0] - 1; i+=2){
            ans *= (a[i] * a[i + 1]);
        }
        if (b[0] < 2 && b[2] == 0){
            ans = a[0];
        }
        if (ans < 0 && b[1] > 0)ans = 0;
        printf("%lld\n", ans);
    }

    return 0;
}
View Code

C n个数  小的可以和大的连起来  可以不相邻  连起来长度为k  

问有多少个

dp[i][j]  连到第i个长度为j  

dp[i][j] = sum(dp[k][j-1]);   w[k]>w[i]    1 <=k<i

离散化

树状数组 维护 j-1  层 (1~i-1)  求和即可

线段树好像tle     别乱用long long

G++能过

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>

using namespace std;

#define ll long long
#define inf 1000000007
#define MAXN 1010

ll dp[MAXN][MAXN];
int z[MAXN];
int w[MAXN];
struct nod
{
    int ind;
    int w;
}x[MAXN];
bool cmp(nod a,nod b)
{
    return a.w<b.w;
}
ll tree[MAXN];

int lowbit(ll t)
{
    return t&(-t);
}
void Insert(int n,int t,ll d)
{
    while(t<=n)
    {
        tree[t]=(tree[t]+d)%inf;
        t=t+lowbit(t);
    }
}
ll Ques(int t)
{
    ll ans=0;
    while(t>0)
    {
        ans=(ans+tree[t])%inf;
        t=t-lowbit(t);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    int ca=1;

    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&z[i]);
            x[i].w=z[i];
            x[i].ind=i;
        }
        sort(x+1,x+n+1,cmp);
        w[x[1].ind]=1;
        int cnt=2;
        for(int i=2;i<=n;i++)
        {
            if(x[i].w!=x[i-1].w)
                w[x[i].ind]=cnt++;
            else
                w[x[i].ind]=cnt;
        }
        memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;i++)
            dp[i][1]=1;

            for(int k=2;k<=m;k++)
            {
                for(int i=1;i<=n;i++)
                {
                    if(i>=2)
                        Insert(cnt-1,w[i-1],dp[i-1][k-1]);
                    ll ans=0;
                    if(w[i]==1)
                        ans=0;
                    else
                        ans=Ques(w[i]-1);
                     dp[i][k]=ans;
                    // printf("%d %d %lld\n",i,k,ans);
                }
                memset(tree,0,sizeof(tree));
            }
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans=(ans+dp[i][m])%inf;
        printf("Case #%d: %lld\n",ca++,ans);
    }
    return 0;
}
/*
3
-1 -1 -2
4
0 0 0 0
4
1 2 1 0

*/
View Code

G 给你一个9*9的矩阵  问 x能不能下一个  吃掉o的 

列举下的位子  然后每个o深搜 看旁边是否有 .  有点就是活的  没有就死了

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>

using namespace std;

#define ll long long
#define inf 1000000007
#define MAXN 1010

char z[12][12];
char x[12][12];
bool vis[12][12];
int s1[4]={1,0,-1,0};
int s2[4]={0,1,0,-1};
struct node
{
    int x,y;
}w[150];
int cnt;

void dfs(int a,int b)
{
    vis[a][b]=1;
    w[cnt].x=a;
    w[cnt].y=b;
    cnt++;

    for(int i=0;i<4;i++)
    {
        int c,d;
        c=a+s1[i];
        d=b+s2[i];
        if(c>=1&&c<=9&&d>=1&&d<=9&&x[c][d]==o&&vis[c][d]==0)
            dfs(c,d);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    int ca=1;
    while(t--)
    {
        for(int i=1;i<=9;i++)
            scanf("%s",z[i]+1);
        int ok=0;

        for(int i=1;i<=9;i++)
        {
            for(int j=1;j<=9;j++)
            {
                for(int k=1;k<=9;k++)
                {
                    for(int kk=1;kk<=9;kk++)
                        x[k][kk]=z[k][kk];
                }
                for(int k=0;k<=10;k++)
                    x[0][k]=x[10][k]=x[k][0]=x[k][10]=x;
                memset(vis,0,sizeof(vis));
                if(z[i][j]==.)
                {
                    x[i][j]=x;
                    for(int k=1;k<=9;k++)
                    {
                        for(int kk=1;kk<=9;kk++)
                        {
                            cnt=0;
                            if(x[k][kk]==o&&vis[k][kk]==0)
                            {
                                dfs(k,kk);
                                int cc=0;
                                for(int kkk=0;kkk<cnt;kkk++)
                                {
                                    for(int kkkk=0;kkkk<4;kkkk++)
                                    {
                                        int a,b;
                                        a=w[kkk].x+s1[kkkk];
                                        b=w[kkk].y+s2[kkkk];
                                        if(x[a][b]==.)
                                            cc=1;
                                    }
                                }
                                if(cc==0)
                                    ok=1;
                            }
                        }
                    }
                }
            }
        }
        if(ok==1)
            printf("Case #%d: Can kill in one move!!!\n",ca++);
        else
            printf("Case #%d: Can not kill in one move!!!\n",ca++);
    }
    return 0;
}
View Code

H队友过的

技术分享
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

char s[5][5];
int biao[5];
int biao1;
int di[8][2] = {{0, 1},{1, 1},{1, 0},{1, -1},{0, -1},{-1, -1},{-1, 0},{-1, 1}};

bool cmp(int i, int j){
if (s[i][j] != * && biao[s[i][j] - 0] == 0)return 1;
else return 0;
}

int main()
{
    int t, i, j, n, k;
    scanf("%d", &t);
    int ci = 1;
    while(t--){

        for(i = 0; i < 4; i++){
            scanf("%s", s[i]);
        }
        int cnt = 0;
        for (i = 0; i < 4; i++){
            for (j = 0; j < 4; j++)
                if (s[i][j] == *)cnt++;
        }

        int q = 0;
        while (1){
            q++;
            if (q >= 50)break;
            for (i = 0; i < 4; i++){
                for (j = 0; j < 4; j++){
                    if (s[i][j] == *){

                        ///////////////////////
                        for (k = 0; k <= 4; k++)biao[k] = 0;
                        biao1 = 0;

                        for (k = 0; k < 4; k++){
                            if (cmp(i, k))biao[s[i][k] - 0] = 1, biao1++;
                            if (cmp(k, j))biao[s[k][j] - 0] = 1, biao1++;
                        }
                        for (k = 0; k < 8; k++){
                            int tt = i + di[k][0], ii = j + di[k][1];
                            if (tt >= 0 && tt <= 3 && ii >= 0 && ii <= 3){
                            if ((tt==1 && di[k][0] == -1) || (tt == 2 && di[k][0] == 1) || (ii == 1 && di[k][1] == -1) || (ii == 2 && di[k][1] == 1))continue;
                            if (cmp(tt, ii))biao[s[tt][ii] - 0] = 1, biao1++;
                            }
                        }
                        
                        if (biao1 >= 3){
                            for (k = 1; k <= 4; k++){
                                if (biao[k] == 0)s[i][j] = 0 + k, cnt--;
                            }
                        }
                        ////////////////
                    }
                }
            }///////
            if (cnt <= 0)break;
        }

        printf("Case #%d:\n", ci++);

        if (q>= 100)printf("p = %d\n", q);
        for (i = 0; i < 4; i++){
        printf("%s\n",s[i]);
        }
    }

    return 0;
}
View Code

L

2*n-1

技术分享
#include <iostream>

using namespace std;

int main()
{
    int T,n;
    cin>>T;
    int ans=1;
    while(T--)
    {
        cin>>n;
        cout<<"Case #"<<ans++<<": "<<2*n-1<<endl;
    }
    return 0;
}
View Code

 

2015 ccpc 南阳国赛