2022级5月测试题解

特别感谢华北理工大学、黄冈师范学院、鲁东大学、曲阜师范大学、沈阳化工大学、石家庄铁道大学、中北大学ACM集训队负责人的大力支持。

A 关灯

Tag: 贪心

把 $00$ 变成 $11$ 一定不会让答案变优，因此每次操作只会关掉不超过 $kk$ 个连续的 $11$。

对于每段连续的 $11$ 看看需要几次关掉，最后求和即可。

时间复杂度 $O(n)O(n)$。

B 动物园

Tag: 双指针

如果已知 $x_l\dots x_{r}x\_l\backslash dots\; x\_r$ 内的种类数，当 $r\to r+1r\; \backslash rightarrow\; r+1$ 或 $l\to l+1l\; \backslash rightarrow\; l\; +\; 1$ 时可以通过 $O(1)O(1)$ 的时间得到新区间的种类数。因此考虑双指针。

时间复杂度 $O(n)O(n)$。

当然也存在队列的做法。

C 奏绝

Tag: 差分/推式子

解法一：差分

计算区间所有贡献的和，一个很自然的想法是线段树维护区间贡献，每个区间记录该区间内黑白之章往前后的长度和与数量，两个区间合并，跨越区间的贡献即为将某一区间的黑白之章长度和乘另一区间的相反颜色的数量

区间前后缀长度和，区间某种元素的数量，答案的贡献均满足可减性，可以通过差分 $O(1)O(1)$ 得出，于是可以利用差分将复杂度优化到 $O(n)O(n)$

本题本来就开了 1s 卡线段树的，zrzring 于心不忍，于是把时间开到了 3s 放了线段树

解法二：推式子

对于给定的任意 $l,r(l\le r)l,\; r(l\; \backslash leq\; r\; )$，不妨仅考虑右端点为 $11$ 的情况，设 $f(i)f(i)$ 表示位置 $ll$ 到 $ii$ 对答案的贡献。

设函数 $g_0(l,i)g\_0(l,i\; )$ 为 $l-il-i$ 内 $00$ 的下标和， $g_1(l,i)g\_1(l,i\; )$ 为 $l-il-i$ 内 $11$ 的下标和。

设函数 $h_0(l,i)h\_0(l,\; i)$ 为 $l-il-i$ 内 $00$ 的个数， $h_{1}1(l,i)h\_11(l,\; i)$ 为 $l-il-i$ 内 $11$ 的个数。

$[s_j==0][s\_j==0]$ 为艾弗森括号，如果方括号内的条件满足则为 $11$，不满足则为 $00$。

$f(i)=\sum _{j=l}^i[s_j==0](i-j)=i\ast \sum _{j=l}^i[s_j==0]-\sum _{j=l}^i[s_j==0]j=i\ast h_0(l,i)-\sum _{j=l}^i[s_j==0]j=i\ast h_0(l,i)-g_0(l,i)f(i)\; =\; \backslash sum\_\{j\; =\; l\}\; ^\; i\; [s\_j\; ==\; 0](i\; -\; j)\; \backslash \backslash \; =\; i*\; \backslash sum\_\{j\; =\; l\}\; ^\; i\; [s\_j\; ==\; 0]-\; \backslash sum\_\{j\; =\; l\}\; ^\; i\; [s\_j\; ==\; 0]\; j\; \backslash \backslash \; =\; i*h\_0(l,i)-\backslash sum\_\{j\; =\; l\}\; ^\; i\; [s\_j\; ==\; 0]\; j\; \backslash \backslash \; =\; i*h\_0(l,i)-\; g\_0(l,\; i)$

那么区间 $l,rl,r$ 的答案

$ans=\sum _{i=l}^r[s_i==1]f(i)=\sum _{i=l}^r[s_i==1](i\ast h_0(l,i)-g_0(l,i))=\sum _{i=l}^r[s_i==1]i\ast h_0(l,i)-\sum _{i=l}^r[s_i==1]g_0(l,i)=\sum _{i=l}^r[s_i==1]i\ast (h_0(1,i)-h_0(1,l-1))-\sum _{i=l}^r[s_i==1](g_0(1,i)-g_0(1,l-1))=\sum _{i=l}^r[s_i==1]i\ast h_0(1,i)-\sum _{i=l}^r[s_i==1]i\ast h_0(1,l-1))-\sum _{i=l}^r[s_i==1]g_0(1,i)+\sum _{i=l}^r[s_i==1]g_0(1,l-1)=\sum _{i=l}^r[s_i==1]i\ast h_0(1,i)-h_0(1,l-1)\ast g_1(l,r)-\sum _{i=l}^r[s_i==1]g_0(1,i)+h_1(l,r)g_0(1,l-1)ans\; =\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]f(i)\; \backslash \backslash \; =\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1](i*h\_0(l,i)-\; g\_0(l,\; i))\; \backslash \backslash \; =\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]i*h\_0(l,i)-\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]g\_0(l,i)\backslash \backslash \; =\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]i*(h\_0(1,i)\; -\; h\_0(1,l-1))\; -\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1](g\_0(1,i)-g\_0(1,l-1))\backslash \backslash \; =\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]i*h\_0(1,i)-\backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]i*\; h\_0(1,l-1))\; -\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]g\_0(1,i)\; +\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]\; g\_0(1,l-1)\backslash \backslash \; =\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]i*h\_0(1,i)-h\_0(1,l-1)*g\_1(l,r)\; -\; \backslash sum\_\{i\; =\; l\}\; ^\; r\; [s\_i\; ==\; 1]g\_0(1,i)\; +\; h\_1(l,r)g\_0(1,l-1)\backslash \backslash$

预处理 $44$ 个数组：

• $h[i][p]h[i][p]$ 表示 $1\dots i1\; \backslash dots\; i$ 内 $pp$ 出现的次数
• $g[i][p]g[i][p]$ 表示 $1\dots i1\; \backslash dots\; i$ 内 $pp$ 出现时的下标和
• $sumh[i][p]={\sum }_{j=1}^n[s_j=p]\ast j\ast h_{p\widehat{}1}(1,j)sumh[i][p]\; =\; \backslash sum\_\{j=1\}^n[s\_j=p]*j*h\_\{p\; \backslash hat\{\; \}\; 1\}(1,j)$
• $sumg[i][p]={\sum }_{j=1}^n[s_j=p]\ast j\ast g_{p\widehat{}1}(1,j)sumg[i][p]\; =\; \backslash sum\_\{j=1\}^n[s\_j=p]*j*g\_\{p\; \backslash hat\{\; \}\; 1\}(1,j)$

因此最后答案为

$ans=(sumh[r][1]-sumh[l-1][1])-h[l-1][0]\ast (g[r][1]-g[l-1][1])-(sumg[r][1]-sumg[l-1][1])+(h[r][1]-h[l-1][1])\ast g[l-1][0]ans=\; (sumh[r][1]\; -\; sumh[l\; -\; 1][1])-h[l-1][0]*(g[r][1]-g[l-1][1])\; -\; (sumg[r][1]-sumg[l-1][1])+\; (h[r][1]-h[l-1][1])*g[l-1][0]$

单次询问可以 $O(1)O(1)$ 得到答案，因此总复杂度 $O(n+m)O(n+m)$

D 崩坏

Tag: BFS

首先需要bfs求出每个单元格会在何时变为崩坏点，之后再次bfs求出人在逃向终点的途中到达每个能到达的单元格（即为 $00$ 的单元格）的最小时间，与常规迷宫问题相比，其中能否经过该单元格的额外判定条件为：人到达此单元格的最短时间是否比该点变为崩坏点的时间小，小则能够经过，反之不能。

E 下棋

Tag: 贪心

独立的考虑每一个棋子，肯定是能走的时候一定会走，如果说这一步别的棋子走了导致自己不能走了，那就等一会走

贪心，这样一来答案就是每个棋子到 1 号点的距离加上等待的时间，在所有棋子里取最大值

考虑如何计算每个棋子需要等待的时间，这个过程比较困难，如果我们用全局的角度考虑，可以得出一些结论

一个棋子肯定会在某个时刻进入一个连通块，连通块里的所有棋子会连续不断的进入 1 号点，并且连通块会在某些点进行合并，一个连通块的贡献为该连通块首次有棋子进入 1 号点的某个儿子的时刻，加上整个连通块的点的数量

这样的话可以考虑全局瓶颈，因为是能走就走，根据已经推出来的结论，如果我们钦定深度最深的棋子畅通无阻，那么全局的瓶颈肯定是深度最深的棋子所在的连通块

因为 1 号点的特殊性，我们取所有 1 号点的儿子为关键节点，答案是所有关键节点的贡献的最大值

而关键节点的贡献就是，每个节点子树内深度最深的棋子到该关键点的距离加上该棋子所带领的连通块点的数量

由已推出的结论可得这样是正确的，那么这个连通块的点的数量怎么计算呢

首先深度最深的棋子是畅通无阻的，也就是说我们只有该点深度的时间去把别的棋子移到 1 号点使得它不会堵住深度最深的那个点

要考虑整个过程有那些点不属于深度最深的棋子的连通块貌似有点困难，但是时间戳和点是一一对应的，所以我们考虑哪些时间戳会有点出去就好了

于是 $O(n)O(n)$ 的复杂度通过此题

思路 1

贪心，能移动一定会移动

考虑对于 1 号点的每个儿子为根的子树进行考虑，显然次数的瓶颈在于深度最深的点，那么先让一个深度最深的点一直移动直到进入 1 号点，之后每个时刻都会有点进入 1 号点了

于是计算一下最深的深度 $dd$，子树内点的数量 $cc$，然后让某一个深度最深棋子畅通无阻得移动到 1 号点，计算这段时间内有棋子出去的时间戳数量，记为 $aa$，一棵子树的贡献就是 $d+c-ad\; +\; c\; -\; a$

然后对 1 号点的所有子树贡献取一个 $\max \backslash max$ 即可，std 使用的是该思路

思路 2

记深度 $\ge i\backslash geq\; i$ 的棋子个数为 $cn{t}_{i}cnt\_i$，深度 $ii$ 的贡献为 $cn{t}_i+i-1cnt\_i\; +\; i\; -\; 1$，对所有深度求最大值即可

依旧是对 1 号点每个子树单独跑一边取最大值

题外话 - 动态维护

我们现在换个情景，我们设棋子一旦开始走就不能停，且1号点只有一个儿子，并且支持修改，支持加入一个棋子，删除一个棋子

为了动态维护，这个题的做法基于上述思路就产生了不一样的解释方法

考虑每个棋子所在节点的深度 $d_{i}d\_i$，每只棋子钦定一个 $\le d_i\backslash leq\; d\_i$ 的到达时刻，并且没有两只棋子的到达时刻相等

记深度为 $ii$ 的棋子个数为 $cn{t}_{i}cnt\_i$，从小到大枚举 $ii$，先往栈里加入 $cn{t}_{i}cnt\_i$ 个棋子，如果栈非空就从栈中弹出一个棋子

可以考虑用线段树维护 $an{s}_{i}ans\_i$ 表示考虑时刻 $ii$ 后还剩多少棋子，线段树二分查找某个位置后第一次出现连续两个 $00$ 的位置和某个位置后第一个 $00$ 即可

F Put numbers first

Tag: 数论

由于 $\gcd (i,i+1)=1\backslash gcd(i,\; i\; +\; 1)\; =\; 1$，因此一种构造方式为让周围的四个数为 $A_{i,j}\pm 1A\_\{i,j\}\; \backslash pm\; 1$。

考虑对行号分奇偶讨论，对于奇数行输出 $1,2,3,\dots ,n1,2,3,\backslash dots,n$，对于偶数行输出 $2,3,\dots ,n,12,3,\backslash dots,n,1$。

时间复杂度 $O(T{n}^2)O(Tn^2)$。

G 三位出题人

Tag: 数学

如果我们画一张 $3\times n3\backslash times\; n$ 的表，会发现题目要求等价于，在这张表每个位置填 0 或 1，需要满足每列都不全是 0 且都不全是 1，有 $66$ 放法$(2^3-2)(2^3-2)$，每列相互独立，于是答案为 $6^{n}6^n$。

zrzring 想出有 $kk$ 个出题人的，被 s7win99 制止了，于是就有了这道小清新签到题（实际上 $kk$ 个也一样，就是看起来会难一些）。

H 树和路径

Tag: LCA，树形DP

码农题，估计赛时只有巨佬才会开这个题吧，我自己写都要写超过 5 个小时了

记 $xx$ 子树内最长链中 $xx$ 在原树上的儿子为 $xx$ 的重儿子

对于每个询问 $x,yx,y$ 有两种情况，设 $xx$ 的深度小于 $yy$：

• $lca(x,y)≠xlca(x,y)\backslash not\; =\; x$，答案就是 $xx$ 和 $yy$ 之间的距离，加上 $xx$ 子树内的最长链和 $yy$ 子树内的最长链的长度
• $lca(x,y)=xlca(x,y)\; =\; x$，我们判断一下 $yy$ 是否在 $xx$ 子树内的最长链上，如果是的话需要在 $xx$ 除去重儿子的子树内的最长链，否则找到 $xx$ 子树外的最长链即可

I 猫狗争霸赛

Tag: 贪心/二分

解法一：贪心

贪心，因为队伍最多可以有 $(n+m)\mathrm{/}3(n\; +\; m)/3$ 支，但又要保证每个队伍里至少有一只小猫和一只小狗，则答案为 $(n+m)\mathrm{/}3\mathrm{、}n\mathrm{、}m(n+m)/3、n、m$ 三者取最小值即可。

解法二：二分

不难发现这个问题的答案是有单调性的，因此我们可以直接二分能组成的队伍数量，$checkcheck$ 也很简单，即若能组成 $xx$ 支队伍则至少有 $xx$ 只小猫和 $xx$ 只小狗且除去这些小猫和小狗剩下的小猫和小狗的总数也不能少于 $xx$ 只。

J 神罚

Tag: 数论

当 $n=1n\; =\; 1$ ，即该数只有一位时，该数为 $xx$，直接判断 $xx$ 是否为质数即可，当 $n>1n\; >\; 1$ 时，我们无法确定任何情况下的该数一定为质数，但是可以得知偶数一定合数，且位数大于 $11$ 的个位为 $55$ 的数也一定为合数，至此即可得出结论。

K 雁队

Tag:思维

对原序列差分出来，把区间修改变成单点修改，一字型可以直接得出答案，人字形枚举一个最高点即可

L 关灯

Tag: 二分

如果把 $11$ 和后面的 $00$ 当成一个块，那么每个块的长度呈等差数列，前 $kk$ 个块的长度总和为 $\frac{k(k+3)}{2}\backslash frac\{k(k\; +\; 3)\}\{2\}$。

同时注意到 $11$ 始终为块首元素，因此只需要找不超过 $xx$ 的最大的 $\frac{k(k+3)}{2}\backslash frac\{k(k\; +\; 3)\}\{2\}$。然后判断一下 $x-\frac{k(k+3)}{2}x-\backslash frac\{k(k\; +\; 3)\}\{2\}$ 是否等于 $11$。

由于 $\frac{k(k+3)}{2}=x\backslash frac\{k(k\; +\; 3)\}\{2\}\; =\; x$，那么 $k=O(\sqrt{x})k\; =\; O(\backslash sqrt\{x\})$，可以二分找 $kk$，二分的右边界应取 $r=\sqrt{2x}r=\backslash sqrt\{2x\}$ 或 $r=2e9r=2e9$。

一次时间复杂度为 $O(\log \sqrt{x})O(\backslash log\backslash sqrt\{x\})$，因此总时间复杂度 $O(T\log 10^9)O(T\backslash log10^\{9\})$。

如果该题仍然超时，可以考虑使用 scanf 读入或关掉同步，并且将 endl 换成 \n。（这个细节在比赛说明里的选手须知有提到）.