【題意】:兩個人在玩數字游戲,規則如下:有2~20這19個數,每個回合每個人輪流取走一個數k,k取走后k的所有倍數都不可以再取,并且任意兩個不可取的數的和也不可以取。給出當前的合法局面,問先手是否必勝,若必勝輸出最優操作。
【題解】:考慮到一共只有19個數字,可以用狀態壓縮。然后在博弈樹上記憶化搜索即可,找到第一個必勝局面就可以跳出了。
【代碼】:
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define MAX 524287
19 int n, x[20];
20 int dp[MAX+10];
21 vector<int> vec;
22
23 void getmask(int &tmp, int &forbid, int x) {
24 for(int i = x; i <= 20; i += x) {
25 if(tmp & (1<<(i-2))) {
26 tmp &= ~(1<<(i-2));
27 forbid |= (1<<(i-2));
28 }
29 }
30 for(int i = 2; i <= 20; i++) {
31 if(forbid & (1<<(i-2)))
32 for(int j = i + 1; j <= 20 - i; j++) {
33 if((forbid & (1<<(j-2))) && (tmp & (1<<(i+j-2)))) {
34 tmp &= ~(1<<(i+j-2)), forbid |= (1<<(i-2));
35 }
36 }
37 }
38 }
39
40 bool g(int mask, int forbid) {
41 if(dp[mask] != -1) return dp[mask];
42 for(int i = 2; i <= 20; i++) {
43 if(mask & (1<<(i-2))) {
44 int nmask = mask, nforbid = forbid;
45 getmask(nmask, nforbid, i);
46 if(!g(nmask, nforbid)) return dp[mask] = 1;
47 }
48 }
49 return dp[mask] = 0;
50 }
51
52 void init() {
53 memset(dp, -1, sizeof(dp));
54 dp[0] = 0;
55 }
56
57 int main() {
58 int T, Case = 1;
59 scanf("%d", &T);
60 init();
61 while(T--) {
62 vec.clear();
63 scanf("%d", &n);
64 int mask = 0;
65 for(int i = 0; i < n; i++) {
66 scanf("%d", &x[i]);
67 mask |= (1<<(x[i]-2));
68 }
69 int forbid = MAX & ~mask;
70 for(int i = 0; i < n; i++) {
71 int nmask = mask, nforbid = forbid;
72 getmask(nmask, nforbid, x[i]);
73 if(!g(nmask, nforbid)) vec.pb(x[i]);
74 }
75 printf("Scenario #%d:\n", Case++);
76 if(vec.size()) {
77 sort(vec.begin(), vec.end());
78 printf("The winning moves are:");
79 for(int i = 0; i < vec.size(); i++) printf(" %d", vec[i]);
80 printf(".\n\n");
81 } else printf("There is no winning move.\n\n");
82 }
83 return 0;
84 }