首页 > 代码库 > 【动态规划】Codeforces Round #406 (Div. 2) C.Berzerk
【动态规划】Codeforces Round #406 (Div. 2) C.Berzerk
有向图博弈问题。
能转移到一个必败态的就是必胜态。
能转移到的全是必胜态的就是必败态。
转移的时候可以用队列维护。
可以看这个 http://www.cnblogs.com/quintessence/p/6618640.html
#include<cstdio> #include<queue> using namespace std; struct Node{ int who,pos; }; queue<Node>q; int n,len[2],to[2][7010],f[2][7010],cant[2][7010]; int main(){ scanf("%d",&n); for(int i=0;i<2;++i){ scanf("%d",&len[i]); for(int j=1;j<=len[i];++j){ scanf("%d",&to[i][j]); } } f[0][0]=f[1][0]=2; q.push((Node){0,0}); q.push((Node){1,0}); while(!q.empty()){ Node U=q.front(); q.pop(); if(f[U.who][U.pos]==2){ for(int i=1;i<=len[U.who^1];++i){ if(f[U.who^1][(U.pos-to[U.who^1][i]+n)%n]==0){ f[U.who^1][(U.pos-to[U.who^1][i]+n)%n]=1; q.push((Node){U.who^1,(U.pos-to[U.who^1][i]+n)%n}); } } } else{ for(int i=1;i<=len[U.who^1];++i){ if(f[U.who^1][(U.pos-to[U.who^1][i]+n)%n]==0){ ++cant[U.who^1][(U.pos-to[U.who^1][i]+n)%n]; if(cant[U.who^1][(U.pos-to[U.who^1][i]+n)%n]==len[U.who^1]){ f[U.who^1][(U.pos-to[U.who^1][i]+n)%n]=2; q.push((Node){U.who^1,(U.pos-to[U.who^1][i]+n)%n}); } } } } } for(int i=0;i<2;++i){ for(int j=1;j<n;++j){ if(f[i][j]==0){ printf("Loop "); } else if(f[i][j]==1){ printf("Win "); } else{ printf("Lose "); } } puts(""); } return 0; }
【动态规划】Codeforces Round #406 (Div. 2) C.Berzerk
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。