Codeforces8月解题报告

不定期更新

EDU Round 133

A, B水题

C. Robot in a Hallway

题意

从起点$(1,1)$，在$2\times n$的棋盘上行走，不重、不漏地走过所有格子。每个格子上有一个数$a_{i,j}$，满足在$a_{i,j}$时刻之后才能走向那个格子。求走完所有格子的最小时间。

分析

由于是$2 \times n$的棋盘，并且满足不重不漏，那么前面一段必定是类似蛇形的走法，后面半段则是走到最右之后返回。

那么前面半段采用搜索的方法，枚举蛇形的终止位置，记录走完蛇形的最小时间。然后后面半段可以用类似前缀和的方法。

假设我从$(1,1)$就直接往右走，那么走完第一行的最短时间就是$max(a_{1,i} - i) + n - 1$，其中$max(a_{1,i} - i + 2)$是等待时间，$n-1$为步行时间。这里只是特殊情况，一般情况还需推导。

这题主要就是要推式子，没啥思考

D. Chip Move

题意

给定$n,k$，从$0$出发，第$i$步可以走$(k+i-1)$的倍数（正数）的距离，求走到$x \in [1,n]$的方案数，对每个$x$都分别求。

分析

挺水的一道题。
最朴素的做法：状态$f[i][j]$走$i$步，到达$j$的方案数。转移枚举第$i$走的距离，有$f[i][j] = \sum_{l | k+i-1} f[i-1][j - l]$。
然后发现距离的转移可以优化：$f[i][j] = f[i-1][j-(k+i-1)] + f[i][j-(k+i-1]$，这样复杂度就是$O(n^2)$了。
又因为每一步走的最少距离是递增的，所以最多走$\sqrt{n}$步，所以层数为$\sqrt{n}$，总共的时间就是$O(n\sqrt{n})$。空间滚动数组优化到$O(n)$。

E. Swap and Maximum Block

发现操作和与异或有相同的性质，可以将$[1,2^n]$区间像线段树那样划分，每个区间节点维护所有可能的操作状态，长度为$2^i$的区间节点只需要维护$2^i$种不同的操作状态，剩下$n-i$位只对上层产生影响。因此每层节点的状态数是$2^n$，总共$n$层，时间和空间复杂度是$O(n2^n)$。
节点维护的信息：最大字段和、与左端点相邻的最大字段和、与右端点相邻的最大字段和。跟线段树一样去合并信息就好了。

F. Bags with Balls

题意

$n$个盒子，每个盒子中有$m$个有标号的小球（不同盒子中相同标号的小球认为是不同的），标号$\in [1, m]$。从每个盒子中随机取出一个小球，令$F$标号是奇数的小球个数。求所有取球方案的$F^k$的和。

分析

首先令$x,y$表示盒子中标号为奇数和偶数的小球个数：$x=\frac{m+1}{2},y = \frac{m}{2}$。得到奇数标号的小球数量为$c$的方案数$f(c) = C_n^c \times x^c \times y^{n-c}$。$ans=\sum_{i=1}^{n} i^k \times C_n^i \times x^i \times y^{n-i}$
但是$n \leq 998244352$，显然是不能通过的。$O(Tk)$才是能通过的复杂度。

考虑$i^k$的意义，等价于将$k$个小球放入$i$个盒子（不同、可空）的方案数。若枚举考虑非空盒子的数量$j$，$i^k = \sum_{j=1}^{i} C_i^j \times S(k, j) \times j!$。$C_i^j$表示取$j$个盒子的方案，$S(i,j)$为第二类斯特林数，将$k$个小球放入$j$个非空盒子（相同）的方案数，$j!$是盒子的排列。

代入到原式子

$ans = \sum_{i=1}^{n} i^k \times C_n^i \times x^i \times y^{n-i} \\ =\sum_{i=1}^{n} C_n^i \times x^i \times y^{n-i} \sum_{j=1}^{i} C_i^j \times S(k, j) \times j! \\ （改变求和顺序）= \sum_{j=1}^{n} S(k,j) \times j! \sum_{i=j}^{n}C_i^j \times C_n^i \times x^i \times j^{n-i} \\ = \sum_{j=1}^{n} S(k,j) \times j! \sum_{i=j}^{n}C_n^j \times C_{n-j}^{i-j} \times x^i \times j^{n-i} \\ = \sum_{j=1}^{n} S(k,j) \times j! \times C_n^j \sum_{i=j}^{n} C_{n-j}^{i-j} \times x^i \times j^{n-i} \\ （二项式定理）= \sum_{j=1}^{n} S(k,j) \times j! \times C_n^j \times x^j \times (x+ y)^{n-j} \\$

斯特林数和组合数可以预处理，复杂度为$O(Tk + k^2)$

---

Codeforces Round 812

A,B,C水题

D. Tournament Countdown

题意

交互题，$2^n$个人进行锦标赛制。$a_i$表示第$i$个人的胜利次数。每次询问$i,j$，如果$a_i < a_j$返回 1，如果$a_i > a_j$返回 2，如果$a_i=a_j$返回 0。使用不超过$\frac{1}{3}2^{n+1}$次询问找到冠军。

分析

如果每$4$个人使用$2$个询问，则使用的次数为$2^{n-1} + 2^{n-3} + … =\leq \frac{1}{3}2^{n+1} $。
在相同组的$4$个人中，$a_i$是类似$\{0,1, 0, 2\}$分布的，两人的小组必有$a_i=0$和$a_j!=0$。
查询$1,4$

• 返回 0，表示$1,4$的$a_i=0$，都不是胜者，再在$2,3$当中查
• 返回 1，表示$a_1 \neq 0, a_4=0$，胜者在$1,3$当中
• 返回 2，表示$a_1=0, a_4 \neq 0$，胜者在$2,4$当中

每一组的四个人都是这样的。递归解决，每一层规模$\div 4$。

E. Cross Swapping

题意

对一个$n\times n$的矩阵进行若干次操作，可将矩阵的第$k$行和第$k$列交换。最后使得矩阵的字典序最小（从第一行读到第$n$行）

分析

从前往后逐个扫描，假设当前是第$i$行第$j$列的元素$a[i][j]$，和$a[j][i]$进行比较，如果要使它交换，则$i$和$j$只能被选其中一个；如果不交换，则$i$和$j$可以被选两个或都不选。
这样就变成了$i$和$j$的相对关系，用带权并查集或者扩展域并查集来维护。

F. Lost Array

to be updated
SOS Dp
SOS Dp 逆运算