题目链接：https://uoj.ac/problem/51
做法
这道题目主要涉及到了一个转化的问题。
SG 函数一般是使用在了没得走的时候为必败态，但是如果题目是走到了某个状态就输了要怎么转化呢？
答案是，我们认为玩家绝顶聪明，那显然不会去走那些输了的状态，也就是状态树中只会去走那些不会立即输的状态。（对应在本题中就是走后一定要 $a^b\le n$）
那么显然，当一个点没的走的时候，其是不是就一定输了，因为其下一步必定要走到判定为输的局面，这样我们就转化为了 $SG$ 的常见模型：没得走的状态为必败态。
这道题目也是同理，经过这种转化后，就是一个非常裸的 SG 函数了。
可以直接按题解写的做：$O(\sqrt{n}\log{n})$ ，但是感觉也存在更加优秀的做法。
就是观察发现状态只有 $0,1,2$ 三种，而且 $2$ 不会相邻，观察不难发现，同一个 $b$ 至多一个 $2$ ，记录一下 $2$ 的位置以及同一个 $b$ 的 SG 函数的一些参数，应该是可以做到 $O(\text{预处理}+m\log{n})$ 的时间做出来这道题目的。
但是感觉上就非常难写，以及有很多细节，有兴趣的读者可以自行尝试，我就不尝试了。
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
56
57
58
59
60
| #include<cstdio>
#include<cstring>
#include<algorithm>
#define N 110000
#define M 40
using namespace std;
int n,m,a[M][N];
int b[M],top;
bool ksm(int x,int y){
int now=n;
while(y){
if(y&1){
if(now<x)return 0;
now/=x;
}
if(y!=1 && now/x<x)return 0;
x=x*x;y>>=1;
}
return 1;
}
int solve(int x,int y){
if(y==1 && x>b[2])return (n-x)&1;
else return a[y][x];
}
int findans(int x,int y){
int now=0;
while(now==x || now==y)now++;
return now;
}
int main(){
scanf("%d%d",&n,&m);
b[top=1]=n;
while(b[top]>1){
b[++top]=1;
while(ksm(b[top]+1,top))b[top]++;
}
top--;
for(int i=top;i>=1;i--){
for(int j=min(b[i],b[2]);j>=2;j--){
int x=-1,y=-1;
if(!(i==top || j>b[i+1]))x=a[i+1][j];
if(j!=b[i] && !(i==1 && j>b[2]))y=a[i][j+1];
a[i][j]=findans(x,y);
}
}
for(int i=1;i<=m;i++){
int a,b;scanf("%d%d",&a,&b);
if(solve(a,b))printf("Yes\n");
else printf("No\n");
}
return 0;
}
|
