注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SDOI2010[外星千足虫]  

2010-07-24 15:08:43|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

赤裸裸的高斯消元,但是是O(n^2*m)的,犹豫了一下,然后百度一下,发现要用位运算来压缩。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-24

DESCRIPTION:

山东2010年省选 外星千足虫

*/

#include <stdio.h>

 

typedef unsigned int bit;

const int MAXN=1000;

const int MAXM=2000;

const bit mod32=(1<<5)-1;

const bit div32=5;

int N,M;

bit _matrix[MAXM][((MAXN+1)>>5)+1];

bit* matrix[MAXM];

bit answer[((MAXN+1)>>5)+1];

int main()

{

    #define assign(i,j,value) (matrix[i][(j)>>div32]|=(value)<<((j)&mod32))

    #define get(i,j) ((matrix[i][(j)>>div32]>>((j)&mod32))&1)

    #define get_answer(j) ((answer[(j)>>div32]>>((j)&mod32))&1)

    #define swap(a,b) {bit* s=matrix[a];matrix[a]=matrix[b];matrix[b]=s;}

    scanf("%d%d",&N,&M);

    for (int i=0;i<M;i++)

    {

        matrix[i]=_matrix[i];

        getchar();

        for (int j=0;j<N;j++)

            assign(i,j,getchar()=='1');

        getchar();

        assign(i,N,getchar()=='1');

    }

    bool have_solution=false;

    for (int i=0,step=0;i<M;i++)

    {

        if (get(i,step))

        {

           swap(step,i);

           go:

           for (int j=step+1;j<M;j++)

               if (get(j,step))

                  for (int k=(step>>div32);k<=(N>>div32);k++)

                      matrix[j][k]^=matrix[step][k];

           step++;

           for (int j=step;j<=i;j++)

               if (get(j,step))

               {

                  swap(j,step);

                  goto go;

               }

           if (step==N)

           {

              printf("%d\n",i+1);

              for (;step--;)

              {

                  for (int k=step+1;k<N;k++)

                      answer[step>>div32]^=(get_answer(k)&get(step,k))<<(step&mod32);

                  answer[step>>div32]^=get(step,N)<<(step&mod32);

              }

              for (int j=0;j<N;j++)

                  printf("%s\n",get_answer(j)?"?y7M#":"Earth");

              have_solution=true;

              break;

           }

        }

    }

    if (!have_solution) printf("Cannot Determine\n");

}

 

  评论这张
 
阅读(526)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018