2025 bnuzh 周赛-6

BNUZH-ACM 周赛 Round 6 - 洛谷 | 计算机科学教育新生态

A 置换环

Solution

显然 $n=1$，答案是 $1$，$n=2$，答案是 $3$。由样例得知，$n=3$ 时答案为 $6$。

继续手动枚举 $n=4$ 的情况，也容易得到答案是 $10$，在 $\{4,3,2,1\}$ 时取得。

由此合理猜测答案是 $\frac{n(n+1)}{2}$，在序列为倒序时取得。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    cout << (n + 1LL) * n / 2 << endl;
    for (int i = n; i >= 1; i--)
        cout << i << " ";
    cout << endl;
    return 0;
}

Proof

这是一个非常经典的组合优化问题。为了证明最大权值为 $\frac{n(n+1)}{2}$ 且倒序排列是最优解，我们可以将证明分为理论上界分析和构造验证两个部分。

一、 理论上界的证明

我们的目标是最大化 $V(A)$，即 $n$ 个循环同构排列中所有置换环的个数总和。为了方便分析，我们可以转换视角：不再去数每个图中“有多少个环”，而是去计算所有可能出现的边对总权值的“贡献”。

边的总数与分布：

考虑一个排列 $A$ 及其所有 $n-1$ 个循环移位。

对于任意一个位置 $u$ ($1 \le u \le n$)，随着排列的循环移位，该位置上的数值 $a_u$ 会遍历 $1$ 到 $n$ 的所有值恰好一次。

这意味着，如果我们把这 $n$ 个排列对应的 $n$ 张图叠加在一起，我们实际上得到了一个包含 $n$ 个顶点的完全有向图（包含自环）。

在这个完全有向图中，总共有 $n^2$ 条有向边，且每一条边 $(u, v)$ 都恰好在某一个循环移位的图中出现了一次。

边对答案的贡献：

在一个置换图中，如果一个置换环的长度为 $L$，那么这个环里包含 $L$ 条边。

我们可以认为，这 $L$ 条边共同贡献了 $1$ 个环。平均下来，每一条属于长度为 $L$ 的环的边，对总答案的贡献是 $\frac{1}{L}$。

极值分析：

要使总权值 $V(A)$ 最大，我们需要让每条边的贡献 $\frac{1}{L}$ 尽可能大，也就是要让每条边所在的环长 $L$ 尽可能小。

• 自环的情况 ($L=1$)：

  对于 $n$ 个顶点，总共只有 $n$ 条可能的自环边 $(i, i)$。

  当边 $(i, i)$ 出现时，它构成一个长度为 $1$ 的环，贡献为 $\frac{1}{1} = 1$。

  这 $n$ 条自环边必然会在 $n$ 次循环移位的过程中各出现一次，无法避免也无法增加。

  因此，自环部分的总贡献固定为 $n \times 1 = n$。

• 非自环的情况 ($L \ge 2$)：

  除去 $n$ 条自环边，剩下的 $n^2 - n$ 条边都是 $u \neq v$ 的边。

  对于这些边，能构成的最小环长是 $2$（即 $u \to v \to u$）。

  此时每条边的最大贡献是 $\frac{1}{2}$。

计算上界：

综上所述，理论上的最大权值为：

V_{max} = (\text{自环边数} \times 1) + (\text{非自环边数} \times \frac{1}{2})

$V_{max} = n + \frac{n^2 - n}{2} = \frac{2n + n^2 - n}{2} = \frac{n(n+1)}{2}$

二、 倒序排列的构造证明

为了证明上界是可以达到的，我们需要寻找一个排列，使得它的所有 $n$ 个循环移位中，所有的置换环长度都不超过 2（即不存在长度 $\ge 3$ 的环）。这样的置换被称为“对合”（Involution），即满足 $P(P(i)) = i$。

我们证明倒序排列 A = \{n, n-1, \dots, 1\} 满足此性质。

循环移位的结构分析

设原排列为 P_0 = \{n, n-1, \dots, 1\}。

考虑向右循环移位 $k$ 次后的排列 $P_k$。这个序列在形态上会被分为两段递减的子序列：

• 第一段（前 $k$ 个数）： 数值从 $k$ 递减到 $1$。

  对于位置 $i$ ($1 \le i \le k$)，其对应的数值是 $p_i = k - i + 1$。

• 第二段（后 $n-k$ 个数）： 数值从 $n$ 递减到 $k+1$。

  对于位置 $j$ ($k+1 \le j \le n$)，其对应的数值是 $p_j = n - (j - (k + 1)) = n + k + 1 - j$。

验证环长性质

我们需要验证对于任意位置 $x$，应用两次置换后是否回到原点，即验证 $P_k(P_k(x)) = x$。

• 对于第一段的位置 $i$ ($1 \le i \le k$)：

  映射规则为 $i \to k - i + 1$。

  显然，映射后的位置 $k - i + 1$ 仍然在 $[1, k]$ 的范围内。

  再次应用映射：

  $P_k(k - i + 1) = k - (k - i + 1) + 1 = i$

  这说明第一段内的元素要么构成自环（当 $i = k - i + 1$），要么构成长度为 2 的互换环。

• 对于第二段的位置 $j$ ($k+1 \le j \le n$)：

  映射规则为 $j \to n + k + 1 - j$。

  同理，映射后的位置仍然在 $[k+1, n]$ 的范围内。

  再次应用映射：

  $P_k(n + k + 1 - j) = n + k + 1 - (n + k + 1 - j) = j$

  这说明第二段内的元素也全部构成长度为 1 或 2 的环。

结论

由于倒序排列的每一次循环移位所生成的置换图中，所有环的长度均只有 $1$ 或 $2$，这意味着我们成功让所有非自环边都贡献了最大可能的权值 $\frac{1}{2}$。

因此，倒序排列 A = \{n, n-1, \dots, 1\} 的权值能够达到理论上界 $\frac{n(n+1)}{2}$。

证毕。

B Creating Chaos

Solution

注意到 $\gcd(|a_i-a_j|,n)\le \min\{|a_i-a_j|,n\}$，因此尽可能使得 $|a_i-a_j|$ 变小是一个方向。

尝试将 $1\sim k$ 去除，剩下 $(k+1)\sim n$ 这些连续的数字。发现 AC 了。

Code

for (int i = 1; i <= k; i++)
	cout << i << ' ';

Proof

这是一个基于数论中 欧拉函数（Euler’s Totient Function） 性质的严格证明。

我们将通过转换求和公式，利用凸函数性质，证明保留连续区间能使得权值和达到理论下界。

符号定义与目标

设 $n$ 为给定的数，我们保留的数字集合为 $S$，其中 $|S| = m = n - k$。

我们的目标是最小化目标函数：

$V(S) = \sum_{\{x, y\} \subseteq S, x < y} \gcd(y - x, n)$

利用欧拉函数转换目标函数

利用数论中的经典恒等式：

$\gcd(k, n) = \sum_{d | k, d | n} \phi(d)$

其中 $\phi(d)$ 是欧拉函数（小于等于 $d$ 且与 $d$ 互质的正整数个数），且 $\phi(d) > 0$。

将此恒等式代入目标函数 $V(S)$：

$V(S) = \sum_{\{x, y\} \subseteq S} \sum_{d | (y-x), d | n} \phi(d)$

我们可以交换求和顺序。首先枚举 $n$ 的所有因子 $d$，然后计算有多少对 $(x, y)$ 的差是 $d$ 的倍数：

V(S) = \sum_{d | n} \phi(d) \times \left( \text{满足 } y \equiv x \pmod d \text{ 的数对 } \{x, y\} \subseteq S \text{ 的数量} \right)

分析同余类分布

对于固定的因子 $d$，为了计算上述括号内的数量，我们将集合 $S$ 中的元素按照模 $d$ 的余数分类。

设 $c_r$ 为集合 $S$ 中满足 x \equiv r \pmod d 的元素个数（其中 r \in \{0, 1, \dots, d-1\}）。

显然，所有余数的计数之和等于集合大小：

$\sum_{r=0}^{d-1} c_r = m$

在模 $d$ 同余的任意两个数，它们的差必然是 $d$ 的倍数。因此，对于固定的 $d$，满足条件的数对数量为：

$\text{PairCount}_d(S) = \sum_{r=0}^{d-1} \binom{c_r}{2} = \sum_{r=0}^{d-1} \frac{c_r(c_r - 1)}{2}$

现在，目标函数可以重写为：

$V(S) = \sum_{d | n} \phi(d) \sum_{r=0}^{d-1} \frac{c_r(c_r - 1)}{2}$

利用凸函数性质求下界

我们要最小化 $V(S)$。由于 $\phi(d)$ 总是正数，如果存在一种构造 $S$，能够同时使每一项 $\sum_{r=0}^{d-1} \frac{c_r(c_r - 1)}{2}$ 达到最小，那么该构造必然是全局最优解。

考虑函数 $f(x) = \frac{x(x-1)}{2}$。这是一个严格凸函数（Strictly Convex Function），因为其二阶导数 $f''(x) = 1 > 0$。

根据琴生不等式（Jensen’s Inequality）或凸优化的基本原理：

在变量总和 $\sum c_r = m$ 固定的情况下，要最小化凸函数之和 $\sum f(c_r)$，变量 $c_r$ 必须分布得越均匀越好。

也就是说，对于任意 $r_i, r_j$，计数的差值 $|c_{r_i} - c_{r_j}|$ 不能超过 1。

理想的分布是：

• 有 m \pmod d 个余数，其计数为 $\lceil m/d \rceil$。
• 剩下的余数，其计数为 $\lfloor m/d \rfloor$。

任何打破这种均匀分布的集合（即某些余数出现次数特别多，某些特别少），都会导致 $\sum \frac{c_r(c_r-1)}{2}$ 增大。

证明连续区间是最优解

现在我们验证连续整数集合 S_{con} = \{1, 2, \dots, m\} 是否满足上述“最均匀分布”条件。

对于 $S_{con}$ 中的元素，模 $d$ 的余数序列是：

1, 2, \dots, d-1, 0, 1, 2, \dots

这是一个周期为 $d$ 的循环序列。

当选取 $m$ 个连续整数时：

1. 我们完整经历了 $\lfloor m/d \rfloor$ 个周期。
2. 多出来的 m \pmod d 个数会依次填充余数 1, 2, \dots。

因此，在 $S_{con}$ 中，对于任意因子 $d$（事实上是任意整数 $d$）：

• 某些余数出现了 $\lceil m/d \rceil$ 次。
• 其他余数出现了 $\lfloor m/d \rfloor$ 次。
• 两者之差仅为 1。

这意味着，$S_{con}$ 使得每一个因子 $d$ 对应的项 $\text{PairCount}_d(S)$ 都达到了理论上的数学下界。

结论

由于目标函数 $V(S)$ 是若干非负项的加权和，而连续区间 $S_{con}$ 能够同时使每一项都取到在约束 $|S|=m$ 下的最小值。

因此，$S_{con}$（即保留连续的 $n-k$ 个数）必然是使得 $V(S)$ 最小的最优解。

证毕。

C Meaningless Operations

Solution

对任意的正整数 $a$，二进制有 $n$ 位，只要 $b$ 的二进制每位都和 $a$ 相反，就有

$\gcd(a\oplus b,a \& b)=\gcd(2^n-1,0)=2^n-1$

且 $b<a$ 一定成立，显然 $2^n-1$ 是 $\gcd$ 的上界。

但是，当 $a=2^n-1$ 时，$b=0$，不符合 $[1,a-1]$ 的要求。根据数据范围，这样的 $a$ 最多只有 $25$ 个，枚举并特判即可。

Code

如果超时，可以先利用此程序打表出 $25$ 个 $a=2^n-1$ 的答案。

#include <bits/stdc++.h>
using namespace std;

int T, n;

void solve()
{
    cin >> n;
    int num = 1, flg = 0, cnt = 0, ans = 0;
    while (num) {
        if (!(num & 1)) {
            flg = 1;
            break;
        }
        num >>= 1;
        cnt++;
    }
    if (flg) 
        cout << (1 << cnt) - 1 << endl;
    else {
        for (int i = 1; i < n; i++)
            ans = max(ans, __gcd(n ^ i, n & i));
        cout << ans << endl;
    }
}

int main()
{
    cin >> T;
    while (T--) solve();
    return 0;
}

D 取沙子游戏

Solution

注意到只要有一个人取 $1$，之后每次双方都只能取 $1$。

如果剩下奇数个沙子给对方，那么只要对方下一次取 $1$，你就输了。换言之不能留给对方奇数的局面；自己一旦面对奇数，自己是必赢的。

因此，我们需要讨论的是一开始沙子数量为偶数的情况。这个情况下，$n=2^mq$，其中 $m>1$，$q$ 为奇数。

我们定义 $lowbit(n)$ 为 $n$ 的二进制表示中最低位的 $1$ 所对应的值。不妨设 $n = 2^m \cdot q$，其中 $q$ 为奇数，此时 $lowbit(n) = 2^m$。

我们将证明：若 $2^m \le k$，则先手必胜；否则先手必败。

首先，让我们考察当 $2^m \le k$ 时，Alice 的必胜策略。

Alice 的最佳策略是第一步取走 $x = 2^m$ 粒沙子。这步操作是合法的，因为 $2^m \le k$。

在 Alice 取走 $2^m$ 后，剩余的沙子数量变为 $n - 2^m = 2^m(q - 1)$。由于 $q$ 是奇数，所以 $q-1$ 必然是偶数，这意味着剩余的沙子数量实际上是 $2^{m+1}$ 的倍数，即剩余沙子中包含着“偶数个” $2^m$。

接下来轮到 Bob 行动。根据规则，Bob 选取的沙子数量 $y$ 必须是上一轮 Alice 选取的 $x = 2^m$ 的因数。这意味着 $y$ 必须是 2^0, 2^1, \dots, 2^m 中的某一个。这里会出现两种情况：

第一种情况，Bob 选取了 $y = 2^m$。

此时，Bob 并没有改变游戏的“粒度”，依然维持在 $2^m$ 的层级上。只要 Bob 坚持取 $2^m$，Alice 也随之取 $2^m$。由于初始沙子包含奇数个 $2^m$，且 Alice 取走了第一个，剩余偶数个。在随后的“你取一个、我取一个”的拉锯战中，Bob 总是面临剩余奇数个 $2^m$ 的局面，而 Alice 总是面临剩余偶数个 $2^m$ 的局面。显然，最后一个 $2^m$ 将会被 Alice 取走，Alice 获胜。

第二种情况，Bob 试图改变局势，选取了更小的因数 $y = 2^j$ （其中 $j < m$）。

这相当于 Bob 主动将游戏的粒度从 $2^m$ 降级到了 $2^j$。让我们看看这对他意味着什么：此时剩余的沙子总数是 $2^{m+1}$ 的倍数，自然也是 $2^{j+1}$ 的倍数。换言之，在以 $2^j$ 为单位的新局面中，剩余沙子的份数是偶数。

此时轮到 Alice，且限制条件变为 $y=2^j$。这对于 Alice 来说，相当于她成为了一个新的子游戏的后手，而这个子游戏的初始沙子数量是 $2^j$ 的偶数倍。根据对称性原理（或者简单的模仿策略），面对偶数份沙子的先手（此时的 Bob）是必败的，因为 Alice 只要模仿 Bob 的操作（Bob 取 $z$，Alice 也取 $z$）即可耗尽沙子。

综上所述，只要 Alice 第一步取走 $lowbit(n)$，无论 Bob 维持原粒度还是降低粒度，Alice 均有必胜策略。

反之，让我们考察 $2^m > k$ 时，为何 Alice 必败。

由于 $k < 2^m$，Alice 无法取走 $2^m$。她只能选取一个较小的数 $x$ （$x \le k < 2^m$）。

因为 $x < 2^m$，所以 $x$ 必然无法被 $2^m$ 整除，这意味着 $x$ 的二进制最低位 $lowbit(x)$ 一定小于 $2^m$。

当 Alice 取走 $x$ 后，剩余沙子 $n-x$ 的二进制最低位将由 $x$ 决定，即 $lowbit(n-x) = lowbit(x)$。

此时局面交给了 Bob，且限制条件变为 $x$。注意到 $lowbit(n-x)$ 显然小于等于 $x$，这完全符合我们前面证明的“必胜条件”。Bob 此时处于一个新局面的先手位置，面对的沙子总量 $N'$ 满足 lowbit(N') \le \text{当前限制 } x。

因此，Bob 可以复制 Alice 在必胜情况下的策略：取走 $lowbit(n-x)$ 粒沙子，从而掌握游戏的控制权并最终获胜。

综上所述，Alice 能够获胜的充要条件是她有能力在第一步取走 $lowbit(n)$，即 $lowbit(n) \le k$。证明完毕。

Code

$lowbit(x)$ 可用位运算 x & (-x) 求出。

#include <bits/stdc++.h>
using namespace std;

int T, n, k;

void solve()
{
    cin >> n >> k;
    if ((n & -n) <= k) 
        cout << "Alice\n";
    else
        cout << "Bob\n";
}

int main()
{
    cin >> T;
    while (T--) solve();
    return 0;
}