首页 > 代码库 > 暑假集训day11
暑假集训day11
时间回到昨天。
今天学了一个超丧的东西——博弈论
倒是挺有趣的。
Treblecross(UVA_10561)
这题细节很多,de了一天的bug
话说博弈论的代码不是都不超过50行的吗、、、、
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int sg[201],used[201],T,ans,hh[201],len;char c[201]; void init(int n){ memset(sg,0,sizeof(sg)); sg[1]=sg[2]=sg[3]=1; for(int i=4;i<=n;i++){ memset(used,0,sizeof(used)); for(int j=1;j<=(i+1)/2;j++){ int tmp=sg[i-j-2]; if(j>3)tmp^=sg[j-3]; used[tmp]=1; } for(int j=0;j<=n;j++)if(!used[j]){sg[i]=j;break;} } } int can(int n){ for(int i=n-2;i<=n+2;i++){ if(i<0||i>=len)continue; if(c[i]==‘X‘)return 0; } return 1; } void print(){ puts("WINNING");int t=0; for(int i=0;i<len;i++)if(hh[i]){if(t)printf(" ");printf("%d",i+1);t=1;} puts(""); } int main() { init(200);scanf("%d",&T); while(T--){ scanf("%s",c); ans=0;memset(hh,0,sizeof(hh)); len=strlen(c);bool win=0; for(int i=0;i<len-2;i++){ if(c[i]==‘X‘){ if(c[i+1]==‘X‘)hh[i+2]=1,win=1; if(c[i+2]==‘X‘)hh[i+1]=1,win=1; }if(c[i+1]==‘X‘&&c[i+2]==‘X‘)hh[i]=1,win=1; } if(win){print();continue;} for(int i=0;i<len;i++){ if(!can(i))continue; int tmp=0,last=-3; for(int j=0;j<len;j++) if(c[j]==‘X‘||j==i){ if(j-last-5>0)tmp^=sg[j-last-5]; last=j;//printf("i%d j%d t%d\n",i+1,j+1,tmp); } if(len-last>3)tmp^=sg[len-last-3];//printf("i%d t%d\n",i+1,tmp); if(!tmp)hh[i]=1,win=1; } if(win)print(); else puts("LOSING\n"); } return 0; }
ENimEN(UVA_11892)
这题就很水了,还有下题
#include<iostream> #include<cstdio> using namespace std; inline int read(){ int num=0,t=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=(num<<3)+(num<<1)+c-‘0‘;c=getchar();} return num*t; } int main() { int T=read(); while(T--){ int n=read(),a,sum=0; for(int i=1;i<=n;i++){ a=read();if(a==1)sum++; } if(sum==n&&sum%2==0)puts("piloop"); else puts("poopi"); } return 0; }
A Funny Game(poj_2484)
#include<cstdio> int main(){ while(1){ int n;scanf("%d",&n);if(!n)break; if(n<3)puts("Alice"); else puts("Bob"); } return 0; }
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。
暑假集训day11
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。