A Too Min Too Max
排序，选前 2 后 2。
B Yet Another Coin Problem
整出 LCM。
容易发现要么是对 LCM 的余数，要么就是对 LCM 的余数 + LCM。
Continue reading “Codeforces Round 1934 解题报告”分类： 算法竞赛
Codeforces Round 1929 解题报告
A Sasha and the Beautiful Array
直接最大值减最小值即可。
B Sasha and the Drawing
容易发现，首先填第一行和最后一行是较优的，只有四个端点处有可能重复，别的点每加一个都会覆盖两条对角线。
对四个端点特判即可。
Continue reading “Codeforces Round 1929 解题报告”Codeforces Round 1923 解题报告
A Moving Chips
从最后往前，每一格都得点一次。
B Monsters Attack!
这坐标正负显然没关系。
绝对值，排序，前缀和，判断每个点是否可行即可。
Continue reading “Codeforces Round 1923 解题报告”Codeforces Round 1937 解题报告
A Shuffle Party
容易观察到在 $2 \cdot x$ 的时候一就会被交换出去。
输出最小的 2 的次幂即可。
B Binary Path
开始和结尾是固定的。
扫描两层中间的部分，只能走上面就归 0，都能走 +1， 只能走下面就结束。
Continue reading “Codeforces Round 1937 解题报告”NOI 2022 游记 SP – 上海之旅
漫天闪烁的繁星
化作繁星
伴着我独自前行
越过光年的距离
照亮我的眼睛
0 启程
上海，中国对外开放的中心。
这场上海之旅来之不易。伴随着紧急疏散的要求，我和抹茶和 dyf_dyf 一同打的前往花桥，乘坐上海轨道交通 11 号线，前往上海。
Continue reading “NOI 2022 游记 SP – 上海之旅”NOI 2022 游记
0 序
今年是最感到时间如白马过隙的。每天窝在机房看自己不会的东西，每天都在想明天要学什么新的东西，然后日子就一天天的过去了。
想学的东西还没有学完，CCF 要求所有选手先到昆山的通告倒是先来了。不管如何，参赛为重，只得踏上前往昆山的旅途。
1 愉快的七天
因为雅礼人的高铁经过温州 & 他们订票的时候也没带上我，我就自己整了个别的列车。
在 08 月 13 日到达的昆山。
一到昆山就跑去找 dyf_dyf 和 Lucky_Yukikaze 聊天。
整理一下情况是几乎整个新疆省队都在一起（除了 Arachv）。接下来的日子就很简单了，蜜雪冰城，Among us，写模版，聊天。
简单欢乐的日子永远过的很快，眨眼见就到了 20 号。
Continue reading “NOI 2022 游记”Codeforces Round 1699 解题报告
考试链接： https://codeforces.com/contest/1699
考试的时候 30min 写完 ABC 发现 D 没几个人就摸了。考完看了眼 E 发现一眼切。最后竟然上分了，我大受震撼。
A The Third Three Number Problem
求能否找到任意三个数字 $a,b,c$ 使得 $(a \oplus b) + (a \oplus c) + (b \oplus c) = n$ 。
容易发现奇数根本不可能，偶数随便构造。
B Almost Ternary Matrix
给表格染色。使得对于任意一个格子，有且只有两个相邻格子和这个颜色不同。
以 2x2 为一个单位，交叉构造即可。
虚树
用途
对于大多数情况，树中只有很少一部分点是对当前要处理的信息是有意义的。
我们可以在保留这些有意义的点，不破原树结构的情况下得到一个很精简的树，这样我们就不用遍历整颗树了。
这种做法就叫虚树。
Continue reading “虚树”Dirichlet 前缀和
和后缀和。
0 序
求
$$
b_k = \sum_{i|k}a_i
$$
或
$$
b_k = \sum_{k|d}a_d
$$
都一样，没啥区别。
Continue reading “Dirichlet 前缀和”斯坦纳树入门
0 序
这个东西看了半天没想明白为啥不是最小生成树，然后发现最小生成树实际上是最小斯坦那树的特殊形式
— 最小生成树里的所有点都是关键点。
最小斯坦那树是指在一个无向图中，求其最小生成网络使得其
- 包含所有关键点
- 总权值在满足 1 的情况下最小。