这场做完B就去写作业了...
题目当时瞅了一眼，感觉不算特别难。
题目链接。
题意
现在有 个格子，编号为 。对于每一个 ，格子 与格子 是相邻的。
最初，有 个方格上写有数字，第
个方格上写的数字是 ，每一个格子上面的数字只能是 或 。剩下的 个方格上没有数字。
现在，高桥和青木将轮流执行一下操作，高桥先执行。
选择一个上面没有数字的方格，在上面写下 或 ，需要保证这个方格与它相邻的方格，上面的数字不同。
如果一个人不能操作，游戏结束，那个不能操作的人就输了。
如果两个人都按最优方案进行操作，谁会赢？
。
。
。
。
。
题解
首先我们知道，这题是个博弈论（废话
我们会发现，假如有两段空白的区域，中间用若干个数字隔开，那么这两段在操作的时候是不会互相影响的。
并且两个人可执行的操作是完全相同的。
所以我们知道，这道题是一个公平博弈，而且使用SG函数大概率可以做出来。
不过这道题的SG函数比较复杂，因为需要多种情况进行讨论。
我们设 为一段长度为
的两端数字相等的空白区域的SG函数值。
设 为一段长度为
的两端数字不等的空白区域的SG函数值。
设 为一段长度为 的一端为格子边界（ 或 ）的空白区域的SG函数值。
设 为一段长度为
的两端都为格子边界的空白区域的SG函数值。
看起来很不好求，所以我们进行打表。
打出来的结果放在这里：
打表程序
会发现SG函数的特征还是比较明显的。
做到这里其实就可以直接使用 SG 函数解决了，时间复杂度是 的。
不过这个结论终究是打表看出来的，下面来证明一下：
证明
我们现在需要证明的是对于任何正整数 ，都有 。
是用数学归纳法。
首先对于 ，结论显然成立。
现在假设，对于一个 ，所有
都满足结论，现在证明对于 ，也满足结论。
对于 ：
显然，一共有两种情况：
- 分成两段长度
的两端相同的空白段，此时可达到的
值为 。
- 分成两段长度
的两端不同的空白段，此时可达到的
值为 。
所以 。
对于 ：
显然，一共有一种情况。
分成一段长度
的两端相同的空白段和一段长度
的两端不同的空白段。
可以达到的 值为 。
所以 。
对于 ：
显然，一共有两种情况。
分成一段长度
的两端相同的空白段和一段长度
的一端为边界的空白段，设含边界的一段长度为 。
则此时可以到达的 值为 ，并且可以知道：。
分成一段长度
的两端不同的空白段和一段长度
的一端为边界的空白段，设含边界的一段长度为 。
则此时可以到达的 为 ，并且可以知道，可以到达的所有 恰好为 的所有整数。
所以 。
对于 ：
显然，一共有一种情况。
分成两端长度
的一端为边界的空白段，假设其中一段的长度为 ，则另一段的长度为 。
当 为偶数时， 与 恰好有一个是偶数，一个是奇数。
此时
当 为奇数时， 与 奇偶性相同。
取 时，，到达的 值为 。
因为他们两个奇偶性相同，所以到达的 值不可能为奇数。
此时 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
using ll=long long;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
ll ans;
int m;
ll n;
ll get(int lst,int now,ll len)
{
if(len==0) return 0;
if(lst==-1||now==-1)
{
if(lst==-1&&now==-1) return len&1;
if(len==1) return 1;
return len;
}
return lst==now;
}
int main()
{
n=lread(),m=read();
ll lst=0;int type=-1;
for(int i=1;i<=m;i++)
{
ll now=lread();int ty=read();
ans^=get(type,ty,now-lst-1);
lst=now,type=ty;
}
ans^=get(type,-1,n-lst);
if(ans) printf("Takahashi\n");
else printf("Aoki\n");
return 0;
}
|
感谢观看！