hdu 1404 Digital Deletions (博弈论，根据定义)
题意：一个数字串，每次可以选择一位减少任意大小到一个非负数，或者清除一个0以及该位右边的所有数字。问是否有必胜策略。。
思路：定义来搞。。所有能一步走到p点的都是n点，那么如果我们现在知道p点，就可以反过来推n点。。
看到一些人强行把变量名起成sg就说自己用了sg函数也是笑死我了呵呵呵呵
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月22日 星期五 19时11分16秒
4File Name :code/hdu/1404.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E6+7;
34int n;
35int sg[N];
36bool vis[N];
37char st[10];
38
39
40void solve( int x)
41{
42
43 int dig[10];
44 int cnt = 0;
45 ms(dig,0);
46 int xx = x;
47 while (x)
48 {
49 dig[++cnt] = x % 10;
50 x/=10;
51 }
52 x = xx;
53 // cout<<"cnt:"<<cnt<<endl;
54 // for ( int i = 1 ; i <= cnt ; i ++) cout<<"i:"<<i<<" dig[i]:"<<dig[i]<<endl;
55 int base = 1;
56 for ( int i = 1 ; i <= cnt ; i++)
57 {
58 for ( int j = dig[i] + 1 ; j <= 9 ; j++)
59 if (x+(j-dig[i])*base<N)sg[x+(j-dig[i])*base] = 1;
60 base *=10;
61 }
62
63 if (cnt<6)
64 {
65 base = 1;
66 for ( int i = cnt ; i < 6 ; i++)
67 {
68 x*=10;
69 for ( int j = 0 ; j < base ;j++)
70 sg[x+j] = 1;
71
72 base*=10;
73 }
74 }
75
76}
77void sg_init()
78{
79 ms(sg,0);
80 // sg[0] = 1;
81
82 for ( int i = 1 ; i < N ; i++)
83 if (!sg[i]) solve(i); //由必败点去更新必胜点 所以能一步走到p点的是n点，反过来说，p点往前走一步到达的点都是n点。
84
85 // for ( int i = 1 ; i <= 300 ; i++)
86 // cout<<"i:"<<i<<" sg[i]:"<<sg[i]<<endl;
87}
88int main()
89{
90#ifndef ONLINE_JUDGE
91 freopen("code/in.txt","r",stdin);
92#endif
93
94 sg_init();
95
96 while (~scanf("%s",st))
97 {
98 if (st[0]=='0')
99 {
100 puts("Yes");
101 continue;
102 }
103
104 int x = 0 ;
105 int len = strlen(st);
106 for ( int i = 0 ; i < len ; i++)
107 {
108 int val = st[i]-'0';
109 x = x*10 + val;
110 }
111 if (sg[x])
112 {
113 puts("Yes");
114 }
115 else
116 {
117 puts("No");
118 }
119 }
120
121
122
123#ifndef ONLINE_JUDGE
124 fclose(stdin);
125#endif
126 return 0;
127}