G题最后求出来所有大小联通子图个数的和与p不互质，这一步该怎么解决呢。
2021年东华大学金马程序设计联赛题解
DHUACM edited 3 年，7 月前
本次比赛由东华大学ACM协会举办。由于我们经验较少，水平有限，在比赛时发生了很多问题，影响了大家的比赛体验，在此深表歉意。感谢EOJ团队提供的技术支持，感谢比赛现场的志愿者们，感谢所有选手的参与。祝大家5月愉快！
A. Smart AEMShana
出题人：Mathemagic 难度：Easy
非常简单的签到题，问在1-m的加法表中第m小的数字是多少，聪明的同学一定一眼就能发现从小到大的数字数量是先从1增加到m个再由m个退回到1，比如给出的3x3的加法表就是先是一个2，再是两个3，再是三个4，再是两个5，再是一个6，因此列出方程即可求得位置在哪里，列出来发现是一个不等式，用一元二次不等式公式或者二分法都可以马上求解。时间复杂度$O(\log n)$.
B. Genshin Impact
难度: Easy
每一段伤害的期望值 $=$ 暴击率 $\times$ 发生暴击时的伤害 $+(1-$ 暴击率 $)\times$ 未发生暴击时的伤害，将两段伤害的期望值相加即为答案。
C. Back
出题人：m0del 难度：Very Easy
边数大于等于点数，则说明无向连通图有环。
D. Move The Numbers
出题人：licoded 难度：Easy
题目大意： 给定一个排列，每次调整是将数组的前 $k-1$ 个元素整体移动到数组末尾，问 $m$ 次调整后的排列
题解： 想象一下，如果将数组首尾相接成一条链，每次调整就相当于转动这条链；将数组的前 $k-1$ 个元素整体移动到数组末尾就相当于将链上的元素循环移动 $k-1$ 步。所以，只需要求出 $m$ 次调整后数组起始位置沿链移动的总步数（需要对数组长度 $n$ 取模）即可得到答案。
E. A Similar Game
出题人：down_down_bear 难度：Easy-Middle
题目大意：给定一个排列，每次将整个区域划分成多个部分，对每个部分进行翻转，对于每次操作过后的排列，询问逆序对个数。
题解：看完整个过程就会发现和归并排序十分类似，直接使用归并排序对逆序对进行维护即可。由于翻转前后区间之间的逆序对个数不会变化，只会变化区间内部的逆序对个数，我们可以事先预处理不同区间大小翻转变化的情况，每次询问可以在 $\log n$ 时间内得到答案。注意爆 $int$。
F. It is Quite Big
难度: Hard
记 $c(n)=(-1)^{\Omega(n)}$，
$$
F(n)=\sum_{k=1}^n\sum_{d|k}c(d)\sigma(\frac{k}{d})\
=\sum_{k=1}^n\sum_{d|k}c(d)\sum_{p|\frac{k}{d}}p\
=\sum_{k=1}^n\sum_{d|k}c(d)\sum_{p|\frac{k}{d}}\frac{k}{dp}
$$
令 $T=dp$，则 $p=\frac{T}{d}$
$$
\sum_{k=1}^n\sum_{d|k}c(d)\sum_{p|\frac{k}{d}}\frac{k}{dp}\
=\sum_{k=1}^n\sum_{d|k}c(d)\sum_{\frac{T}{d}|\frac{k}{d}}\frac{k}{T}\
=\sum_{k=1}^n\sum_{d|k}c(d)\sum_{T|k\land d|T}\frac{k}{T}\
=\sum_{k=1}^n\sum_{T|k}\frac{k}{T}\sum_{d|T} c(d)
$$
容易发现
$$
\sum_{d|n}c(d)=[n是完全平方数]
$$
$$
\sum_{k=1}^n\sum_{T|k}\frac{k}{T}\sum_{d|T} c(d)\
=\sum_{k=1}^n\sum_{T|k}\frac{k}{T}[T是完全平方数]\
=\sum_{k=1}^n\sum_{T^2|k}\frac{k}{T^2}\
=\sum_{T=1}^{\sqrt{n}}\sum_{k=1}^{\frac{n}{T^2}} k\
=\sum_{T=1}^{\sqrt n}\frac{(1+\frac{n}{T^2})\frac{n}{T^2}}{2}
$$
使用整除分块即可，时间复杂度 $O(\sqrt[3] n)$。
G. IDEA’s Tree
难度: Middle
我们可以先求得树上选取每个大小的连通块的方案数，然后就能求得连通块大小的期望。
不妨令 $1$ 为根，设 $dp[u][j]$ 表示在以 $u$ 为根的子树中，选取一个包含 $u$ 的连通块，并且这个连通块大小为 $j$ 的方案数。设当前在 $u$ 结点，$v$ 是 $u$ 的一个儿子，且刚遍历完以 $v$ 为根的子树计算出 $dp[v][j]$，则包含 $u$ 的连通块显然可以和包含 $v$ 的连通块合并，产生新的连通块。所以以 $v$ 为根的子树带来的贡献为 $dp[u][j]+=\sum_{k=0}^j dp[u][k]\times dp[v][j-k]$，枚举到子树大小即可。
H. A Simple Game
出题人：down_down_bear 难度：Easy
题目大意：每张牌被 $Alice$ 和 $Bob$拿到会获得不同的分数，如果双方都足够聪明，询问最后的胜利者。
题解：容易发现，对于每一张牌，不是 $Alice$ 拿就是 $Bob$ 拿，所以牌的价值由 $a_i$ 与 $b_i$ 的和决定。我们将牌按照价值排序，按顺序分配给$Alice$ 和 $Bob$，最后计算两者的分数即可.注意爆 $int$。
I. A Small Game
出题人：down_down_bear 难度：Easy-Middle
题目大意：已知将一个数加一、减一、和乘二的花费分别为 $A、C、B$，计算从 $0$ 到 $N$ 的最小花费。
题解：可以将题意转化为从 $N$ 到 $0$ 的最小花费，加一、减一、乘二替换为减一、加一、除二。容易发现，如果当前数 $x$ 为奇数时只有两种方案：加一或者减一，除二操作不合法；如果当前数 $x$ 为偶数时，也只有两种方案：除二或者一路减到 $0$，原因是偶数的时候如果将来要做除二操作，一定是现在做最赚，也就是说现在不做除二操作，将来也不会做，一路减到 $0$ 就行。即：
$$
\mathrm{dfs}[x]=min(x\times A,\mathrm{dfs}[x/2]) 若x为偶数
$$
$$
\mathrm{dfs}[x]=min(\mathrm{dfs}[x+1],\mathrm{dfs}[x-1]) 若x为奇数
$$
直接$dfs$的复杂度为$O(n)$，由于搜索过程中大量重复搜索，所以可以考虑记忆化搜索或者对小数据进行预处理等操作，大概时间复杂度为$O(logn)$。注意爆$int$。
J. A Special Game
出题人：down_down_bear 难度：Middle
题目大意：在一个直方图区域上，每次选择一个$1\times k(k<5)$的区域涂色，两个人中不能涂色的人失败。
题解：简单的博弈问题，对$n=1$的情况打表 $sg$ 函数，容易发现 $sg$ 函数在 $a_i$ 很大的时候存在循环节，打表循环节即可在 $O(n)$ 时间内得出当前局面的 $sg$ 函数。
K. AEMShana loves games
出题人：Mathemagic 难度：Easy
钩直饵咸的入门dp签到题，对于天上掉下来的弹幕，分黑白色，会让你减分
或者加分，求最高分的走法。
可以开一个二维数组，表示在当前时间的当前位置如果在这个位置能拿到多少分，如果这个地方没有弹幕就是 $0$。
那么题目就变成了从中间走到底求一条路径使得和最大，就变成了非常简单的数字金字塔模型。因为路的宽度限定为 $10$，所以时间复杂度 $O(n)$。
Comments
paleprince
由于状态只可能是 $\lfloor \frac{n}{2^i} \rfloor$ 或者 $\lceil \frac{n}{2^i} \rceil$ 所以必然是 $\Theta(\log n)$ 的?
承认这是道假题了，非常抱歉！