自动搬运

查看原文

来自洛谷，原作者为

	chenly8128 God helps those who help themselves.

搬运于2025-08-24 23:04:32，当前版本为作者最后更新于2024-09-29 10:00:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前置知识

• 博弈论
• 状态转移
• 找规律

找规律

根据标准的博弈论思想，我们可以记录每一个状态下，先手有没有必胜策略。如果能转移到一个先手必败的状态，那么有先手必胜策略；反之亦然。

可以发现每一次操作碎片至少减少一块，所以不可能出现循环，状态转移是比较明确的。

然后开始手推不同的状态。我们用 $n$ 来表示剩余几堆。

$n = 1$ 时：

很显然，先手必胜，全部丢弃即可。

$n = 2$ 时：

根据博弈论的基本原理，可以得到如果先手率先把其中的一堆丢光，那么只剩下一堆了，会导致后手获胜，先手必败。

当两堆个数分别为 $i,j (i \leq j)$ 的情况。首先给出结论：$i = j$，则先手败；$i \neq j$，则先手胜。

证明：运用归纳法。

1. $k = 1$，在两堆都只有 1 个碎片的情况下，先手被迫减少堆数，先手必败。如果一堆有 1 个碎片，另一堆有 $j (j > 1)$ 个碎片那么可以将状态转移为每堆都是 1 的情况，先手必胜。
2. $k > 1$，假设在 $i = k-1$ 的情况下，该结论正确。那么当 $i = j = k$ 时，状态只能转移成 $i$ 更小的状态，而且转移形成的状态 $i \neq j$，所以先手必败。当 $i = k$，$j > k$ 时，可以转移成 $i = j = k$ 的状态，所以先手必胜。

证明完毕。

$n = 3$ 时：

结论：先手必胜。

因为，可以把碎片数量最大的一堆给选出来，用它的碎片把数量最小的一堆给补到与另外一堆数量相等，然后把剩下的碎片全部丢弃。就转移到了两堆的先手必败情况，所以 $n = 3$ 时先手必胜。

$n$ 为偶数时：

可以通过总结规律得到判断方法：

1. 设每一堆碎片的数量组成长度为 $n$ 的数组 $a_{1,2,\dots,n}$。
2. 将 $a$ 从小到大排序。
3. 如果存在 $i$ 使得 $a_{2i-1} < a_{2i}$，那么先手必胜。反之先手必败。

证明类似于 $n = 2$ 的情况，只是复杂一些，略。

$n$ 为奇数时：

与 $n = 3$ 的情况类似，先手必胜。

证明类似。

实现

当你发现了上述规律，并且能够说明为什么了的时候，你就差不多解决了这道题了。

Init

根据上述规律排序并判断即可。

Get

记录上一步的数组，我的实现中 GET 函数几乎什么都没做。

Play

这是重点！！！分成两种情况：

1. $n$ 是奇数：显然需要减少一堆碎片，并且转移为必败状态。我的方法是先进行排序，然后把碎片最多的一组的删掉，把排序好的 $a$ 数组中的 $a_{2i-1}$ 赋值为 $a_{2i}$。可以证明增加的碎片数比删掉的要少。最后把 $a$ 数组恢复成原来的顺序。
2. $n$ 是偶数：显然不应该删掉任何一堆，应该转移为先手必败的状态。我的方法是先进行排序，然后记录不同碎片数量的出现次数。将出现次数为奇数的碎片数量设为 $b_{1,2,\dots,m}$，要求 $b$ 严格单调递增。然后将 $b_m$ 改为 $b_1$，将剩下的 $b_{2i}$ 改为 $b_{2i+1}$，可以证明增加的碎片数比删掉的要少。将 $b$ 数组上的改动映射到 $a$ 上，最后把 $a$ 数组恢复成原来的顺序。

这样就转移成了必败状态。

代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
struct point {
	int id,val;
	bool operator < (const point b) const {
		return val < b.val;
	}
};
vector <point> v;
vector <int> Play(void) {
	int n = v.size();
	sort (v.begin(),v.end());
	if (n&1) {
		vector <int> res(n);
		for (int i = 0;i < n-1;i += 2) {
			res[v[i].id] = v[i+1].val;
			res[v[i+1].id] = v[i+1].val;
		}
		return res;
	}
	vector <int> res(n);
	vector <point> v2(0);
	for (int i = 0;i < n;i++) {
		if (i < n-1 && v[i].val == v[i+1].val) {
			res[v[i].id] = v[i].val;
			res[v[i+1].id] = v[i+1].val;
			i++;
			continue;
		}
		else v2.push_back(v[i]);
	}
	if (v2.size()) {
		assert (v2.size()>1);
		for (int i = 1;i < v2.size()-1;i += 2)
			res[v2[i].id] =  res[v2[i+1].id] = v2[i+1].val;
		res[v2[0].id] = v2[0].val;
		res[v2[v2.size()-1].id] = v2[0].val;
	}
	fflush(stdout);
	return res;
}
void Get(vector<int> a) {
	v.clear();
	for (int i = 0;i < a.size();i++)
		v.push_back((point){i,a[i]});
	return;
}
bool Init(int n, int op,vector<int> a) {
	v.clear();
	for (int i = 0;i < a.size();i++)
		v.push_back((point){i,a[i]});
	if (a.size()&1) return false;
	sort (a.begin(),a.end());
	for (int j = 0;j < a.size()-1;j += 2)
		if (a[j] != a[j+1]) return false;
	return true;
}

注意不要用 C++14（GCC 9）。轻松 AC。