暑期多校总结

牛客多校

第一场

D

两个人博弈，每次可以取走一个矩形的左上角，取走最后一块的输，问先手是否必胜。

可以发现，当矩形退化为一个点时，先手必败，其余先手必胜

因为若矩形不为一个点时，先手可以取走一个极大的矩形，使得剩下的是一个 $L$ 形，然后最终会成为一条矩形，此时先手只要取到只剩下一个点即可

J

一个人玩游戏，最开始 $x=1$，赢了会获得 $x$ 元并重新将 $x$ 置为 $1$，输了会失去 $x$ 元并让 $x=x\times 2$，输赢概率都为 $0.5$，最开始有 $n$ 元，问在钱数不为负数的情况下获得 $n+m$ 元的概率

仔细观察给定的式子，会发现每次赢都是只净赢一块，那连续输的次数就不能超过 $\log x$，次数在某一段中是相等的，这样的段只有 $\log$ ，每段需要一个快速幂，所以最后的时间复杂度为 $\log^2$

K

对于一个无向图，可以把某条边分裂成一个点连两条边，问操作任意多次后，距离节点 $1$ 不超过 $k$ 的点最多有多少个

先考虑链，那答案其实是固定的，因为当加入的点达到这个值后，再加入点也不会让答案更优

再考虑图，不难发现，如果某条边在最短路上，那么操作它一定不会让答案更优，所以实际上只会操作不在最短路上的和最短路尾端的边

H

给出两种线段组，求两种线段组中线段交的最大值

求线段交有很多种做法，这里给出最简单的一种

将线段按照右端点排序，从右到左扫描线段，维护已经扫描过的线段中，左端点的最小值，然后直接更新即可

只需要使用数组即可，不需要用到数据结构

A

构造一种排序方法，使得这个排序对给定 $0/1$ 串无效，但是对其余所有串都有效

让排序方法对某个串无效，只需要让其中某一对 $0/1$ 逆序关系即可

这里选择最靠左的一个 $1$ 和最靠右的一个 $0$，显然这两个更容易逆序

首先将所有 $1$ 和最右边的 $1$ 排序，然后将所有 $0$ 和最左边的 $0$ 排序，这样操作之后，除了给定串外，两个指定位置不可能逆序，所以对其余位置排序，只有给定串是有两个位置需要调整，其余串均只有一个，于是对两侧分别跑一下排序即可

L

给定一种三元组的变换方式，问经过多少次变换后可以得到原三元组，变换方式存在 $3$ 的循环节

只需要对每一元求出其在循环节中的位置，然后用中国剩余定理求出答案即可

注意对取模的合并要用到中国剩余定理

B

在一个凸多边形上找到三个点，使这三个点构成的三角形面积极大

固定一个点，找另外两个点使得面积极大

然后移动固定点，其余两个点也只能跟着移动，过程中更新答案即可

C

区间加 $x$，区间对大于等于 $k$ 的数减 $k$，问最终所有数一共减了多少次

维护每个位置当前的高度 $c_i$，每次让 $c_i+x$，或者 $c_i-k$，那么每个位置没有成功砍掉的次数和为 $\lceil-\frac{\min c_i}{k}\rceil$

结论题，然后只需要维护历史最小值即可

第二场

E

给定一个数 $x$，找到一个数 $y$ 使得 $y^2$ 是以 $x$ 开头的

转化为数学式子就是 $\lfloor \frac{y^2}{10^k} \rfloor=x$，这个式子有单调性，所以直接二分就行

I

构造一种五子棋的棋盘，使得双方只能平局

先用几个棋子构造出一种双方都赢不了的局面，然后把剩下的棋子填进去即可

F

二分图博弈，当且仅当所有的最大匹配都包含起点 $s$，先手必胜，否则后手必胜

判断是否所有的最大匹配都包含起点，可以先跑出一组最大匹配，再尝试增广一条路，来替代起点

C

给定一张图，每个点有点权 $0/1$，如果一条边对应两个点的点权相同，则不连边，否则连边，问新图中能否一定存在欧拉路，若能则给出构造

加强一下限制，因为欧拉路允许有两个点度数为奇数，所以这里把限制加强为存在欧拉回路，即所有点度数为偶数，这样就可以直接用高斯消元求解了

可以证明，一定有解

H

一个 $0/1$ 序列，$0$ 表示将给定的数 $x$ 各位 $0,1$ 互换，$1$ 表示让 $x=x+1$

可以发现 $0$ 操作其实就是在模意义下让 $x=-x$，于是直接用线段树维护即可

D

$n$ 个人吃菜，每个人对 $m$ 道菜的喜爱程度不同，一共只能点 $k$ 道，问如果每个人都希望自己最喜欢的菜上的最多，最后会得到什么样的结果

纳什博弈问题，每个人在当前轮点自己最喜欢吃的是不可行的，因为后面可能有人会点，所以就浪费了这样一次机会，于是倒着考虑就行

G

询问一个串 $S$ 是否由多个中心对称串拼接而成

回文自动机的匹配，每次删掉一个最小的回文后缀即可

注意一些细节，比如 $1$ 节点为奇根，$0$ 节点为偶根，所以 $lst$ 要先标记成偶根，以及清空的时候需要把 $0$ 位置上也清空

B

最大权闭合子图问题，用线段树优化即可，注意线段树上边压缩到点上时，需要考虑端点问题

A

给出一种神奇的 CRC 校验码计算方式，求一个字符串，使得校验码和这个字符串相同

由于后面的位会被前面的位影响，所以需要倒着考虑，这样就可以求出每一位翻转对最后答案的影响，然后直接做就可以了

J

给出 $F_0$ 以及递推式 $F_{i,j}=pA_{j-1}F_{i-1,j-1}+(1-p)(B_j+C_i)F_{i-1,j}$

求 $\sum_{j}F_{n,j}$

可以令 $F_{i,j}=A_{j-1}F_{i-1,j-1}+(B_j+C_i)F_{i-1,j}$

有 $F_{i,j}=A_{j-1}F_{i-1,j-1}+B_jF_{i-1,j}+C_iF_{i-1,j}$

$C_i$ 的作用是整体乘上某个定值，不会对 $F_{i,j}$ 之间的递推产生影响

然后不会了

L

给定矩形，构造外接菱形使其面积位矩形两倍，需要判断是否无解

首先一定有解

考虑如下构造，平移矩形的两条对角线，构成一个平行四边形，显然这个平行四边形的面积是举行的两倍，然后再旋转其中的一组边，使其成为菱形

M

$n$ 个点的有根树，每个点权为 $0/1$，支持两种操作

• 链点权赋值为 $0$ 或 $1$
• 查询子树内满足 $a_x,a_y,a_{lca(x,y)}$ 异或和为 $0$ 的点对数量

考虑在 lca 处统计答案，讨论 lca 处的权值，假设权值为 $0$ ，那么询问的是位于不同子树的点对中，权值不同的点对有多少个，利用容斥，可以用子树内所有权值不同的点对减去儿子节点中所有权值不同的点对

把式子写出来，会发现在如果父亲节点的值和儿子节点的值一样，那么该儿子节点的答案会被抵消掉，也就是说，一个值相同的连通块只需要计算连通块根节点的答案即可，并且还要提前给父亲的连通块答案减去当前连通块的答案，例如儿子值为 $0$ 的时候，父亲值一定为 $1$，要减去儿子子树中值为 $1$ 的答案

可以用树剖来维护这个过程

第三场

A

给定两个二进制非负整数 $x,y$，每次选定 $x$ 的某个数位 $b$，让 $x=x+b$ 或 $x=x-b$，问 $x=y$ 最少步数

简单分类讨论一下，$x=y$ 的时候答案为 $0$，否则 $x=0$ 答案为 $-1$ ，其余情况为 $|x-y|$，一定要注意，$x=y=0$ 不要被判断成 $-1$

D

给定一个 $0/1$ 矩阵 $A$，第 $i$ 行构成一个二进制数 $r_i$，第 $j$ 列构成一个二进制数 $c_j$，每次操作可以指定一行或者一列，使得 $0$ 变 $1$，$1$ 变 $0$，问最少操作次数使得 $\min r_i \ge \max{c_j}$ ，并问最小步数

诈骗题，当且仅当矩阵全为 $0$ 或 $1$ 的时候条件成立，判断翻转行还是翻转列，两个取最小答案即可

E

给定 $n$ 个点 $m$ 条边的有向图，判断以 $1$ 为根的所有 dfs 树是不是都为以 $1$ 为根的最短路树

通过 bfs 建立分层图，考虑一条边 $u->v$ ，如果 $v$ 处于 $u$ 的下一层，如果在同一层，那么一定会出错，因为到达 $u$ 之后可以立即到 $v$ 使得 $v$ 的答案出错，如果 $v$ 处于 $u$ 上面的层，那么要求 $v$ 必须是 $u$ 的支配点，这样经过 $v$ 之前必须先经过 $u$

F

给定两个非负的十进制整数，$x,y$

每次操作选定 $x$ 的某个数位 $b$ ，令 $x=x-b$ 或者 $x=x+b$ ，问最少操作次数使得 $x=y$

多组询问，强制在线

如果数字范围比较小，那么可以进行暴力最短路

考虑进行分治，每次取出区间中间一段长度为 $9$ 的区间，因为每次操作变化的范围不可能超过 $9$，做一个类似线段树的东西，对每个结点求出到中间区间的正距离和反距离

现在考虑查询，因为 $[x,y]$ 变化的时候可能并不是在这个区间中的，所以假设它变化的上下界是 $[l,r]$，一定有 $l\le x$ 且 $y\le r$，那么我们在线段树结点从上到下去考虑，一定存在一个区间，使得 $[x,y]$ 经过了这个区间的中间

G

给定一个矩阵，求有多少个中心对称的矩阵

显然可以对于每个点二分哈希

考虑不进行二分，使用Manacher算法，枚举中心对称的行，然后将扩展的条件改为判断矩阵对称即可

I

给定一棵树，每个结点都有一个颜色集合，可以在某个点切换颜色，每次询问能否在一条路径上从 $x$ 走到 $y$，可以走的条件为当前颜色在 $y$ 的颜色集合中

考虑一个贪心，一定是一直走，直到不能走为止才会换颜色，所以可以倍增维护这个信息，有一些细节，比较难写

J

给定若干组大小关系，要求构造若干个赋值，使得每个大小关系至少在一个赋值中成立

构造方式比较多，首先容易使用拓扑排序来判断是否为有向无环图

否则只需要两个序列即可

最简单的方式是构造一个 $1-n$ 的排列和一个 $n-1$ 的排列

我的方式是sb的 dfs 树，树边和返祖边构成两个序列

第四场

杭电多校