2023 暑假牛客多校

Semorius / 2023-07-22 / 原文

时隔一年，多校又至。还是和jimmywang与shihoghmean组队。只可惜后面要文化课了，可能打不完。

只记一些赛时想过的和听完题解后会的妙妙题：

7.17

“范式杯”2023牛客暑期多校训练营1

D

题意：\(n \times m\) 的巧克力， Kelin 先手 Walk Alone 后手拿走一块矩形的巧克力，谁拿走 \((n, m)\) 处的巧克力谁输，问结果。

数据范围：\(1 \le n, m \le 10^9\)。

结论题，只有 \(1 \times 1\) 的时候 Walk Alone 会赢，其余情况均是 Kelin 赢。

K

题意：给定一个无向图 \(G(n, m)\)，可以将其中任意一条边分裂成一条长度为任意的链（向边中插任意多个点），可以操作任意多次（也可以不操作）。问经过这样处理之后，从 \(1\) 号节点出发，至多走 \(k\) 步最多可以到多少个节点。

数据范围： \(1 \le n \le 10^5， 1 \le m \le 200000， 1 \le k \le 10^9\)。

先考虑求 \(1\) 到每个节点的最短路，可以用 \(\text{dijkstra}\) 或 \(01\)-\(\text{bfs}\) 解决。发现所有最短路形成的是一棵搜索树。如果在树边上插点会影响很多点到 \(1\) 的最短路，而在非树边上插点不影响 \(1\) 到任意一个点的最短路，所以考虑在非树边上插点。一条非树边上的新插点可以通过该边两端点到 \(1\) 的最短路来到 \(1\)。记点 \(x\) 到 \(1\) 的最短路长为 \(d_x\)，则一条非树边 \((x,y)\) 的贡献为 \(2K-d_x-d_y\)。还有每个不连接非树边的叶子节点贡献为 \(K-d_x\)。注意 \(1\) 所在连通块没有边的情况。

H

题意：给定两个长度为 \(n\) 的序列 \(\{a\}^n_{i=1}\) 和 \(\{b\}^n_{i=1}\)，现在可以选择其中一个序列交换其中的两个数字，问经过至多一次操作后最小的 \(\sum_{i=1}^{n}|a_i-b_i|\)。

数据范围：\(1 \le n \le 200000， 0 \le |a_i|, |b_i| \le 10^{12}\)。

分四类讨论，二分解决。原题 CF1513F

7.21

2023牛客暑期多校训练营2

K

题意：给出一个长度为 \(n\) 的 \(01\) 串以及每个位置都有权值 \(a_i \ge 0\)。每个 \(1\) 最多移动一次且最多移动一位。若一个位置有 \(1\) 则可以获得权值。问最大可能的权值和。\(n \le 10^6\)。

一开始贪心了半天写的巨长。发现是easy \(\text{dp}\) 题。

设 \(dp_{i,0/1/2}\) 表示枚举到第 \(i\) 位，这一位不动，有 \(1\) 的话前移或后移产生的最大贡献。

答案即为 \(\max(dp_{n,0},dp_{n,1})\)。

H

题意：给定一个长为 \(n\) 的只含 \(\text{A,B}\) 两种字符的字符串。给定 \(Q\) 次询问 \((l, r, x)\) 表示二进制字符串 \(x\) 经过字符串 \((l, r)\) 这段区间后变成什么。之中，\(\text{A}\) 操作反转该二进制字符串（\(0,1\) 互换），\(\text{B}\) 操作将该二进制字符串视为数字计算 \(x \gets x + 1\)（溢出的位舍弃）。数据范围都在 \(2 \times 10^5\) 级别，且询问要求强制在线。