CF786A - Berzerk
生活随笔
收集整理的這篇文章主要介紹了
CF786A - Berzerk
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
1 /*
2 CF786A - Berzerk
3 http://codeforces.com/contest/786/problem/A
4 博弈論
5 直接搜出NP狀態圖。記得要記憶化剪枝。
6 *
7 */
8 #include <cstdio>
9 #include <cstring>
10 //#define tle
11 #ifdef tle
12 //#define test
13
14 using namespace std;
15 const int Nmax=7005;
16 int now;
17 int is[2][Nmax];
18 int n;
19 int s[2][Nmax];
20 int tmp[2][Nmax];
21 int k[2];
22 #ifdef test
23 void watch()
24 {
25 for(int i=0;i<=1;i++)
26 {
27 printf("s[%d]:\n",i);
28 for(int j=1;j<=n;j++)
29 printf("%d ",is[i][j]);
30 printf("\n");
31 }
32 }
33 #endif
34
35 void work()
36 {
37 for(int j=0;j<=1;j++)
38 for(int i=1;i<=k[j];i++)
39 {
40 int x=(n+1-s[j][i])%n;
41 while(x<=0)
42 x+=n;
43 is[j][x]=1;
44 }
45 #ifdef test
46 watch();
47 #endif
48
49 for(int t=1;t<=100000;t++)
50 {
51 for(int ii=0;ii<=1;ii++)
52 for(int jj=1;jj<=n;jj++)
53 tmp[ii][jj]=is[ii][jj];
54 for(int now=0;now<=1;now++)
55 for(int i=2;i<=n;i++)
56 {
57 if(is[now][i]!=-1)
58 continue;
59 int flag=0;
60 for(int j=1;j<=k[now];j++)
61 {
62 int x=(i+s[now][j])%n;
63 while(x<=0)
64 x+=n;
65 if(is[now^1][x]==0)
66 {
67 is[now][i]=1;
68 flag=1;
69 break;
70 }
71 if(is[now^1][x]==-1)
72 flag=1;//標記不是P態
73 }
74 if(!flag)
75 is[now][i]=0;
76 #ifdef test
77 printf("is[%d][%d]:\n",now,i);
78 watch();
79 #endif
80
81 }
82 int ff=0;
83 for(int ii=0;ii<=1;ii++)
84 {
85 if(ff)
86 break;
87 for(int jj=1;jj<=n;jj++)
88 if(tmp[ii][jj]!=is[ii][jj])
89 {
90 ff=1;
91 break;
92 }
93 }
94 if(!ff)
95 break;
96 }
97
98 }
99
100 void init()
101 {
102 for(int i=1;i<=n;i++)
103 is[0][i]=is[1][i]=-1;
104 is[0][1]=is[1][1]=1;
105 }
106 int main()
107 {
108 scanf("%d",&n);
109 for(int i=0;i<=1;i++)
110 {
111 scanf("%d",&k[i]);
112 for(int j=1;j<=k[i];j++)
113 scanf("%d",&s[i][j]);
114 }
115 init();
116 work();
117 for(int t=0;t<=1;t++)
118 {
119 for(int i=2;i<=n;i++)
120 {
121 if(i!=2)
122 printf(" ");
123 if(is[t][i]==-1)
124 printf("Loop");
125 else if(is[t][i]==0)
126 printf("Lose");
127 else
128 printf("Win");
129 }
130 printf("\n");
131 }
132 }
133 #endif
134
135 using namespace std;
136 const int Nmax=7005;
137 int now;
138 int is[2][Nmax];
139 int n;
140 int s[2][Nmax];
141 int tmp[2][Nmax];
142 int k[2];
143
144 void dfs(int now,int x,int sstatus)
145 {
146 if(is[now][x]!=-1)//如果已經有狀態了，返回
147 return;
148 is[now][x]=sstatus;
149 if(sstatus==0)//如果當前點為必敗態，則讓與其相接的點為必勝態
150 {
151 for(int i=1;i<=k[now^1];i++)
152 {
153 int next=(x-s[now^1][i])%n;
154 while(next<=0)
155 next+=n;
156 dfs(now^1,next,1);
157 }
158 }
159 if(sstatus==1)//如果當前點為必勝態，則讓與其相接的點的非必勝態邊個數-1
160 {
161 for(int i=1;i<=k[now^1];i++)
162 {
163 int next=(x-s[now^1][i])%n;
164 while(next<=0)
165 next+=n;
166 tmp[now^1][next]--;//利用tmp數組記錄當前相接的點的非必勝態個數來剪枝，如果相鄰點都是必勝態，則當前點為必敗態
167 if(!tmp[now^1][next])
168 dfs(now^1,next,0);
169 }
170 }
171 }
172
173 void init()
174 {
175 for(int i=1;i<=n;i++)
176 is[0][i]=is[1][i]=-1;
177 is[0][1]=is[1][1]=0;
178 }
179 int main()
180 {
181 scanf("%d",&n);
182 for(int i=0;i<=1;i++)
183 {
184 scanf("%d",&k[i]);
185 for(int j=1;j<=k[i];j++)
186 scanf("%d",&s[i][j]);
187 for(int j=1;j<=n;j++)
188 tmp[i][j]=k[i];
189 }
190 init();
191 for(int j=0;j<=1;j++)
192 for(int i=1;i<=k[j];i++)
193 {
194 int x=(n+1-s[j][i])%n;
195 while(x<=0)
196 x+=n;
197 dfs(j,x,1);
198 }
199 for(int t=0;t<=1;t++)
200 {
201 for(int i=2;i<=n;i++)
202 {
203 if(i!=2)
204 printf(" ");
205 if(is[t][i]==-1)
206 printf("Loop");
207 else if(is[t][i]==0)
208 printf("Lose");
209 else
210 printf("Win");
211 }
212 printf("\n");
213 }
214 return 0;
215 }
?
轉載于:https://www.cnblogs.com/BBBob/p/6612753.html
總結
以上是生活随笔為你收集整理的CF786A - Berzerk的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 《EXPLAINING AND HARN
- 下一篇： 找人程序