题解

· · 题解

1.decrypt（T1 难度）

知识点：二进制

直接枚举统计即可。O(w\sum n),w=32。

2.station（T2 难度）

知识点：数学（鸽巢定理）、前缀和

注意到当 n>m 时，由鸽巢定理（好像超纲了），一定存在 d_i\equiv d_j\pmod m，因此答案一定为 0。所以只需要在 n\le m 时暴力计算即可。O(Tm^2)。

不过如果有人写了个 O(nm) 的算法并且在 n 过大时直接输出 x，就算不知道鸽巢定理也能水过这道题，所以个人认为这道题不好（主要是恰好控制难度有点困难，只好出一道大水题）。

3.swap（T3 难度）

知识点：动态规划/BFS

令 f[i][j] 表示前 i 个操作后，那盘菜在第 j 个位置的最小代价。

假设第 i 次交换为 u_i,v_i，则 f[i][u_i]=\min(f[i-1][v_i],f[i-1][u_i]+1)，f[i][v_i]=\min(f[i-1][u_i],f[i-1][v_i]+1)。对于其他位置，f 不变。

因此容易想到利用滚动数组优化掉第一维，DP 转移每次只用修改两个位置的 f。O(m)。

也有比较复杂（但也是我最开始想到）的 BFS 做法，因为时间复杂度更劣（O(m\log n)）且代码很复杂（也可能是我写的过于丑了），因此这里不再赘述，具体看 std。

4.sequence（T3 难度）

知识点：数学（组合）

打表/分析得到 n=4k+1,k\in\mathbb{N} 时才有解。否则符合要求的字符串个数为 0。因此特殊情况 A 直接输出 0 有 10pts。

因为以 0 开头和以 1 开头的个数应该是一致的，因此这里只考虑以 0 开头，最后将答案乘 2 即可。以 0 开头则有 2k+1 个 0，2k 个 1。

假设开始时是一个 0 后面跟着 2k 个 1，然后使用隔板法。因为有 k 组 10，所以要选出 k 个 1 后面跟上 0。同时考虑到要有 k 个 11，因此最后一个 1 必须接一个 0。这一部分的方案数为 \tbinom{2k-1}{k-1}。

然后还剩 k 个 00 需要解决。还有 k+1 处地方可以放 0，一共要放 k 个。因为可能几个 0 放在同一个位置，也即把 k 个元素分成 k+1 组，允许为空，由隔板法得这一部分的方案数为 \tbinom{2k}{k}。

因此 ans=2\times\tbinom{2k-1}{k-1}\tbinom{2k}{k}。

5.transfer（T4 难度）

知识点：数学（逆元）、模拟、最短路、分层图（好像超纲了）

尝试迭代函数 f(x)，发现 f(f(f(f(x))))=x，也就是迭代四次之后就重复了，这启发我们对每一种 z_i 建一层图，每条边从下层连向上层，然后在分层图中跑最短路即可。O(n+m)。

6.bx（T4 难度）

知识点：数学，模拟，构造

令 even=p,odd=k-p。

首先由小学二年级知识可以知道：奇数加奇数得偶数；奇数加偶数得奇数；偶数加偶数得偶数。

对于偶数堆，我们放入一个偶数大小的苹果，如果没有这样的苹果了就放两个奇数大小的苹果；对于奇数堆，先填完 odd-1 堆，之后把剩下的最后一个奇数堆里。

如果奇数不够用或者全部填完后第一堆的大小和为偶数则无解。

结语

组题用了 1346，个人感觉还行，std 周末放上来。