2013腾讯编程马拉松预赛第5场（3月25）（HDU 4525 HDU4526 HDU4527 HDU4528 HDU4529）

2013腾讯编程马拉松初赛第5场（3月25）（HDU 4525 HDU4526 HDU4527 HDU4528 HDU4529）

    这次比赛题有点难。。我在谷大哥的帮助下把第一题A了。。斌哥在自己的努力下把第二题A了。。于是我们拿到了。。Rank 58 。。。。。。有点夸张啊。。。我最后看了看。。一共才180个人A出来题了。。。难道其他120个名额要分给那些疯狂刷wa的人？？不叨叨了看题。。。

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4525

题解：

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<iostream>#include<map>#include<string>#include<queue>#include<stack>#include<vector>#include<set>#include<list>using namespace std;typedef __int64 lld;const int MAX=10;const int INF=1000000000;const double EPS=1.0e-8;const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};int dblcmp(double x){    if(fabs(x)<EPS)return 0;    return x<0?-1:1;}int a[MAX];lld dp[2][11][1<<8][1<<8];char s[MAX];bool ok1[1<<8][1<<8];bool ok2[1<<8][1<<8];bool judge(int a,int b,int d){    int i;    int x,y;    for(i=0;i+d-1<8;i++)    {        x=1<<i;        y=1<<i<<d;        if((x&a)&&(y&b))return false;        if((x&b)&&(y&a))return false;    }    return true;}int cnt[1<<8];int count(int n){    int ret=0;    while(n)    {        ret+=n&1;        n>>=1;    }    return ret;}int main(){        int n=6;    int i,j;    int k;    int T;    int CS=1;    for(i=0;i<(1<<8);i++)    {        for(j=0;j<(1<<8);j++)        {            ok1[i][j]=judge(i,j,1);            ok2[i][j]=judge(i,j,2);        }    }    for(i=0;i<(1<<8);i++)    {        cnt[i]=count(i);    //    printf("cnt[%d]=%d\n",i,cnt[i]);    }    //printf("%d\n",1<<8);    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        for(i=0;i<8;i++)        {            scanf("%s",s);            a[i]=0;            for(j=0;j<8;j++)            {                a[i]*=2;                if(s[j]=='*')a[i]++;            }        //    printf("a[%d]=%d\n",i,a[i]);        }            memset(dp,0,sizeof(dp));        int xx=0;        for(i=0;i<(1<<8);i++)        {            if(i&a[0])continue;            if(cnt[i]>n)continue;            dp[0][cnt[i]][0][i]++;            xx++;            //printf("i=%d\n",i);        }    //    printf("xx=%d\n",xx);        int tag=0;        for(i=1;i<8;i++)        {            tag=i&1;            for(xx=0;xx<=n;xx++)            {                for(j=0;j<(1<<8);j++)                {                    for(k=0;k<(1<<8);k++)                    {                        dp[tag][xx][j][k]=0;                    }                }            }            for(j=0;j<(1<<8);j++)            {                if(i-2>=0&&(j&a[i-2]))continue;                    for(k=0;k<(1<<8);k++)                {                    if(k&a[i-1])continue;                        if(cnt[j]+cnt[k]>n)continue;                    if(!ok2[j][k])continue;                    int tt;                                            for(tt=cnt[j]+cnt[k];tt<=n;tt++)                    {                        if(dp[1-tag][tt][j][k]==0)continue;                            for(int z=0;z<(1<<8);z++)                        {                            if(cnt[z]+tt>n)continue;                            if(z&a[i])continue;                            if(!ok2[z][k]||!ok1[z][j])continue;                            dp[tag][tt+cnt[z]][k][z]+=dp[1-tag][tt][j][k];                        }                    }                }            }            }            lld ans=0;        for(i=0;i<(1<<8);i++)        {            for(j=0;j<(1<<8);j++)            {                //if(dp[tag][n][i][j]>0)printf("%d %d\n",i,j);                ans+=dp[tag][n][i][j];            }        }        printf("%I64d\n",ans);    }    return 0;}/*21*...........*..........*.....*....*...........*..*.........*....        21................................................................    21*******.*********************************************************/

5楼dyx40451431分钟前

第3,4题题解这里有http://blog.csdn.net/dyx404514/article/details/8720661

Re: liuqiyao_0130分钟前

回复dyx404514n多谢大牛！

4楼xiajun070612259小时前

昨天的比赛一道都没做出来，欲哭无泪啊！

3楼qingzhu_1993612昨天 19:46

好

Re: icelolipop昨天 12:08

回复icelolipopn我也是啊。。。我们这些小菜鸟，呀加油啊。。。

1楼icelolipop昨天 11:26

这场 看了一下题 就吃饭了啊。。。 楼主是大牛，支持！