题解 | #2022河南萌新联赛第（三）场：河南大学#

A 玉米大炮
给定 $nn$ 个玉米大炮,每个玉米大炮都有自己的攻击伤害和装填时间,何时可以击溃僵王博士。
很容易发现答案具有单调性,如果花费 $xx$ 的时间可以击溃目标,则花费$x+1x+1$的时间也可以击溃目标,可以直接二分答案,考虑到二分的左右区间在 $[0,10^{18}][0,10^\{18\}]$,对于 $C++C++$ 选手可能需要使用 $\mathrm{\_}\mathrm{\_}int128\backslash \_\backslash \_int128$ ,或者在二分的过程提前判断是否合法, $pythonpython$ 选手则可以直接二分通过。
B 逆序对计数
给定$nn$个数的排列,$qq$次询问,每次询问区间$[l,r][l,r]$,反转区间$[l,r][l,r]$后,排列的逆序对个数。每次询问独立。
首先,对于一个排列,如果区间反转,逆序数等于区间种所有的对数减去当前的逆序对数,即原本的正序对变为逆序对,原本的逆序对变为 正序对。如果对于每个位置记录其到后面所有位置的逆序对个数即可解决本题,考虑从$[l,r]\to [l,r+1][l,r]\; \backslash rightarrow\; [l,r+1]$逆序对的 个数增加区间$[l,r][l,r]$中比$a_{r+1}a\_\{r+1\}$的数的个数,所以可以事前统计对于每一个位置, 到他的前面的每一个位置比他大的数有多少个,统计完直接计算逆序对即可。
时间复杂度 $O(n^2)O(n^2)$
当然也可以使用树状数组统计逆序对,可以很好的通过本题。
时间复杂度近似 $O(n^2)O(n^2)$
同时特别感谢kws提供的莫队做法。
时间复杂度近似 $O(q\times \sqrt{n}\times log(n))O(q\; \backslash times\; \backslash sqrt\{n\}\; \backslash times\; log(n))$
C 区间操作
给定$nn$个数,$qq$次询问。两个操作$op{t}_{1}opt\_1$询问区间$[l,r][l,r]$的漂亮值,$op{t}_{2}opt\_2$更改区间$[l,r][l,r]$的值。

考虑线段树,可以区间加,和区间求和。如果可以在一个很低的时间复杂度 出来每个$xx$对漂亮值的贡献是多少,然后通过线段树操作即可通过本题, 如果直接暴力求出所有质数,每个质数需要时间$\sqrt{4\times 10^6}\backslash sqrt\{4\backslash times\; 10^6\}$ ,很明显不足以通过本题。考虑根号分治,比$20002000$小的质数大概$300300$个,预处理出来 所有小于$20002000$的质数,然后只看是否可以整除这些质数,只需要处理$300300$次, 然后用处理完的数经行线段树操作即可。
时间复杂度 $O(n\times log(n)+300\times n)O(n\; \backslash times\; log(n)+300\backslash times\; n)$
当然使用线性筛预处理出来所有数的贡献,然后线段树操作。
时间复杂度近似 $O(n\times log(n)+w)O(n\; \backslash times\; log(n)\; +\; w)$
D 小蓝的新技能

对于 $lcm(a^3,b^3)+gcd(a^3,b^3)=nlcm(a^3,b^3)+gcd(a^3,b^3)=n$中,满足$(a,b)(a,b)$的对有多少个。
可以推断出$lcm(a^3,b^3)\times gcd(a^3,b^3)=a^3\times b^{3}lcm(a^3,b^3)\; \backslash times\; gcd(a^3,b^3)\; =\; a^3\; \backslash times\; b^3$, 枚举$gcd(a,b)gcd(a,b)$,只需要枚举$\sqrt[3]{n}\backslash sqrt[3]\{n\}$个数,然后再次枚举每一个 $aa$,可以发现时间复杂度是调和级数,然后判断是否合法,如果合法结果加$11$
时间复杂度 $O(\sqrt[3]{n}\times log(\sqrt[3]{n}))O(\backslash sqrt[3]\{n\}\backslash times\; log(\backslash sqrt[3]\{n\}))$
E 演算任务

从给定的$nn$个数中选取一些,使其的和等于目标值,特别的可以进行一次除法操作。
通过背包可以算每一个位置可以组成的数, 在通过一个背包记录每一个位置经过一次除法可以组成的数, 最后输出两者的最小值。 也可以正序做一下一维背包,倒序做一下一维背包,然后再每一个位置,枚举前面的每一个背包除以2的值 以及不除以2的值,同时与目标值相减判断后面的背包是否有这个值。
时间复杂度 $O(n\times w)O(n\; \backslash times\; w)$
F 爱学习的小蓝
当前电子数在第几层。
签到,直接模拟即可。
G 小蓝的玻璃球
找与其他球相撞的概率。
玻璃球与其余每个球都会在某一弧度区间 $[l,r][\; l\; ,\; r\; ]$ 范围内相撞，我们只需要求出与每一个球相撞对应的弧度区间，合并区间后的总长度与圆的弧度的比值就是相撞的概率。

已知:点G的坐标为$(x,y)(\; x\; ,\; y)$,两圆的半径均为1。以求区间上限r为例:如图所示,做切线 $IJIJ$ 为球 $EE$ 和球 $GG$ 的公切线,过 $EE$ 点做直线 $EKEK$ 平行于直线 $IJIJ$ 所以当球 $EE$ 沿直线 $EKEK$ 运动时，两球不会相撞，刚好相切,此时 $\mathrm{\angle }KEL\backslash angle\; KEL$ 对应的弧度为相撞区间的临界值。其中$\mathrm{\angle }KEL=\mathrm{\angle }KEG+\mathrm{\angle }GEL\backslash angle\; KEL=\backslash angle\; KEG+\backslash angle\; GEL$可以发现： $\mathrm{\angle }GEL\backslash angle\; GEL$的值为线段 $GLGL$ 的长度与线段 $ELEL$ 的长度比值的反正切 $\mathrm{\angle }KEG\backslash angle\; KEG$的值为线段 $KGKG$ 的长度与线段 $EGEG$ 的长度比值的反正弦 其中线段 $KGKG$ 的长度恒为 $22$ ,线段GE的为 $\sqrt{x^2+y^2}\backslash sqrt\{x^2+y^2\}$; 同理做出两条圆的另一条公切线即可求出区间下限。 由于区间范围属于 $[-\pi ,\pi ][-\backslash pi,\backslash pi]$。当越界时，记得处理一下溢出的范围。 求出所有的区间段后，把所有区间段的弧度进行合并，合并后的值与圆的弧度的比值即为答案。
H 树上操作
选择三个相连的节点,使代价最大。
首先需要预处理出来所有代价,考虑 $11$ 节点为根处理出来所有子节点的代价,以及自己的代价, 然后对于每一个子节点的代价为 $max(f_u,f_p)max(f\_u,f\_\{p\})$ , $f_{u}f\_u$ 为当前节点为子树的代价, $f_{p}f\_p$ 为将 父节点作为子树的代价 $f_p=max(f_{f_p}+a_p,max(f_{son})+a_p)f\_p\; =\; max(f\_\{f\_p\}\; +\; a\_p,max(f\_\{son\})+a\_\{p\})$ 特别的,选取的所有儿子节点 中要去除他要更新的儿子的节点,所以记录最大值和次大值即可。处理出来所有代价,选取连续的三个节点,可以枚举每一节点,要么选两个儿子, 要么选一个儿子+这个儿子的儿子,所以直接树形dp即可。
时间复杂度 $O(n)O(n)$
I 旅行
从城市$11$到城市$nn$, 每隔一天多花费$ww$。
将每个城市看成两个城市,缴费的,未缴费的,然后让缴费于未缴费的城市 建边,跑最短路即可。
时间复杂度 $O(n\times log(n))O(n\backslash times\; log(n))$

J 神奇数字
给定三个数字$a,b,ca,b,c$其对一些数取余后结果相同,找到所有取余后结果相同的正数。
如果三个数相等,对任何数取余结果都相同,输出$-1-1$。 如果不想等,想到任何数都可以写成$x\times y+wx\; \backslash times\; y\; +\; w$, 作$a-b=(x_1-x_2)\times ya-b\; =\; (x\_1-x\_2)\backslash times\; y$,此时$a,ba,b$对$x_1-x_2,yx\_1-x\_2,y$ 取余结果相同,如果是$a,b,ca,b,c$则取$gcd(abs(a-b),abs(b-c),abs(a-c))gcd(abs(a-b),abs(b-c),abs(a-c))$ 然后输出所有的质因子即可。
时间复杂度 $O(t\times \sqrt{n})O(t\backslash times\; \backslash sqrt\{n\})$

K 实习生的任务
模拟一个游戏逻辑。
直接模拟即可,根据题意排序,输出结果。

L 合成游戏
求满足题意的方案数.
如果不考虑限制条件,$nn$的排列一共有$n!n!$种. 然后考虑去除不满足限制条件的情况,在由一级卡牌合成二级卡牌的过程中,可以得到$\lfloor n\mathrm{/}2\rfloor \backslash lfloor\; n/2\; \backslash rfloor$个二级卡牌,合成二级卡牌的一级卡牌的顺序可以交换,所以一共可以得到$\frac{n!}{2^{\lfloor n\mathrm{/}2\rfloor }}\backslash frac\{n!\}\{2^\{\backslash lfloor\; n/2\; \backslash rfloor\}\}$种二级卡牌的组合.二级合成三级同理.所以最终答案为.
时间复杂度 $O(t\times log(n))O(t\; \backslash times\; log(n))$