Skip to content

2023“钉耙编程”中国大学生算法设计超级联赛（7）

A. Xcellent Tree Query Problem

B. Random Nim Game

题意：Nim 游戏的随机版本，每个人可以自由选择石堆，但是选择的石子是从可能的结果中均匀随机的，求先手获胜的概率

首先考虑一堆的情况，很容易发现只有当 $n=1$ 时必胜，否则概率为 $\frac 12$ 然后考虑多堆，假设所有的都是 $1$，则按奇偶性讨论即可；否则不论选哪个不为 $1$ 的堆，都有 $\frac 12$ 概率最终剩下 $1$，$\frac 12$ 最终剩下 $0$，所以最终有 $\frac 12$ 概率有奇数堆 $1$，$\frac 12$ 有偶数堆 $1$，故先手获胜概率为 $\frac 12$，输出即可，复杂度 $O(1)$

C. Rotation

D. Medians Strike Back

题意：求构造一个长度为 $n$ 且值域为 $3$ 的数列，使得该数列的任意子区间的中位数出现次数的最大值最小，并输出中位数出现次数的最小值

考虑将问题转化为构造子区间中中位数出现次数最大值为 $n$ 的最长数列长度

首先有一个比较容易发现的事实，假如只考虑中位数为 $2$ 的子区间，那么很容易构造出如下数列满足中位数出现次数最多为 $2$：$1313...1313221313..1313$

中位数出现次数为 $n$ 时，我们可以首先构造出来一个类似上面模式的数列，两边的 $1$ 和 $3$ 都各有 $n$ 个，这样就保证了只含有 $1,3$ 的区间有 $n$ 个中位数，含有 $2$ 的区间有 $2$ 个中位数。由于这样的区间满足包含 $2$ 的区间 $2$ 一定是中位数，所以我们只需要类似这样构造出如下数列：$1313...131322131313...13132221313...1313 ...$，这样就能满足含有 $2$ 的区间中位数最多有 $n$ 个的条件了，根据规律很容易计算出这样的数列长度是 $(\lfloor\frac n2\rfloor+1) \times 2n+n$，然后就可以随便搞了，解二次函数也可，直接二分也可，复杂度 $O(T\log n)$，可以通过

E. Subsequence Not Substring

题意：求 $S$ 字典序最小的不是子串的子序列

考虑把子串自动机和子序列自动机搞出来，不考虑复杂度的话每次从 $|\Sigma|^0$ 贪心即可，但这样需要遍历所有的子串，复杂度会达到 $O(n^2)$，然后我们注意到如果一个节点后面能得出的子串和子序列个数是相同的，我们本质上就不会继续往下走了，所以我们可以反向拓扑 dp 先跑出来从每个点出发的路径数，每次判断一下能走出的路径数相不相等即可，虽然子序列自动机可能会出现溢出，但由于是判断相等，可以理解成无模哈希，所以没有区别，最终复杂度 $O(n|\Sigma|)$，可以通过

F. Product of Sorting Powers

G. Sum of Binomial Coefficients

H. HEX-A-GONE Trails

题意：两个人在树上博弈，每个人每次可以在树上走一步，但不能前往自己或对方走过的点，两人轮流前进，先走不了的输，求先手是否存在必胜策略

首先考虑将两人起始点所在的路径拎出来，可以发现每次每个人的移动可以分为两类：在路径上走/下到子树里，容易发现如果选择下到子树里，那么其可以移动的最大步数和对方可以移动的最大步数都可以很简单的求出来，这样就可以直接得到下到子树是否必胜，而由于只有两种选择，如果不是必胜的话，那么不论结果是否存在必胜策略，为了达到更优的解都必须继续在路径上走，知道两人相撞或任意一方下到子树里必胜，所以直接模拟即可，复杂度是每次求一个区间最小值，不带修，复杂度 $O(n\log n)$，可以通过

I. Colorings Counting

J. Widely Known Problem

K. Three Operations

题意：给定三种操作：$x=x-1,x=\lfloor\frac{x+a}2\rfloor,x=\sqrt{x+b}$，求让 $x$ 变成 $0$ 的最小操作次数

考虑贪心，每次找三种操作能使当前数到达的最小值，如果是 $x-1$ 的话说明要减到底，直接做就可以，复杂度 $O(T\log n)$，可以通过

正确性证明： 1. 对于 $x$，一定是往下比较优，且是到可能的最小值最优，因为 $x$ 能到达的最小值一定 $\leq$ 任意比 $x$ 大的数能到达的最小值，往上步数只会平白无故增加而已 2. 是 $x-1$ 的话一定是减到底，因为 $\lfloor\frac{x+a}2\rfloor,\sqrt{x+b}$ 都是单调递增的函数

L. Landmine

M. Minimal and Maximal XOR Sum

题意：给定一个排列，你可以反转任意个子区间使其称为 $1 \sim n$，求所有反转区间长度异或和的最小值和最大值

首先有一个很容易发现的事实：对于长度为 $2^k(k \geq 2)$ 的区间，我们可以通过反转若干个长度为 $2$ 的区间之后反转整个区间，使得在不改变原序列顺序的情况下在最终结果上加上/减去一个二进制位的贡献，那么剩下需要考虑的就只有 $1/2$ 对应二进制位的可能结果

$1$ 很明显可以反转一个长度为 $1$ 的区间增加/删除，而 $2$ 由于一定造成的逆序对数的变化所以无论怎么翻转这一位的结果都确定 $=$ 序列的逆序对数 $\&1$，所以只要求一下逆序对数即可，复杂度 $O(n\log n)$，可以通过