[关闭]
@ysner 2018-07-30T21:10:01.000000Z 字数 1713 阅读 1955

[ZJOI2009]染色游戏

博弈论


题面

一个的长方形上,每个格子上有一硬币。每次需选一联通块并全部翻面,前提是其右下角硬币必须初始为反面。双方轮流行动,问先手是否有必胜策略。

解析

这是一个二维翻硬币问题。

先从一维说起。
一维翻硬币问题有个结论:局面的SG值等于局面中所有反面朝上的硬币单独存在时的SG值的异或和

于是试着算一下:(其实我就是想试试怎么算值)
表示第个硬币单独反面向上的情况。
据(表示取括号内不包含的 最小非负整数


,因操作后状态可转移到状态;

,因操作后状态可转移到状态和状态

;

,因操作后状态可转移到状态、状态和状态这个状态可由状态异或状态产生),

;

,因操作后状态可转移到状态、状态和状态

;

同理,
发现规律,(相当于只保留最高位)。

同理,可以试着算二维状态的值,方法与上类似,懒得打过程了。(矩阵转动后值不变

于是得到规律:
时,
除此之外,

随便用存下各位是否为就好了。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define max(a,b) ((a)>(b)?(a):(b))
  11. #define min(a,b) ((a)<(b)?(a):(b))
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=205,mod=2017;
  16. int n,m,mp[2000],ans;
  17. bool vis[N];
  18. il ll gi()
  19. {
  20. re ll x=0,t=1;
  21. re char ch=getchar();
  22. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il int SG(re int x,re int y)
  28. {
  29. if(x==1||y==1) return mp[(x+y-1)&(-x-y+1)];
  30. else return x+y-2;
  31. }
  32. int main()
  33. {
  34. ios::sync_with_stdio(false);
  35. re int T;cin>>T;
  36. fp(i,1,10) mp[1<<i]=i;
  37. while(T--)
  38. {
  39. memset(vis,0,sizeof(vis));
  40. cin>>n>>m;
  41. fp(i,1,n) fp(j,1,m)
  42. {
  43. re char c;cin>>c;
  44. if(c=='T') vis[SG(i,j)]^=1;
  45. }
  46. re int tag=0;
  47. fq(i,n+m-1,0) if(vis[i]) {tag=1;break;}
  48. puts(tag?"-_-":"=_=");
  49. }
  50. return 0;
  51. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注