我为什么不取标题啊
题意：G和A玩游戏，每次G先走，G能从i走到j，当且仅当i < j 且 Ai和Aj在二进制位上最多有一位不同，谁走到最后走不动就输了。
现在给你两种操作，1：在数列后加一个数字x，2：问从第x个数开始走，谁会赢。
数列长度 n < 2e5,操作次数m < 2e5，0 <= Ai <=255。
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
··
·
·
·
·
··
·
·
··
·
思路：
本题关键是注意到Ai <=255，所以二进制最多8位。所以从Ai最多能走到9种数(包括自己)。那么我们在数列末尾加入一个数，则从这个数开始，必定是必输态，然后通过拓扑排序，我们往前update。但是因为n很大，这个update会超时，我们需要优化。还是从Ai <=255入手，所以我们应该对于同一种数字进行讨论。不难发现，对于同一种数字，除了最右端的数，其他数都是必胜态。故update时，我们只需update每种数最右端的数即可。
代码：
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
61
| #include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=4e5+11;
ll pos[333],f[maxn],ar[maxn];
ll n,m;
void dfs(ll x,ll s){
f[pos[x]]=s;
for(ll i=0;i<=7;i++){
ll y=x^(1<<i);
if(pos[y]<pos[x]){
if(f[pos[y]]==1-s) continue;
if(s==0){
dfs(y,1-s);
}
else{
ll flag=1;
for(ll j=0;j<=7;j++){
ll k=y^(1<<j);
if(pos[k]>pos[y] && f[pos[k]]==0){
flag=0;break;
}
}
if(flag) dfs(y,1-s);
}
}
}
}
void solve(ll x){
dfs(x,0);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++){
ll x;cin>>x;ar[i]=x;
pos[x]=i;
solve(x);
}
ll tmp=n;
for(ll i=1;i<=m;i++){
ll op,x;cin>>op>>x;
if(op==1){
pos[x]=++tmp;
ar[tmp]=x;
solve(x);
}
else{
if(x==pos[ar[x]]){
if(f[x]) cout<<"Grammy"<<endl;
else cout<<"Alice"<<endl;
}
else cout<<"Grammy"<<endl;
}
}
return 0;
}
|