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

DHUACM edited 1 年,9 月前

本次比赛由东华大学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

BHU-吴嘉帅

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

DHUACM

承认这是道假题了,非常抱歉!

Hile_Meow

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

MAOoo

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

paleprince

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

paleprince

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

DHUACM

是,不好意思ORZ

wish2lucky

有电子证书吗

DHUACM

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

ZegWee

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