题解 | #2022河南萌新联赛第（四）场：郑州轻工业大学 题解#

A_ZZULI

这道题由于要计算连通块大小，可以使用并查集，关键在于如何去合并。
对于 $a,b,c\{a,b,c\}$ ，$(a,b)(a,b)$ 合并后 $(b,c)(b,c)$ 合并，与 $(a,b)(a,b)$ 合并再 $(a,c)(a,c)$ 合并是没有区别的，那么要合并的一组数就用第一个去合并一遍。
所以拿第一个 Z 向后合并一遍，遇见 Z 、U、 L、 I 就合并；
再拿第一个 U 按照规则向后合并一遍，再拿第一个 L 按照规则向后合并一遍，再拿第一个 I 按照规则向后合并一遍即可

B_大本营

如果大本营在其中一个守卫的侦察范围（圆）内，那么是不可行的。
考虑大本营在圆外的情况，不可行的情况就是大本营被几个圆围起来，所以把相交（切）的守卫的圆心连起来（建边）。
因为一个守卫最多与其他两个守卫相交，所以一个圆心的度最大值为2，那么建的边只能构成链或者是环，最后判断大本营是否在多边形内即可。

C_最大公因数

由于 $gcd(a,b)=xgcd(a,b)=x$ ，则 $gcd(\frac{a}{x},\frac{b}{x})=1gcd(\backslash frac\; ax,\backslash frac\; bx)=1$ ，那么这道题就是让我们找 $[l,r][l,r]$ 内两个数，其不仅是 $xx$ 的倍数，在除完 $xx$ 后也要互质。
两个相邻的整数是互质的，所以这里找 $[l,r][l,r]$ 内两个相邻的 $xx$ 的倍数就行

例：若存在，$gcd(r\mathrm{/}x,r\mathrm{/}x-1)=1gcd(r/x,r/x-1)=1$ ，$gcd(r\mathrm{/}x\ast x,(r\mathrm{/}x-1)\ast x)=xgcd(r/x*x,(r/x-1)*x)=x$

D_大盗

每个物品拿或者不拿，一个比较明显的01背包。
用数组维护到达每一个房间的背包状态，遇到藏品时所有状态可以加也可以不加，遇到三体人时保留对应状态即可。
使用数组暴力更新的复杂度为 $O(nk)O(nk)$ ，会超时，考虑优化。
一个 bool 类型的 $dpdp$ ，且只有加法和清空非保留的状态，可以对应到 $0101$ 串也就是 bitset ，如果其是用 int 维护的话时间为 $O(\frac{nk}{32})O(\backslash frac\{nk\}\{32\})$
在遇到藏品，加为 ，不加为 $dpdp$ ，合并就是
遇到三体人时看一下这一位是 $00$ 还是 $11$ 就行了
最后暴力从 $kk$ 向下找

E_睡大觉

因为是将其换算成最近的日期，所以我们记录一个当前的时刻，如果下一个给定的时间比当前的时间大我们就可以是为仍在这一天，否则就向后走一天。同时需要注意的是，因为他每次至少睡1s，所以如果与我们当前的时刻相同的话也要向后推一天，接下来就是算出当前是哪一天判断月与日是否就相同就可以了。

F_小欧拉

本题由于最终式子过于常见，解法多为打表找规律，下面是推导：

看累加符号右边，有一堆奇奇怪怪的东西，最奇怪的当然是 $\varphi \backslash phi$ ，推一下
考虑欧拉函数的计算式，设 $p\in primep\backslash in\{prime\}$ ，则 $\varphi (x)=x\prod _{p\mathrm{\mid }x}\frac{p-1}{p}\backslash phi(x)=x\backslash prod\backslash limits\_\{p|x\}\backslash frac\{p-1\}\{p\}$ ，发现这里有个 $xx$ ，这和 $\frac{\varphi (gcd(i,j))}{gcd(i,j)}\backslash frac\{\backslash phi(gcd(i,j))\}\{gcd(i,j)\}$ 简直天造地设的一对，那么约分掉
先不看下取整符号
$\begin{array}{c}{\displaystyle \frac{\varphi (ij)\varphi (gcd(i,j))}{gcd(i,j)}=ij(\prod _{p\mathrm{\mid }ij}\frac{p-1}{p})(\prod _{p\mathrm{\mid }gcd(i,j)}\frac{p-1}{p})}\end{array}\backslash begin\{aligned\}\backslash frac\{\backslash phi(ij)\backslash phi(gcd(i,j))\}\{gcd(i,j)\}=ij(\backslash prod\backslash limits\_\{p|ij\}\backslash frac\{p-1\}p)(\backslash prod\backslash limits\_\{p|gcd(i,j)\}\backslash frac\{p-1\}p)\backslash end\{aligned\}$
这里 $i,ji,j$ 共有的质因数前面的括号只被算了一次，而后面的括号是让它成功计算第二次，分配下来就是 $ii$ 的每个质因数参与计算一次，$jj$ 的每个质因数参与计算一次。

这就和 $(i\prod _{p\mathrm{\mid }i}\frac{p-1}{p})(j\prod _{p\mathrm{\mid }j}\frac{p-1}{p})(i\backslash prod\backslash limits\_\{p|i\}\backslash frac\{p-1\}p)(j\backslash prod\backslash limits\_\{p|j\}\backslash frac\{p-1\}p)$ 是一样的了，而这个式子就是 $\varphi (i)\varphi (j)\backslash phi(i)\backslash phi(j)$。
可推原式就是 ${\sum }_{i=1}^N{\sum }_{j=1}^M\varphi (i)\lfloor \frac{N}{i}\rfloor \varphi (j)\lfloor \frac{M}{j}\rfloor ={\sum }_{i=1}^N\varphi (i)\lfloor \frac{N}{i}\rfloor {\sum }_{j=1}^M\varphi (j)\lfloor \frac{M}{j}\rfloor \backslash sum\backslash limits\_\{i=1\}^N\backslash sum\backslash limits\_\{j=1\}^M\backslash phi(i)\backslash left\backslash lfloor\backslash frac\; Ni\backslash right\backslash rfloor\backslash phi(j)\backslash left\backslash lfloor\backslash frac\; Mj\backslash right\backslash rfloor=\backslash sum\backslash limits\_\{i=1\}^N\backslash phi(i)\backslash left\backslash lfloor\backslash frac\; Ni\backslash right\backslash rfloor\backslash sum\backslash limits\_\{j=1\}^M\backslash phi(j)\backslash left\backslash lfloor\backslash frac\; Mj\backslash right\backslash rfloor$ ，这两部分是一样的，那么只推导出来一侧就可以得出解了。
将 $\lfloor \frac{N}{i}\rfloor \backslash left\backslash lfloor\backslash frac\{N\}\{i\}\backslash right\backslash rfloor$ 放进计数循环，即前面设置一个累加为 ${\sum }_{i=1}^N{\sum }_{n=1}^{\lfloor \frac{N}{i}\rfloor }\varphi (i)\backslash sum\backslash limits\_\{i=1\}^N\backslash sum\backslash limits\_\{n=1\}^\{\backslash left\backslash lfloor\backslash frac\; Ni\backslash right\backslash rfloor\}\backslash phi(i)$
转换为 $nn$ 枚举 $ii$ 的倍数为 ${\sum }_{i=1}^N\sum _{i\mathrm{\mid }n}\varphi (i)\backslash sum\backslash limits\_\{i=1\}^N\backslash sum\backslash limits\_\{i|n\}\backslash phi(i)$
后面那个东西就是常见的卷积 $\varphi \ast 1=Id\backslash phi\; *1=Id$ 形式（下面有证明）
所以 $\sum _{i\mathrm{\mid }n}\varphi (n)=n\backslash sum\backslash limits\_\{i|n\}\backslash phi(n)=n$ ，${\sum }_{i=1}^{N}n=\frac{N(N+1)}{2}\backslash sum\backslash limits\_\{i=1\}^Nn=\backslash frac\{N(N+1)\}2$
那么 ${\sum }_{i=1}^N\varphi (i)\lfloor \frac{N}{i}\rfloor {\sum }_{j=1}^M\varphi (j)\frac{M}{j}=\frac{N(N+1)}{2}\frac{M(M+1)}{2}\backslash sum\backslash limits\_\{i=1\}^N\backslash phi(i)\backslash left\backslash lfloor\backslash frac\; Ni\backslash right\backslash rfloor\backslash sum\backslash limits\_\{j=1\}^M\backslash phi(j)\backslash frac\{M\}\{j\}=\backslash frac\{N(N+1)\}2\backslash frac\{M(M+1)\}2$
结果已出，看数据量开个 int128 就可以了

证明 $\varphi \ast 1=Id\backslash phi*1=Id$ :

$\mathrm{\forall }d\mathrm{\mid }m,1\le \alpha \le n\backslash forall\; d|m,1\backslash le\; \backslash alpha\backslash le\; n$ ，有 $(\alpha ,n)=d⟹(\frac{\alpha }{d},\frac{n}{d})=1(\backslash alpha,n)=d\backslash Longrightarrow(\backslash frac\{\backslash alpha\}d,\backslash frac\; nd)=1$
这样的 $\alpha \backslash alpha$ 可以选出来 $\varphi (\frac{m}{d})\backslash phi(\backslash frac\; md)$ 个 （$mm$ 下有多少个数是 $dd$ 的倍数）
所以 $n=\sum _{d\mathrm{\mid }n}\varphi (\frac{m}{d})n=\backslash sum\backslash limits\_\{d|n\}\backslash phi(\backslash frac\; md)$ ，即 $(\varphi \ast 1)(n)=Id(n)(\backslash phi*1)(n)=Id(n)$
得证

G_迷宫

最短路问题，两两建边，如果目标点为花那么边权为 $1-1=01-1=0$ ，否则为 $11$
固定源点与汇点，最短路的各种算法都可以写

H_安全区

初始的位置并不固定，同时又因为趋于无穷步。那么此时小明在每一个无毒迷失的概率都是相同的，在进行到一定轮之后，其每一步的情况与概率都是相同的。
那么我们此时应计算出下一步的所有情况，以此来作为答案。
所以答案的表示应为$\frac{\mathrm{下}\mathrm{一}\mathrm{步}\mathrm{能}\mathrm{够}\mathrm{到}\mathrm{达}\mathrm{安}\mathrm{全}\mathrm{区}\mathrm{的}\mathrm{步}\mathrm{数}}{\mathrm{下}\mathrm{一}\mathrm{步}\mathrm{可}\mathrm{以}\mathrm{走}\mathrm{的}\mathrm{总}\mathrm{步}\mathrm{数}}\backslash frac\{下一步能够到达安全区的步数\}\{下一步可以走的总步数\}$,暴力的方法就是统计每一个无毒密室下一步的情况然后相加就可以计算出，但是我们$n,mn,m$都很大无法计算出，所以我们就是假设每一个都是无毒密室，然后计算出相应的步数，随后遍历每一个有毒密室，我们只需将从这个有毒密室走出去的情况减去，并且更新一下从其他无毒密室走进来的情况（你可能在一在安全区的无毒密室走进来又退回到了安全区）。

I_密集

过去的时间越久剩下的蜗牛的数量也会越少，存在单调性，所以我们使用二分。

对于原本顺序为 $AA$，$BB$，$CC$ 的三个蜗牛，如果 $BB$ 先超过了 $CC$,然后 $AA$ 超过了 $BB$ 的话，那么 $AA$ 也一定能超过 $CC$。我们想一下如果想要知道在某一时刻那些蜗牛已经退赛的话，就是看有哪些蜗牛的相对顺序发生了变化。
那么 $checkcheck$ 函数中我们只需要求出每一个蜗牛按照此时的位置排序，从最远的位置向前遍历，更新一个此时的编号的最小值 $MinMin$，如果当前这个蜗牛的编号比 $MinMin$ 大，就说明其被超过了，这样就可以统计出来被超过的数量。
同时需要注意的是此时刻两个蜗牛位于同一个位置不算超过。

J_苹方树

本题树上差分和树链剖分都可做，这里说一下树上差分的写法。
由于询问在所有操作之后，那么就操作完离线向上跑一下 dfs 处理下结果然后输出。
操作很多，一次操作一条路径，可以打一个标记。如果都乘起来最大可以达到 $100^{4\times 10^{10}}100^\{4\backslash times\; 10^\{10\}\}$ 显然不可以直接乘，但由于平方数的判定方式是所有质因数的数量为偶数，所以将标记定为 $ww$ 的质因数与其对应的数量（$\sqrt{n}\backslash sqrt\{n\}$ 分解就可以）。
对于每次操作路径 $u,vu,v$ ，在向上走到 $lca(u,v)lca(u,v)$ 前，$uu$ 与 $vv$ 对于各自上面的祖先都起作用，所以在 $uu$ 与 $vv$ 这两个节点都存一下 $ww$ 的质因数与对应数量，但走到 $lca(u,v)lca(u,v)$ 之后，如果两个子树的信息都保留会造成一条路被计算两次的情况，所以要存一下 $ww$ 的质因数与其对应数量的相反数来让这条路对完整包含这条路的子树根节点的贡献只有一次。
存完之后，将所有节点我们存入的信息进行向上合并，每个节点 $ii$ 在用自己的信息合并完所有的子节点 $son[i]son[i]$ 的信息之后，暴力判断一下是否存在出现次数为奇数的质因数，如果存在那么 $v_{i}v\_i$ 就不是平方数，否则是平方数。

K_试香

$a_{i}a\_i$ 是 $22$ 的幂，判断 $xx$ 能不能由其中几个 $a_{i}a\_i$ 构成即可。

L_固执

我们可以发现对于当前的字符串，如果出现次数最多的那个字符的数量大于等于 $n\mathrm{/}2+1n\; /\; 2\; +\; 1$,我们就无法构造出合法的字符串，又因为要保证字典序最小，所以我们对于每一位，我们从 a 到 z 去遍历，如果将这个字符位于这一位，验证剩下的字符时候是否对于下一个后缀是否还满足上面的关系就可以了。