Coding

闲言碎语：最近对引体向上着迷，虽然拉不了几个，身体上的健身还是太困难了，毕竟不是所有人都擅长运动。偶然间在网上冲浪看到一位82年的大叔把健身和编程结合起来了(B站，CF)，生活哪来那么多为什么，做点想做的就是了。决定，像健身一样coding，写点题解。今天听到一首歌很好听，推荐一下《有没有人曾告诉你》by陈楚生。 这次练的题目还是非常经典的，先看看题。 题目连接 题目大意：有$n$个目标排成一排，标记为$1$到$n$。射击选手可以射击一个目标$i$，然后获得$a_i$的积分，之后目标$i$损坏，无法再次被射击。这场游戏有两个选手R和S，R先射击，然后S射击，依次轮替，直到所有目标均被摧毁。获得最多累计积分的选手获胜。但是这样太简单了。所以，要求有$q$次询问，每次选取$l$到$r$区间内的目标进行比赛，问这个区间内S选手是否能够不输。 输入格式：第一行包含一个整数$t(1\le t \le 10^4)$，表示测试样例数。每个测试，第一行有两个整数$n,q(1\le n, q \le 2\cdot 10^5)$，表示总的目标数和询问次数。然后第二行是$n$个整数$a_1,a_2,\dots,a_n(1\le a_i\le 10^6)$表示每个目标的积分数。接下来$q$行，每行两个整数$l$和$r(1\le l \le r \le n)$表示每次询问的区间。保证$n$和$q$的分别在多组测试中和不超过$2\cdot 10^5$。 输出格式：对于每次询问，如果S选手不会输，就输出YES。反之输出NO。 这道题可以用哈希(hash)解决。 楔子：先手的人不会输，每次都取最大的值，后手的积分和不会大于先手的。如果每个积分大小的目标数量都是偶数，先手不管怎么取，后手只要取一样的就行了(首先有不输的策略，然后都是偶数又赢不了，两人均是选取最优的方案博弈，那就只能平局了)。如果存在奇数数量的积分，先手存在必胜的策略，只要每次取最大的，必然有次后手取不到一样的(取到不等号)。 问题就转化为在区间$l$到$r$之间是否有奇数数量的积分值，如果没有则S选手能够不输，否则就会输。 一个简单的事实。假设我们有两个随机变量$X,Y$，它们均有50%的概率是0，50%的概率是1。用数学表达式表示一下。 $$P(X=x)=0.5,x∈\{0,1\}$$$$P(Y=y)=0.5,y∈\{0,1\}$$令随机变量$Z=X\bigoplus Y$。那么$P(Z=0)=0.5\times 0.5+0.5\times 0.5=0.5$，也就是$X$和$Y$，同取$0$或者$1$的时候。同理求出$P(Z=1)=0.5$，和$X$和$Y$的分布相同。 hash是非常好用的东西，使用概率学打破常规。这里给每个不同的积分分配一个随机的64位无符号数。异或运算具有非常好的性质，比如两个相同的值异或起来就是0，我们通过前缀异或和可以很容易地求出某个区间内的异或值。那么有什么用呢？如果区间异或值为0，我们认为，这个区间内不存在奇数出现次数的值，错判概率是$2^{-64}$，也就是几乎等于正确。 首先，如果区间内每种数的出现次数均为偶数，给每个数分配了一个随机值之后仍然保持偶数，根据异或的性质，区间异或和100%为0。我们错判的概率情况是，区间内存在奇数次出现的值，但是随机分配后的随机数的异或和恰好是0。我们可以把所有奇数出现的值取出一个，运行交换律和结合律，得到全部的偶数出现次数的数异或上某些奇数出现次数的数的异或和。前者是0，而后者几乎不可能是0。因为，给每个不同的数分配的不同的64位随机数，一个随机数每个bit位上是0或1的概率均为50%，根据上面的那个简单的事实，这些数的异或和结果中每个bit位0或1的概率也均为50%，所以要想令后者为0造成误判，总共有64位，要求全零，概率就是$(0.5)^{64}=2^{-64}$。 Codeforces上的随机数也是要小心使用。如果这样写。 uint64_t generateRandom64() { auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count(); std::mt19937_64 generator(seed); std::uniform_int_distribution<uint64_t> distribution(0, UINT64_MAX); return distribution(generator); } 在CF平台上，每次生成的数都是一样的，因为每次获取的时间都是一样的。可能是代码优化，或者CF机子特别快的缘故。 #include <bits/stdc++.h> uint64_t generateRandom64(std::mt19937_64& generator) { std::uniform_int_distribution<uint64_t> distribution(0, UINT64_MAX); return distribution(generator); } void solve() { int n, q; std::cin >> n >> q; std::vector<uint64_t> a(n); std::map<int, uint64_t> mp; auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count(); std::mt19937_64 generator(seed); for (int i = 0; i < n; i++) { int x; std::cin >> x; if (!mp.count(x)) { mp[x] = generateRandom64(generator); } a[i] = mp[x]; if (i) a[i] ^= a[i - 1]; } for (int i = 0; i < q; i++) { int l, r; std::cin >> l >> r; l--; r--; if (!l && a[r] == 0 || (a[r] ^ a[l - 1]) == 0) { std::cout << "YES\n"; } else { std::cout << "NO\n"; } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int T = 1; std::cin >> T; while (T--) { solve(); } return 0; } 稍微修改一下G神(GPT)的代码，下面是python版本(已测试)。 ...