A. The Play Never Ends
题意
让我们来介绍一个双人游戏–乒乓球，在这个游戏中，胜负已定，不可能出现平局。
索赛、福福和浩海三个人想一辈子打乒乓球。他们决定以下面的方式永远打下去：
- 在每场比赛中，两名选手比赛，第三名选手旁观。
- 为了保证公平，任何选手都不能连续打三次。在下一场比赛中，连续下两次棋的棋手必须作为观众退场，由另外两名棋手下棋。否则，获胜者和旁观者将参加下一场比赛，而失败者将旁观。
现在，玩家们完全沉浸在这无限循环的比赛中，委托你们解决以下问题：
给定一个整数 $k$ ，判断第一场比赛的观众能否成为 $k$ /第三场比赛的观众。
思路
手玩样例，会发现，若前两个玩家比赛，后一个玩家观战，那么初始排列为ABC的三人，确定第二局比赛的排列后（不妨设为 BCA），他们只能重复进行固定的比赛组合，ABC，BCA，CAB，ABC，…。
所以，验 $n mod 3 == 1$ 即可。
参考代码
void solve() {
int n;
std::cin >> n;
std::cout << (n % 3 == 1 ? "YES\n" : "NO\n");
}
B. Perfecto
题意
长度为 $n$ $^{\text{∗}}$ 的置换 $p$ 如果在每个索引 $i$ ( $1 \le i \le n$ ) 中都满足以下条件，那么这个置换 $p$ 就是完美的：
- 前 $i$ 个元素 $p_1 + p_2 + \ldots + p_i$ 的和不是个完全平方 $^{\text{†}}$ 。
你希望事情是完美的。给定正整数 $n$ ，找出长度为 $n$ 的完美排列，如果不存在，则打印 $-1$ 。
$^{\text{∗}}$ 长度为 $n$ 的排列是由 $n$ 个不同的整数组成的数组，这些整数从 $1$ 到 $n$ 按任意顺序排列。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（ $2$ 在数组中出现了两次）， $[1,3,4]$ 也不是一个排列（ $n=3$ ，但数组中有 $4$ ）。
$^{\text{†}}$ 完全平方是一个整数的平方，例如 $9=3^2$ 是一个完全平方，但 $8$ 和 $14$ 不是。
思路
首先，特判 $\frac{n(n + 1)}{2}$ 是否是完全平方数，然后再随便构造即可。我使用的构造方法是，先从大到小填充数组（为什么倒序，因为正序的话，$1$ 就被放到最前面了），然后顺着遍历一遍数组，判断前缀和是否为完全平方数。如果是，就和下一位 swap 一下。
参考代码
bool ck(i64 x) {
return i64(std::sqrt(x)) * i64(std::sqrt(x)) == x;
}
void solve() {
i64 n;
std::cin >> n;
i64 sum = n * (n + 1) / 2;
if (ck(sum)) {
std::cout << -1 << "\n";
return;
}
std::vector<int> a(n);
std::iota(rall(a), 1);
i64 res = 0;
for (int i = 0; i < n; i++) {
res += a[i];
//assert(!ck(res));
if (ck(res)) {
res -= a[i];
std::swap(a[i], a[i + 1]);
res += a[i];
assert(!ck(res));
}
}
for (auto i : a) std::cout << i << " ";
std::cout << "\n";
}
C. Trapmigiano Reggiano
题意
在意大利的一个村庄里，一只饥饿的老鼠从一棵有 $n$ 个顶点的树 $^{\text{∗}}$ 上的顶点 $\textrm{st}$ 开始。
给定长度为 $n$ $^{\text{†}}$ 的排列 $p$ ，共有 $n$ 步。对于第 $i$ 步来说
- 一块诱人的帕尔马干酪出现在顶点 $p_i$ 。如果老鼠当前位于顶点 $p_i$ ，它将停留在那里享受这一刻。否则，它会沿着简单路径移动到顶点 $p_i$ 。移动一条边。
你的任务是找到这样一种排列方式，使小老鼠在走完所有 $n$ 步之后，不可避免地到达顶点 $\textrm{en}$ ，那里有一个陷阱在等着它。
请注意，小鼠必须在经过所有 $n$ 步之后到达 $\textrm{en}$ 处，尽管在此过程中它可能会提前经过 $\textrm{en}$ 。
$^{\text{∗}}$ 树是一个没有循环的连通图。
$^{\text{†}}$ 长度为 $n$ 的排列是由 $n$ 个不同的整数组成的数组，这些整数从 $1$ 到 $n$ ，顺序任意。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（ $2$ 在数组中出现了两次）， $[1,3,4]$ 也不是一个排列（ $n=3$ ，但数组中有 $4$ ）。
思路
考虑一直选非终点，度数为 1 的叶子节点，将其选择，然后删去。这样可以保证老鼠始终和终点处于同一连通块中。
稍微思索一下就会发现，这其实也相当于直接输出，以终点为根的后序遍历。
参考代码
void solve() {
int n, s, t;
std::cin >> n >> s >> t;
s--; t--;
std::vector<int> d(n);
std::vector edg(n, std::vector<int>());
for (int i = 1; i < n; i++) {
int x, y;
std::cin >> x >> y;
x--; y--;
edg[x].push_back(y);
edg[y].push_back(x);
d[x]++; d[y]++;
}
std::vector<int> ans;
std::vector<int> vis(n);
std::queue<int> q;
for (int i = 0; i < n; i++) {
if (d[i] == 1 && i != t) {
vis[i] = 1;
q.push(i);
}
}
while (q.size()) {
auto now = q.front(); q.pop();
ans.push_back(now);
for (auto nxt : edg[now]) {
if (vis[nxt]) continue;
if (--d[nxt] == 1) {
if (nxt == t) continue;
vis[nxt] = 1;
q.push(nxt);
}
}
}
ans.push_back(t);
for (auto i : ans) std::cout << i + 1 << " ";
std::cout << "\n";
}
D1. Infinite Sequence (Easy Version)
题意
这是问题的简单版本。不同版本的区别在于，在这个版本中， $l=r$ .只有解决了所有版本的问题，您才能破解。
给你一个正整数 $n$ 和一个无限二进制数列 $a$ 的前 $n$ 项，其定义如下：
- 对于 $m > n$ , $a_m = a_1 \oplus a_2 \oplus \ldots \oplus a_{\lfloor \frac{m}{2} \rfloor}$ $^{\text{∗}}$ .
你的任务是计算给定范围 $[l, r]$ ： $a_l + a_{l + 1} + \ldots + a_r$ .
$^{\text{∗}}$ $\oplus$ 表示位操作 XOR。
思路
稍微手玩一下样例，试着往后推几位，我们会发现，除了题目给定数组，后面拼接上的生成元素，一般都是两两一对的。
因此，存在一些位置，在求前缀异或和时恰好将所有新生成的元素，全部两两抵消掉了。
可以考虑递归 $l$：
- 当 $x \le n$ 时，返回 $a[x]$；
- 当 $\lfloor x / 2 \rfloor \le n$ 时，返回 $a[1] \oplus a[2] \oplus \dots \oplus a[\lfloor x / 2 \rfloor]$；
- 当 $\lfloor x / 2 \rfloor$ 为奇数时，返回 $a[1] \oplus a[2] \oplus \dots \oplus a[n]$；
- 当 $x$ 为奇数时，返回 $dfs(\lfloor x / 2 \rfloor) \oplus a[1] \oplus a[2] \oplus \dots \oplus a[n]$.
最后要注意先把数组凑到奇数再跑 $dfs$，不然就没法用两两抵消的性质了。
参考代码
void solve() {
i64 n, l, r;
std::cin >> n >> l >> r;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
a[i] ^= a[i - 1];
}
if (n % 2 == 0) {
a.push_back(a.back());
n++;
a[n] ^= a[n / 2];
}
auto dfs = [&](auto&& self, i64 now) -> int {
if (now <= n) return a[now] ^ a[now - 1];
if ((now / 2) <= n) return a[now / 2];
if ((now / 2) & 1) return a.back();
return self(self, now / 2) ^ a.back();
};
std::cout << dfs(dfs, l) << "\n";
}
D2. Infinite Sequence (Hard Version)
题意
这是问题的困难版本。不同版本的区别在于，在这个版本中， $l\le r$ .只有解决了所有版本的问题，您才能进行 Hack 提交。
给定一个正整数 $n$ 和无限二进制序列 $a$ 的第一个 $n$ 项，其定义如下：
- 对于 $m < n$ ， $a_m = a_1 \oplus a_2 \oplus \ldots \oplus a_{\lfloor \frac{m}{2} \rfloor}$ $^{\text{∗}}$ 。
您的任务是计算给定范围 $[l, r]$ : $a_l + a_{l + 1} + \ldots + a_r$ 中的元素之和。
$^{\text{∗}}$ $\oplus$ 表示按位异或操作。
思路
这里提供一个，个人认为挺直观的方法。
在上一题的“后面拼接上的生成元素，一般都是两两一对的”的基础上，我们继续多玩一点样例出来。
容易发现，当初始数组补成奇数之后，后面进行的操作，可以划分为若干个组，每组都经由上一组的元素所确定。
我们继续手玩样例，研究一下这些组之间的转移关系，看看是否有什么方法能快速处理出前缀和：
当原数组补齐为奇数长度后，有偶数个 $1$ 时，可以得到如下图：
当原数组补齐为奇数长度后，有奇数个 $1$ 时，可以得到如下图：
容易发现，当补齐数组的元素和为偶数时，每轮完整操作后，产生的 $1$ 的个数是固定的，而且位置也很好确定；但是当其为奇数时，每轮完整操作后所产生的 $0$ 和 $1$ 的分布似乎不是很直观。
因此我们可以对奇数和情况进行分类讨论。
考虑如何对奇数情况进行贡献统计：
从奇数情况的图中，我们可以总结出一个规律：从第一轮开始，若将每两个连续相同元素视为同一个元素，则，每个 “1” 元素会生成一个 “0” 元素和 一个 “1” 元素，而每个 “0” 元素会生成两个 “1” 元素。
由于这个转移图的高度是 $\log r$ 的，所以我们可以设 $dp[0][j]$ 表示，从 “0” 号元素开始，向后传递了 $j$ 次贡献后，第 $j$ 层所包含 1 的个数；$dp[1][j]$ 表示，从 “1” 号元素开始，向后传递了 $j$ 次贡献后，第 $j$ 层所包含 1 的个数。
初始状态：$dp[0][0] = 0$，$dp[1][0] = 2$。
转态转移：$dp[0][i] = 2dp[1][i - 1]$，$dp[1][i] = dp[0][i - 1] + dp[1][i - 1]$
dp 数组 的处理是 $O(n\log r)$ 的。
随后我们倍增（应该叫倍增）模拟出最大轮数并记录后，就可以用一种很像分治的方法，结合 $dp$ 数组，对最后一层不完整的轮数，求出其一共含有多少 1。
至于每个完整的轮次钟有多少 1，可以在模拟轮数的过程中，用 $dp$ 数组 $O(1)$ 收集。
偶数情况的话，比奇数情况好写很多，这里不再展开了，建议直接看参考代码理解。
参考代码
void solve() {
i64 n, l, r;
std::cin >> n >> l >> r;
std::vector<int> pre_xor(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> pre_xor[i];
pre_xor[i] ^= pre_xor[i - 1];
}
if (n % 2 == 0) {//将长度补至奇数
n++;
pre_xor.push_back(pre_xor.back());
pre_xor.back() ^= pre_xor[n / 2];
}
// 进行第一轮周期预处理
for (int i = n + 1; i <= 2 * n + 1; i++) {
pre_xor.push_back(pre_xor.back());
pre_xor.back() ^= pre_xor[i / 2];
}
std::vector<int> pre_sum((2 * n + 1) + 1);
for (int i = 1; i <= 2 * n + 1; i++) {
pre_sum[i] = pre_sum[i - 1] + (pre_xor[i] ^ pre_xor[i - 1]);
}
std::vector repeat(2, std::vector<i64>(std::__lg(r) + 2));
repeat[0][0] = 0;
repeat[1][0] = 2;
for (int i = 1; i <= std::__lg(r); i++) {
repeat[0][i] = 2 * repeat[1][i - 1];
repeat[1][i] = repeat[0][i - 1] + repeat[1][i - 1];
}
auto conquer = [&](auto&& self, int dep, i64 pos, int r) -> i64 {
if (dep == 0) return pos * r;
if (pos <= (1ll << dep)) return self(self, dep - 1, pos, 1 ^ r);
return repeat[1 ^ r][dep - 1] + self(self, dep - 1, pos - (1ll << dep), 1);
};
// 初始周期串中 1 的数量
i64 cnt = pre_sum[2 * n + 1] - pre_sum[n];
auto calc = [&](i64 x) -> i64 {
if (x <= 2 * n + 1) return pre_sum[x];
int res = pre_xor[n];
i64 ans = pre_sum[n];
x -= n;
i64 time = 0;
i64 T = n + 1;
i64 w = 0;
i64 unit = 2;
while (x > time + T) {
if (res) ans += cnt * repeat[1][w] / 2 + (n + 1 - cnt) * repeat[0][w] / 2;
else ans += cnt;
time += T;
T <<= 1;
w++;
unit <<= 1;
}
x -= time;
if (res) {
for (int i = 1; i <= x / unit; i++) {
ans += repeat[pre_sum[n + 2 * i] - pre_sum[n + 2 * i - 1]][w];
}
if (2 * (x / unit) + 2 <= n + 1 && x % unit != 0) {
ans += conquer(conquer, w, x % unit, pre_sum[n + 2 * (x / unit) + 2] - pre_sum[n + 2 * (x / unit) + 1]);
}
} else {
for (int i = 1; i <= x / unit; i++) {
ans += 2 * (pre_sum[n + 2 * i] - pre_sum[n + 2 * i - 1]);
}
if (2 * (x / unit) + 2 <= n + 1 &&
pre_sum[n + 2 * (x / unit) + 2] - pre_sum[n + 2 * (x / unit) + 1] == 1
) {
ans += std::min(2ll, x % unit);
}
}
return ans;
};
std::cout << calc(r) - calc(l - 1) << "\n";
}