首页 > 代码库 > UVa10561 Treblecross

UVa10561 Treblecross

2024-08-31 23:40:04   218人阅读

博弈 sg函数

 

如果能一步取胜的话，直接扫一遍，找出所有能一步取胜的位置输出。

否则枚举放‘X’的位置，计算剩下空区间的SG函数的异或和，若为0，则该位置可以作为答案。

计算空区间时要刨去X旁边的两个空（放在这里必败） 例如.X.....X.这一区段的可用长度为3

SG函数的预处理还不太理解


↓那个pd()并没有用到

  1 /*by SilverN*/  2 #include<iostream>  3 #include<algorithm>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 using namespace std;  8 const int mxn=210;  9 char s[mxn]; 10 int n,f[mxn]; 11 inline bool pd(){ 12     for(int i=2;i<n;i++){ 13         if(s[i-1]==‘X‘ && s[i]==‘X‘ && s[i+1]==‘X‘)return 1; 14     } 15     return 0; 16 } 17 inline bool check(int pos){ 18     if(s[pos+1]==‘X‘){ 19         if(s[pos-1]==‘X‘ || s[pos+2]==‘X‘)return 1; 20     } 21     else if(s[pos-1]==‘X‘){ 22         if(pos>2 && s[pos-2]==‘X‘)return 1; 23     } 24     return 0; 25 } 26 inline bool ar(int p){ 27     for(int i=max(1,p-2);i<=p+2;i++)if(s[i]==‘X‘)return 1; 28     return 0; 29 } 30 bool calc(){ 31     int i,j,len=0; 32     int res=0; 33     for(i=1;i<=n;i++){ 34         if(ar(i)){ 35             res^=f[len]; len=0; 36         } 37         else len++; 38     } 39     res^=f[len]; 40     return res; 41 } 42 int ans[mxn],cnt=0; 43 void solve(){ 44     cnt=0; 45     int i,j; 46     for(i=1;i<=n;i++){ 47         if(s[i]!=‘.‘)continue; 48         if(check(i)){ 49             for(j=i;j<=n;j++) 50                 if(s[j]==‘.‘ && check(j)){ans[++cnt]=j;} 51             return; 52         } 53     } 54     if(calc()){ 55         for(i=1;i<=n;i++){ 56             if(!ar(i)){ 57                 s[i]=‘X‘; 58                 if(!calc()){ 59                     ans[++cnt]=i; 60                 } 61                 s[i]=‘.‘; 62             } 63         } 64     } 65     return; 66 } 67 int vis[mxn]; 68 void init(){//处理sg函数  69     int i,j,x; 70     f[1]=f[2]=1; 71     for(i=3;i<mxn;i++){ 72         memset(vis,0,sizeof vis); 73         for(j=1;j*2<=i+1;j++){ 74             x=f[i-j-2];//去掉边界两个空位  75             if(j>3)x^=f[j-3]; 76             vis[x]=1; 77         } 78         for(j=0;;j++){if(!vis[j]){f[i]=j;break;}} 79     } 80     return; 81 } 82 int main(){ 83     int T;scanf("%d",&T); 84     init(); 85     while(T--){ 86         memset(s,0,sizeof s); 87         scanf("%s",s+1); 88         n=strlen(s+1); 89         solve(); 90         if(cnt){ 91             printf("WINNING\n"); 92             for(int i=1;i<cnt;i++){ 93                 printf("%d ",ans[i]); 94             } 95             printf("%d\n",ans[cnt]); 96         } 97         else printf("LOSING\n\n"); 98     } 99     return 0;100 }

 

UVa10561 Treblecross


联系
我们