2021年东华大学金马程序设计联赛题解

DHUACM edited 3 年，11 月前

本次比赛由东华大学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{)}^{\mathrm{\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\wedge 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{d}\mathrm{f}\mathrm{s}[x]=min(x\times A,\mathrm{d}\mathrm{f}\mathrm{s}[x/2])若x为偶数$$
$$\mathrm{d}\mathrm{f}\mathrm{s}[x]=min(\mathrm{d}\mathrm{f}\mathrm{s}[x+1],\mathrm{d}\mathrm{f}\mathrm{s}[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

BHU-吴嘉帅

3 年，11 月前

G题最后求出来所有大小联通子图个数的和与p不互质，这一步该怎么解决呢。

回复 2 0

DHUACM

3 年，11 月前

承认这是道假题了，非常抱歉！

回复 1 0

Hile_Meow

3 年，11 月前

出题哥哥们能不能发下B题数据。对拍一年没拍出来，人都要看吐了(′д｀ )…彡…彡

回复 1 0

MAOoo

3 年，11 月前

红名可以尝试一下Polygon权限，可以在赛后看数据

回复 0 0

paleprince

3 年，11 月前

由于状态只可能是 $\lfloor \frac{n}{2^i}\rfloor$ 或者 $\lceil \frac{n}{2^i}\rceil$ 所以必然是 $\mathrm{\Theta }(\log n)$ 的?

回复 0 0

paleprince

3 年，11 月前

I 的复杂度不是 $O(logn)$ 吗

回复 0 0

DHUACM

3 年，11 月前

是，不好意思ORZ

回复 0 0

wish2lucky

3 年，11 月前

有电子证书吗

回复 0 0

DHUACM

3 年，11 月前

有电子证书，请近期注意邮箱对个人信息的查询

回复 0 0

ZegWee

3 年，11 月前

G树上dp+旋根其实可以做到$O(n)$的，加上逆元的常数也可以开到1e6

回复 0 1