A. The Play Never Ends

题意

让我们来介绍一个双人游戏–乒乓球，在这个游戏中，胜负已定，不可能出现平局。

索赛、福福和浩海三个人想一辈子打乒乓球。他们决定以下面的方式永远打下去：

• 在每场比赛中，两名选手比赛，第三名选手旁观。
• 为了保证公平，任何选手都不能连续打三次。在下一场比赛中，连续下两次棋的棋手必须作为观众退场，由另外两名棋手下棋。否则，获胜者和旁观者将参加下一场比赛，而失败者将旁观。

现在，玩家们完全沉浸在这无限循环的比赛中，委托你们解决以下问题：

给定一个整数 $k$ ，判断第一场比赛的观众能否成为 $k$ /第三场比赛的观众。

思路

手玩样例，会发现，若前两个玩家比赛，后一个玩家观战，那么初始排列为ABC的三人，确定第二局比赛的排列后（不妨设为 BCA），他们只能重复进行固定的比赛组合，ABC，BCA，CAB，ABC，…。

所以，验 $nmod3==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+\dots +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{∗}}$ 上的顶点 $\text{st}$ 开始。

给定长度为 $n$ ${}^{\text{†}}$ 的排列 $p$ ，共有 $n$ 步。对于第 $i$ 步来说

• 一块诱人的帕尔马干酪出现在顶点 $p_i$ 。如果老鼠当前位于顶点 $p_i$ ，它将停留在那里享受这一刻。否则，它会沿着简单路径移动到顶点 $p_i$ 。移动一条边。

你的任务是找到这样一种排列方式，使小老鼠在走完所有 $n$ 步之后，不可避免地到达顶点 $\text{en}$ ，那里有一个陷阱在等着它。

请注意，小鼠必须在经过所有 $n$ 步之后到达 $\text{en}$ 处，尽管在此过程中它可能会提前经过 $\text{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 \dots \oplus a_{\lfloor \frac{m}{2}\rfloor }$ ${}^{\text{∗}}$ .

你的任务是计算给定范围 $[l,r]$ ： $a_l+a_{l+1}+\dots +a_r$ .

${}^{\text{∗}}$ $\oplus$ 表示位操作 XOR。

思路

稍微手玩一下样例，试着往后推几位，我们会发现，除了题目给定数组，后面拼接上的生成元素，一般都是两两一对的。

因此，存在一些位置，在求前缀异或和时恰好将所有新生成的元素，全部两两抵消掉了。

可以考虑递归 $l$：

• 当 $x\le n$ 时，返回 $a[x]$；
• 当 $\lfloor x/2\rfloor \le n$ 时，返回 $a[1]\oplus a[2]\oplus \cdots \oplus a[\lfloor x/2\rfloor ]$；
• 当 $\lfloor x/2\rfloor$ 为奇数时，返回 $a[1]\oplus a[2]\oplus \cdots \oplus a[n]$；
• 当 $x$ 为奇数时，返回 $dfs(\lfloor x/2\rfloor )\oplus a[1]\oplus a[2]\oplus \cdots \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 \dots \oplus a_{\lfloor \frac{m}{2}\rfloor }$ ${}^{\text{∗}}$ 。

您的任务是计算给定范围 $[l,r]$ : $a_l+a_{l+1}+\dots +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";
}