2021-2022 BUAA XCPC Team Supplementary Training 03¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 3/20 | 8 | 12 | 12 |
B¶
solved by 2sozx Bazoka13
题意¶
给定一个二分图 \(A, B\)，集合大小分别为 \(n, m\)，每个点有权值，一个点集使可以被选择当且仅当在原图中存在一个匹配，使得选择的点集中的所有点都是这个匹配的端点，并且点集的权值和大于 \(t\)。问有多少种选择点集的方式。\(1\le n, m\le 20, t\le 10^9\)
题解¶
根据 Hall 定理，我们可以分别预处理出来 \(A,B\) 的子集使得其能成为一个匹配的端点，并且预处理出来每个子集的权值和。
如果子集 \(S_A,S_B\) 分别是 \(A,B\) 中的可行子集，那么 \(S_A \cup S_B\) 一定是原图中可以被选择的子集。证明放在最后。因此我们可以将所有 \(B\) 的可行子集按权值和大小排序，对于每个 \(A\) 的可行子集二分查找即可，注意此题选择可以为空际。
简略证明：
考虑 \(A\) 的可行子集，\(B\) 同理。
对于一个可行子集 \(S\) ，所对应的 \(B\) 中子集为 \(T\) ，我们可以知道对于此时的 \(S\) 以及原图的任意一个匹配包含 \(S\) ，则 \(S\) 所连的点一定包含了一个必选子集 \(H\)，而且我们可以推断出与 \(H\) 所连的点集 \(G\)。从 \(S,T\) 中刨除 \(G, H\) 得到 \(S^{'}, T^{'}\) 。如果 \(T^{'}\) 在 \(S^{'}\) 中还有必选子集 \(H^{'}\) ，我们进行讨论。
- 如果 \(H^{'} \cap G = \varnothing\) 显然把这个删除，剩余的在原图中一定可以找到一个匹配
- 否则设 \(H^{'}\cap G = I\)，我们会发现 \(I\) 对应了一个原来在 \(S\) 中必选的 \(H\) 以及非必选的 \(H^{'}\) 且 \(H\cap H^{'} = \varnothing\) ，这样根据我们对于必选的定义，会发现原先的选择 \(G\) 并非必选，与假设矛盾，因此不存在这样的情况。
证毕。
D¶
upsolved by 2sozx JJLeo
题意¶
\(6\times 6\) 的矩阵，\((1, 1)\) 开始存有 \(n\) 个无序的数，按照堆排列，并且没有相等的元素。每次操作可以选择一个位置 \((x, y)\) ，从顶部取走连续的一段放入 \((x+1, y)\) 或者 \((x, y+1)\) 的栈顶，问一种操作方式使得最终到达 \((6, 6)\) 的时候从栈底到栈顶是递增数列。(\(1 \le n \le 40000\))
题解¶
我们考虑简单的情况。\((1,1)\) 只可以排好一个数， \((1, 2),(2,1)\) 的位置最多可以将两个数排成递增或递减数列，而对于其余的 \((x,y)\) 会发现将 \(1 \le i \le x, 1\le j \le y\) 其与所有位置 \((i, j)\) 按照能排列好的数最多去放置，这样对于到 \((x, y)\) 的排序方法即为多路归并排序，因此我们可以知道每个 \((x, y)\) 最多能排好多少个数。
递推式为 \(f(x,y) = \sum \limits _{i=1}^x \sum \limits _{j=1}^y[i \ne x \lor j \ne y]f(i,j)\)，特别地 \(f(1,1)=1,f(1,2)=f(2,1)=2\)。
\(f(6,6)=42960\)。
对于将初始状态排序好，可以从 \((6, 6)\) 开始贪心的排序，尽量将其余的状态放满数即可。由于这个排序每次会将原来的顺序取反，因此递归时需要考虑此时需要递增数列还是递减数列。
对于 \((1, 2),(2, 1)\) 位置且要放置 \(2\) 个数时我们需要特判，因为这两个数都是从 \((1, 1)\) 转移过来，但是是要进行两次操作的，因此与其余方式不同。
递归可以写成 vector<int> solve(int i, int j, int n, bool d) 的形式，表示需要在 \((i,j)\) 这个位置上面出现 \(n\) 个升序 / 降序的数 (和 \(d\) 有关)，返回这些数组成的 vector<int>。
E¶
solved by JJLeo Bazoka13
题意¶
找到 \(n\) 个满足 \(a^2 + b^2 + c^2 = k(ab + ac + bc) + 1\) 的三元组 \((a, b, c)\) ，并且方案中 \(a, b, c\) 最多只出现一次，答案每个数位数不超过 \(100\)。 \(n, k\le 1000\)
题解¶
找到一组初始解 \(a = 1, b = k, c = k + k ^ 2\) ，考虑固定两个数，我们可以得到一个方程组。
两式相减化简可得
由于 \(a_1 \not = a_2\) ，则有 \(a_2 = k(b + c) - a_1\) ，根据特解寻找即可。
G¶
upsolved by JJLeo Bazoka13 2sozx?
题意¶
\(2^n \times 2^n\) 的网格图，每个位置上数字都不同，范围是 \(\left[0,2^{2n}\right)\)。递归地给每个格子标号，从高到底依次确定二进制下每一位：
- 首先把当前区域竖直地分成面积相等的两半，\(x\) 坐标大的那一侧这一位是 \(1\)，\(x\) 坐标小的那一侧这一位是 \(0\)。
- 再把当前区域水平地分成面积相等的两半，\(y\) 坐标大的那一侧下一位是 \(1\)，\(y\) 坐标小的那一侧下一位是 \(0\)。
- 这样就确定了两位，把当前区域分为了四个面积一样的区域，继续递归这四个部分，确定每部分更低的位。
一共递归进行 \(n\) 轮，这样 \(2n\) 位上的数字都确定了。
现在给出一个 \(m\) 个顶点的简单多边形，保证所有边都是竖直或者水平的且贴着格子边界，设这个多边形内部包含的数字组成集合是 \(S\)。
现在有 \(q\) 组询问，每次给定一个值 \(k\)，你需要选择至多 \(k\) 个区间，设使得这些区间的并是 \(T\)，要求 \(S \subseteq T\)，最小化所选区间的长度之和。
(\(1 \le n \le 30\)，\(4 \le m \le 200\)，\(1 \le q \le 10^5\)，\(1 \le k \le 10^9\))
题解¶
首先，假设我们求出了多边形内部包含的的数，把他放到数轴上，如果 \(k=1\)，答案就是最大值减去最小值；否则，其内部一定有很多空隙，\(k\) 每增大 \(1\)，就可以去掉一个空隙，因此只需减去最大的 \(k-1\) 个空隙即可。
我们考虑如何求出这些空隙。
一个最暴力的做法就是模拟上述递归过程，假设此时值域是 \([l,r]\)，令 \(\textit{mid}=\left\lfloor\dfrac{l+r}{2}\right\rfloor\)，那我们这里计算所有跨过 \(\textit{mid}\) 的空隙，递归求出 \([l,\textit{mid}]\) 以及 \([\textit{mid}+1,r]\) 中在多边形内的最小 / 大值，这样后者最小值减去前者最大值就是空隙大小了，同时前者最小值和后者最大值就是 \([l,r]\) 中在多边形内的最小 / 大值。
注意两个子区间得有数才能算空隙，不然显然不是内部的空隙。
这样的确可以算出所有空隙，但是复杂度裂了，考虑利用这个多边形的特点 ：所有边都是竖直或者水平的。可以证明，对于这样一个 \(m\) 个点的多边形，用大小相同的瓷砖铺满整个平面，那么对于本质不同的瓷砖的多边形经过该瓷砖的方案是 \(O(m)\) 的：
（图片摘自官方题解）
考虑将所有顶点在的瓷砖标红，其周围四个瓷砖标蓝，那么所有白色瓷砖一定和某一个蓝色瓷砖的方案是相同的。
因此，我们在递归的时候，如果左右两个区域是本质相同的，也就是只有当前考虑的这一位是不同的，那么我们可以只递归一侧，并将其中的空隙数量都 \(\times 2\)，这可以通过传入一个参数，算空隙的时候乘以这个参数即可，那么每一次只递归一侧就要将其 \(\times 2\)。
考虑如何判断两个区域是本质相同，以当前是竖着切为例：
- 如果当前区域被水平的多边形边界通过，不影响两边的相同性。
- 如果当前区域被竖直的多边形边界通过，两边必然不同。
- 如果当前有顶点严格在当前区域内部，两边必然不同。
横着切同理，我们可以 \(O(m)\) 判断上述内容。
最后，递归的终点，只有一个格子的情况，我们同样可以用射线法 \(O(m)\) 判断其是否在多边形内部，因为所有边都是水平或竖直，可以从中心竖直向上射出一条射线，然后判断和多少条水平的边相交，奇内偶外。
递归过程中如果继续递归两侧说明两边不同，一共有 \(O(n)\) 种分割，由证明易得这种情况最多出现 \(O(nm)\) 次。每出现一次这种情况最多递归 \(O(n)\) 层，每层都需要 \(O(m)\) 判断，因此复杂度为 \(O(n^2m^2)\)。
但是题解写复杂度是 \(O(nm^3)\)，同时 cf 上也有👴提出是 \(O(n^2m^3)\) 的，不懂，求带。
最后将所有空隙按大小后排序，lower_bound 即可，询问复杂度为 \(O(q \log nm)\)。
I¶
upsolved by Bazoka13 JJLeo
题意¶
一个由 \(1\) 到 \(9\) 组成的未知串，现在有这个串生成了 \(n\) 个提示，每个提示按如下规则生成：
- 随机选一个位置。
- 随机往左或往右确定一个方向。
- 初始这个提示 \(h\) 是空的序列，从这个位置一直走到尽头，每次遇到一个 \(h\) 中没有的数，就将其加入到 \(h\) 的末尾。
给出这 \(n\) 个提示，问原串最短能是多少，或判断无解。(\(1 \le n \le 10\))
题解¶
先考虑往右的提示，设提示开始的位置是 \(x_1\le x_2 \le \cdots \le x_m\)，那么对于 \(x_i\) 位置开始的提示，一定是进行到某个位置时 (当然也可能是所有数字都经过了后)，它可以直接被 \(x_{i+1}\) 位置开始的提示所取代，也就是说后面只要满足 \(x_{i+1}\) 就能满足 \(x_i\)，否则 \(x_{i+1}\) 及之后的提示永远都开始不了。
我们考虑处理出 \(t_{i,j,k}\) 表示第 \(i\) 个提示前 \(k\) 个位置都对应上了，现在能否被第 \(j\) 个提示所取代。\(t_{i,j,k}\) 为真当且仅当：
- 第 \(j\) 个提示的数字全在第 \(i\) 个提示中出现过，因为第 \(i\) 个提示开始位置在第 \(j\) 个位置之前。
- 第 \(i\) 个提示从 \(k+1\) 个位置开始的数字，要以同样的顺序出现在第 \(j\) 个提示中，否则显然不成立了。
我们再来考虑往左的提示，我们考虑上述过程的逆过程。首先因为 dp 过程是不断向右加数，因此对于每个提示要从后往前填充，当一个提示 \(j\) 走到头时，反过来考虑可以发现此时它是刚开始的，考虑它能否是取代了到了第 \(k\) 个位置的第 \(i\) 个提示，只需看 \(t_{i,j,k}\) 是否为真。如果可以就可以转为第 \(i\) 个提示第 \(k\) 个位置，并继续倒着匹配。
另外还需预处理出 \(L_{i,j}\) 和 \(R_{i,j}\) 分别表示当前向左 / 右的是第 \(i\) 个提示，能否放第 \(j\) 个数，这些都可以根据定义很容易求出。
最后进行 dp，设 \(f_{S,l,i,r,j}\) 表示当前已经完事了的提示集合 \(S\)，当前向左的提示 \(l\)，从后向前匹配到了位置 \(i\)，当前向右的提示 \(r\)，从前向后匹配到了位置 \(j\)。设第 \(i\) 个提示的长度为 \(\operatorname{len}(i)\)，有以下三个转移：
- 如果 \(i=1\) 说明 \(l\) 走到头了，可以枚举下一个向左的提示及位置，利用 \(t\) 数组即可；也可以让其作为最后一个靠左的提示，之后都不能选择向左的提示了，可以将 \(l\) 设置为一个特值 \(V\)。
- 如果 \(j=\operatorname{len}(r)\)，说明 \(r\) 走到头了，可以枚举下一个向右的提示，利用 \(t\) 数组即可。
- 新增一个数，根据 \(L\) 和 \(R\) 数组判断是否合法，如果和向右的提示下一位相同，则必须匹配；如果和向左的提示下一位相同，则可匹配可不匹配。
最终的合法状态为选择完了所有的提示，且 \(l=V\)。此外，如果有向右的提示则要求 \(j=\operatorname{len}(r)\) 且 \(S\) 加上 \(j\) 是全集；如果没有向右的提示则要求 \(S\) 就是全集。
因为可以没有向右的提示，初始状态的 \(r\) 也可以用一个特值 \(V\) 来代替，其转移时不要用 \(t\) 数组，直接特判。
使用记忆化搜索，复杂度真是 \(O(\)能过\()\)，上界根本不可信，因为光是状态数乘上转移的复杂度就已经裂了，可见有效状态很少。
J¶
upsolved by JJLeo 2sozx
题意¶
给定一个长度为 \(n\) 的 \(01\) 串，有以下四种操作：
- 删掉一个 \(0\)，花费 \(o_0\)。
- 删掉一个 \(1\)，花费 \(o_1\)。
- 删掉一个 \(0\) 和 \(1\)，要求 \(0\) 在 \(1\) 前头，不要求两者挨着，花费 \(r_0\)。
- 删掉一个 \(0\) 和 \(1\)，要求 \(0\) 在 \(1\) 后头，不要求两者挨着，花费 \(r_1\)。
求把所有数删掉的最小代价。(\(1 \le n \le 10^5\))
题解¶
现用 \(o_0+o_1\) 去最小化 \(r_0\) 和 \(r_1\)， \(r_0\) 和 \(r_1\) 哪个小就贪心把能选的都选了，再选另一个，最后只剩一种数了就单个选即可。
L¶
solved by Bazoka13
题意¶
给定三组 \(n\) 个布尔变量的取值，保证互不完全相同，构造一个 2-SAT，使得这三组解恰为全部的解，或判断无解。
题解¶
如果有一个变量全是一个值，那么直接让 \(x \to \neg x\) 或 \(\neg x \to x\)。
剩下 \(6\) 种可能的情况有两两一对，可以让其中等于另一个的反，即 \(x \to \neg y \land y \to \neg x\)。
剩下就三种情况了，如果就剩一个了，说明有两组解一模一样，不可能。
如果就剩两个，即两个变量有四种情况其中一种不行，这可以通过一个 \(\to\) 把那种封掉。
如果剩三个，由样例可得 寄了，八种情况封掉五个是不可行的，可以打表证明。
记录¶
0h：MJX网炸了，调了10min的网，导致开始没看到A的大签到，CSK开C大签到，ZYF冲A大模拟，直接一血(校内)，F过的多看F，很sb，ZYF开冲。CSK推完式子冲C，寄了，MJX和ZYF讨论K，发现也是个签到，直接开冲。
1h：ZYF过了，MJX帮着找C的问题，挑了俩bug改完过了。CSK找了个E的递推方式，ZYF直接冲java。MJX看H，很眼熟，想了想直接喂ZYF了
2h：ZYF过了，一起去看B，CSK看L，喂给MJX，MJX没听明白。喂给ZYF，ZYF好像也没明白，CSK自己去优化算法了。
3h：CSK把L乱冲过了，MJX想了个J的大概应该是正解的做法，喂给了ZYF，ZYF直接开冲。
4h：J出bug了，MJX看B，看了看样例解释，发现题nm读错了，sb题直接读成了不可做题，CSK给了个复杂度巨优的算法，MJX直接开冲。然后没开ll，还有奇怪的return，4:58几乎卡时过的。
总结¶
Dirt¶
B(+2):没开long long ,MJX多扔了个0，不应该直接return
C(+3):CSK少考虑了几种情况