脚本宝典收集整理的这篇文章主要介绍了2020 ICPC 澳门站 G - Game on Sequence 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题面看这里

题目大意

给你一个长度为 n 的数组 a，Grammy 和 Alice 用这个数组玩个小游（bo）戏（yi），游戏规则如下：

对于每局游戏，先选定一个位置 (k) 为起点，(rm Grammy) 先手，轮流操作，每次操作都可以从当前位置 (i) 跳到后面的某个位置 (j)，(j) 满足 (a_i)​​​ 和 (a_j)​​​ 在二进制下最多只有一位不同，谁的回合中不能操作了，谁就输了。

然后有 m 次操作，每次操作给定两个数 op 和 k，op 代表操作类型，有两种：第一种类型，直接在数组末尾新增一个数 k；第二种类型，询问以 k 为起点开一局游戏谁能赢。

题目分析

首先显然这是一道博弈论的题目，于是我们从先手必胜态和先手必败态的分析入手。（以下简称必胜态和必败态）

必胜态的定义：可以跳到一个必败态的即为必胜态。

必败态的定义：没有一个地方可以跳或者能跳的地方都是必胜态的即为必败态。

打表，嗯推，推着推着发现一个有趣的性质：一个数如果在数组里面多次出现，那么除了最后出现的那个位置之外的其他位置都是必胜态。

有了这个性质，对于任意一个数 x，我们就不必关心非最后的位置 j 以外的其他位置了，游戏开始位置为这些位置时直接输出 "Grammy" 即可。

对于某个数的最后一个位置 j，我们则需要判断一下这个究竟是必胜态还是必败态。

显然这个游戏没有平局，所以不是必胜态就是必败态，同时根据上面的定义，感性地觉着必胜态更好判一些，我们来思考怎么判断必胜态。

起始位置为终点时先手必定跳不动，所以最初的必败态是 k = n，初态在末尾，考虑逆着推。

想到一个正确性显然的算法：对于当前位置后面的每一个位置（逆着推的，后面的每一个位置的状态肯定都是确定好了的），判断其是否是必败态，如果是，再判断下能否跳过去，如果能跳过去，则当前的位置是必胜态，逆着推一直推到所求的位置 k 即可。

正确性显然，但复杂度不咋地，考虑到 a 数组很大，当起点 k 很小时，最坏时间复杂度 (O(n^3),~n=2e5)​​，必 T。

考虑优化，怎么优化捏，根据性质，易知只需判断每个数字出现的最后一个位置即可，因为我们要判的是后面某个位置是否为必败态，而除了每个数字的最后一个位置，其他位置都一定是必胜态，所以根本不用判，注意到数据范围 (0leq a_ileq255)​​​，因此每次游戏撑死也就判个 255 次，时间复杂度 (O(n*255^2))​​​，当然还可以进一步优化，但这题时间开了 4s，且就算出题人特意造数据卡掉这个算法，我们也可以通过加点离线和特判来黑掉出题人造的数据，所以直接嗯艹过去就行了。大力出奇迹

代码实现

结合代码来说明一下实现细节。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
int a[maxn];
int vis[300],flag[300],v[300];
int main(){
	int n,m,op,k;
	cin >> n >> m;
	for(int i=1;i<=n;i++) {
		cin >> a[i];
		vis[a[i]]=i;
	}
	while(m--){
		cin >> op >> k;
		if(op==1){
			a[++n]=k;
			vis[k]=n;
		}
		else {
			if(vis[a[k]]>k){
				cout << "Grammyn";
			}
			else {
				int cnt=0;
				for(int i=0;i<256;i++){
					flag[i]=0;
					if(vis[i]){
						v[cnt++]=vis[i];
					}
				}
				sort(v,v+cnt);
				for(int i=cnt-1;;i--){
					for(int j=i+1;j<cnt;j++){
						if(flag[a[v[j]]]==0){
							int d=a[v[i]]^a[v[j]];
							d&=d-1;
							if(d==0){
								flag[a[v[i]]]=1;
								break;
							}
						}
					}
					if(a[v[i]]==a[k]) break;
				}
				if(flag[a[k]]) cout << "Grammyn";
				else cout << "Alicen";
			}
		}
	}
}

vis[x] 用于储存数字 x 在数组 a 中的最后一个位置。

把真正要判的位置存在数组 v[] 中，排个序，然后 v[i] 就表示第 i 个真正要判的位置在原数组 a 中的下标；用 flag[i] 来标记 i 这个位置是必胜态还是必败态。

有个小技巧，判断能否跳过去可以 (O(1))​ 判，代码如下：

int d=a[v[i]]^a[v[j]];
d&=d-1;
if(d==0) ;  //能跳
else ;  //不能跳

解释一下就是，两个数如果二进制下只有一位不同，那它们的异或和肯定是二的幂次，判断一个数 (d)​​ 是否是二的幂次只需判断 (d~&~(d-1))​ 是否为 0 即可。（可以举个栗子试试）

脚本宝典总结

以上是脚本宝典为你收集整理的2020 ICPC 澳门站 G - Game on Sequence 题解全部内容，希望文章能够帮你解决2020 ICPC 澳门站 G - Game on Sequence 题解所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。