[关闭]
@Junlier 2018-08-21T17:20:59.000000Z 字数 1370 阅读 1962

题解 luogu外星千足虫(线性基+高斯消元)

数学方法——线性基

题目

luogu题目传送门

题解想法

  1. 首先需要知道这是个异或方程对吧
    然后既然看到位运算,又有这么多,就可以考虑线性基(做题技巧),那我们就丢进去
    接下来看一看线性基,哇,性质美妙
    它不就是Gauss消元里面想要的上三角矩阵吗
  2. 所以说:
    • 如果能拼成线性基,那么枚举到哪里完成了,就输出位置(first_ans)
    • 如果拼不成,那就解不出(毋庸置疑)
  3. 那真是美妙啊。。。
  4. 所以怎么消元呢?这可是个异或方程,我们要解出来啊
    枚举整个线性基的g[i]
    如果g[i][j]这一位上为1,是不是就有一个未知数!
    (注意这是个异或方程)
    我们的线性基在g[j][j]上是一定会有数的对吧
    那我们直接给g[i]异或一下g[j]不就消掉了!!!
    直到枚举玩整个g[i],剩下的y(输入的那个"等号右边"的)如果为0就是地球了,为1就是外星了(单数只脚。。。)

code

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #include<bitset>
  13. #define lst long long
  14. #define ldb long double
  15. #define N 2050
  16. using namespace std;
  17. const int Inf=1e9;
  18. int read()
  19. {
  20. int s=0,m=0;char ch=getchar();
  21. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  22. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  23. return m?-s:s;
  24. }
  25. int m,n,Done;
  26. bitset<N>f[N],g[N];
  27. void Insert(int now)//高斯消元
  28. {
  29. for(int j=1;j<=n;++j)
  30. {
  31. if(f[now][j])
  32. {
  33. if(!g[j][j]){g[j]=f[now],Done++;break;}
  34. f[now]^=g[j];
  35. }
  36. }
  37. }
  38. void Gauss()
  39. {
  40. for(int i=1;i<=n;++i)
  41. {
  42. for(int j=i+1;j<=n;++j)
  43. if(g[i][j])g[i]^=g[j];
  44. if(g[i][n+1])puts("?y7M#");
  45. else puts("Earth");
  46. }
  47. }
  48. int main()
  49. {
  50. n=read(),m=read();
  51. char x;int y;
  52. for(int i=1;i<=m;++i)
  53. {
  54. for(int j=1;j<=n;++j)
  55. cin>>x,y=x-'0',f[i][j]=y;
  56. cin>>x,y=x-'0',f[i][n+1]=y;
  57. }
  58. for(int i=1;i<=m;++i)
  59. {
  60. Insert(i);
  61. if(Done==n){printf("%d\n",i);break;}
  62. }
  63. if(Done!=n){puts("Cannot Determine");return 0;}
  64. Gauss();
  65. return 0;
  66. }

yeh!!!

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注