题目链接：https://atcoder.jp/contests/arc151/tasks/arc151_c
1 /*
2 博弈
3 归纳法，先开始处理单个情况，0 1是相对的
4 0....1：必败
5 0....0：必胜 策略：在0边上放1
6 ......：n%2=1必胜 策略：先手在中间放1 其他的模仿后手对称放
7 0.....：必胜
8 组合情况：
9 由于0...1是必败，所以其实两人在这个区间里面操作都是一对对的，所以对结果胜负无影响
10 由于0...0是必胜，所以在这个区间内操作是使得胜负手交换的，所以对ans^1
11 两端的...0当且仅当.个数一样才是必败的所以对a ns^tn（一段的.个数）
12 文后附加sg打表验证
13 */
14 #include <bits/stdc++.h>
15 using namespace std;
16 #define IOS ios::sync_with_stdio(0);cout.tie(0);
17 #define int long long
18 typedef long long ll;
19 typedef pair<int,int> P;
20 const int N=1e6+7;
21 const int INF=0x3f3f3f3f;
22 const int mod=998244353;
23 int n,m;
24 int fl;
25 void solve()
26 {
27 cin>>n>>m;
28 if(!m){
29 cout<<(n%2?"Takahashi":"Aoki")<<endl;
30 return;
31 }
32 vector<P>v(m+1);
33 for(int i=1;i<=m;i++){
34 cin>>v[i].first>>v[i].second;
35 }
36 int an1=0;
37 an1^=(v[1].first-1);
38 an1^=(n-v.back().first);
39 for(int i=2;i<=m;i++){
40 if(v[i].second==v[i-1].second)an1^=1;
41 }
42 cout<<an1<<endl;
43 cout<<(an1?"Takahashi":"Aoki")<<endl;
44 }
45 signed main()
46 {
47 //IOS
48 int __=1;
49 //cin >> __;
50 while (__--)
51 solve();
52 }
53 /*
54 #include <bits/stdc++.h>
55 using namespace std;
56 #define IOS ios::sync_with_stdio(0);cout.tie(0);
57 #define int long long
58 typedef long long ll;
59 typedef pair<int,int> P;
60 const int N=1e6+7;
61 const int INF=0x3f3f3f3f;
62 const int mod=998244353;
63 map<string,int>sg;
64 int dfs(string s)
65 {
66 if(sg.count(s))return sg[s];
67 // cout<<s<<endl;
68 bitset<100>vis;
69 for(int i=0;i<s.size();i++){
70 if(s[i]=='1'||s[i]=='0')continue;
71 if((i==0||s[i-1]!='1')&&(i==s.size()-1||s[i+1]!='1')){
72 char c=s[i];
73 s[i]='1';
74 vis[dfs(s)]=1;
75 s[i]=c;
76 }
77 if((i==0||s[i-1]!='0')&&(i==s.size()-1||s[i+1]!='0')){
78 char c=s[i];
79 s[i]='0';
80 vis[dfs(s)]=1;
81 s[i]=c;
82 }
83 }
84 int mex=0;
85 while(vis[mex])mex++;
86 // cout<<s<<" "<<mex<<endl;
87 return sg[s]=mex;
88 }
89 void solve()
90 {
91 string s;
92 cin>>s;
93 cout<<dfs(s)<<endl;
94 }
95 signed main()
96 {
97 //IOS
98 int __=1;
99 cin >> __;
100 while (__--)
101 solve();
102 }
103 */
标签：151,AtCoder,typedef,01,const,int,long,必胜,define From： https://www.cnblogs.com/20km-shimakaze/p/16810116.html