【自主命题】牛客小白月赛 89 题解
这是第一场所有赛题都由我命制的公开比赛,也是第二场我参与命题的公开比赛。 比赛时由于内测下来大家都觉得 D 比 E 难,就更换了 DE 的顺序,本篇题解中没有发生更换,望读者注意。 比赛链接:Link. A. 伊甸之花 题目链接:Link. 若乐曲中同时存在 $1$ 和 $m$ 则无解,否则一定可以通过整体上移/下移一个音调来满足条件,时间复杂度 …
【整理】算法竞赛数据结构学习笔记
区间信息维护 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。 例如二维前缀和求法: $sum_{i,j}=a_{i,j}$ $sum_{i,j}+=sum_{i-1,j}$ $sum_{i,j}+=sum_{i,j-1}$ 例题:NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分连续…
[Practice]算法竞赛小东西简记
分层并查集 P2024 [NOI2001] 食物链。 并查集通过分层可以有效用于逻辑关系,相同的思路还可以用于动态判断当前图是否为二分图。 异或方程组 例题。 有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块,就可以给其中一块的所有点标记为 $1$,另一块所有点标记为 $0$,这样对于每个点只需要进行一些异或运算 $\Sigma …
[Competition]大学算法竞赛比赛记录册
不知道过了多久,似乎是时候开始回归之路了。 CodeForces Pinely Round 3 (Div. 1 + Div. 2) 链接:Link 时间:23.12.23 分数:4109(solved:4/10) 排名:963/10976 Rating 变化:2006->2006 简评: 我好菜。 BC 观察+猜想 D 从假设目标已有的情况反推,可…
只是聊聊【一】当我早上醒来,我怎么知道今天的我还是昨天的我?
几年前,我常常想到这个问题,晚上入睡,我失去了意识,第二天早上醒来,我却未曾怀疑早上醒来的我和昨晚睡下的我不是同一个人。这或许是一种潜意识吧,但这种潜意识又从何而来。后来我想,兴许是记忆赋予的。 早上醒来的我,和昨晚睡下的我有着及其相近的记忆,这让我从未怀疑我这个个体是否过了一宿仍是同一个个体,因为我所见所闻的一切都与我的记忆所吻合。假如记忆可以转…
关于我闲着没事写的诗歌的发布问题
呐,处于各方面的考量,我不再会把我的文学性诗歌发到本站。 今后我所有公开的诗歌作品(古体诗以及现代诗)都会发在我的 Lofter 账号:流凡上。 诗歌一部分是写着玩儿,一部分是我内心的吐露,当然很多是二者兼之。虽然质量不高,但作为我图一乐的内容(或许吧),也非常足够了。 至于原因,一方面是方便我发,不然重复发挺麻烦的,另一方面也让本站的内容可能不那…
P7878 「SWTR-07」My rating is 1064(hard version) 题解
题目链接。 解析 首先第一个帖子肯定会由某一个账号发出。大力观察可以发现当第二个账号发帖之后,接下来一定可以至少两个账号交替发帖,即安全系数不再会有损失。我们仅需要解决第二个账号第一次发帖在哪一个位置即可。 假设我们确定了第二个账号第一次发帖的位置 $i$,那么剩下的 $k-2$ 个账号一定会在 $[i+1,n]$ 中选择 $k-2$ 的最大值进行…
P7099 [yLOI2020] 灼 题解
题意 题目链接。 数轴上有 $n$ 个虫洞,有 $q$ 个按坐标升序给出的飞船,保证飞船一定在不会在第一个虫洞左边或最后一个虫洞右边。每个飞船每秒会等概率左移一格或右移一格,对于每个飞船,求到达任意一个虫洞的期望时间。 解析 记 $f_i$ 为位置在 $i$ 的飞船的期望时间,只要 $i$ 位置没有虫洞(有虫洞期望时间显然为 $0$),就有 $f_…