作者: water_tomato

月流华 岁遗沙 万古吴钩出玉匣

98 篇文章

基础数据结构(前缀和/差分/树状数组/线段树)学习笔记
前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。 例如二维前缀和求法: 1. $sum_{i,j}=a_{i,j}$ 2. $sum_{i,j}+=sum_{i-1,j}$ 3. $sum_{i,j}+=sum_{i,j-1}$ 例题:NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分…
图匹配学习笔记
这两天零零散散地对图匹配算是进行了一个较为系统的学习,写个简单的学习笔记,既是记录,也是一边写一边帮助回忆巩固。 二分图匹配 判定 静态:黑白染色。 动态:分层并查集。并查集可以维护的可以是点的连接关系,也可以是关系的连接方式。连接两个点,我们可以改为连接这两个点的逻辑关系,黑-白,白-黑。如果有一天同一个点的黑白被连在了一起,则这就不是一个二分图…
[Practice]算法竞赛小东西简记
分层并查集 P2024 [NOI2001] 食物链。 并查集通过分层可以有效用于逻辑关系,相同的思路还可以用于动态判断当前图是否为二分图。 异或方程组 例题。 有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块,就可以给其中一块的所有点标记为 $1$,另一块所有点标记为 $0$,这样对于每个点只需要进行一些异或运算 $\Sigma …
[Competition]大学算法竞赛比赛记录册
不知道过了多久,似乎是时候开始回归之路了。 PAT 甲级 2023冬考 链接:Link 官方还没公开题目,暂用这个 时间:23.12.2 分数:400/400 排名:1/185 简评: diagonal这个单词不认识卡了我半天... A dfs水题,前提是认识diagonal B 单调栈水题 C 树上dfs+双指针,两个part没啥关联,不难 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_…