OI

题解：CF1733E Conveyor

0 条评论 OI 无标签 SunJude
Solution读完题发现因为每个史莱姆每秒都会往右或者往下走，所以不可能有相遇，所以那个合并是没用的。第 $t$ 秒很不好考虑，可以转化成 前 $t$ 秒有没有史莱姆经过 $(x, y)$，比较第 $t$ 秒和第 $t - 1$ 秒。那么前 $t$ 秒是好做的，考虑一个位置有 $x$ 个史莱姆经过时，因为方向是右下右下交替的，显然有 $\lceil \frac{x}{2} \rceil$ ...

题解：AT_joisc2016_j 危険なスケート

0 条评论 OI 无标签 SunJude
首先发现一次滑冰产生的冰块不会重复利用，也不会对最短路产生阻碍，因为我们可以在第一次到达这个格子的时候就直接去要去的地方。考虑怎么移动，到达另一个点：移到相邻的格子，比方说移到右侧的格子，可以通过先往右滑再往左滑来实现，步数为 $2$。滑到下一个冰块，步数为 $1$。发现所有的状态都可以通过这两个移动方式转移过来，并且其他的移动方式是不优的。于是考虑建出图来跑最短路，具体地，把每个点和其相邻...

CF2147E 题解

0 条评论 OI 无标签 SunJude
赛时想了个二分做法假飞了，最后遗憾离场了。/dkSolution考虑求出对于每个答案，需要的最小操作数。把不操作时所有元素的按位或结果记作 $c$，显然小于 $\text{popcount}(c)$ 的答案都是 $0$。然后考虑从 $c$ 往上增加，首先显然为了让操作数较小，我们要优先让低位的 $0$ 变成 $1$。设我们要让第 $0 \sim m$ 位都变成 $1$，会发现从第 $m$ 位...

Prufer 序列

1 条评论 OI 无标签 SunJude
Prufer 序列$n$ 个点有标号无根树方案数：$n ^ {n - 2}$考虑转化成组合意义：对于每棵有标号无根树，可以将其唯一地映射到一个长度为 $n - 2$，值域为 $[1, n]$ 的序列中。建立 Prufer 序列每次选择一个编号最小的叶结点并删掉他，然后在序列中记录他的父亲，如此重复 $n - 2$ 次。$O(n)$ 实现：首先，删除一个叶结点，叶结点数量是单调不增的，只会不变...

csp 前训练

2 条评论 OI 无标签 SunJude
10.18T2 P14066容易发现分成的三段按 $a_i$ 排序之后一定是连续的三段，否则可以通过交换两个人所在的集合使得限制更严格。钦定最大的 $a_i$ 在第三组。按照 $a_i$ 从小到大的三段分别为 $123$ 还是 $213$ 分类。枚举第一段的长度，然后可以计算出第二段最少是多少，最后检查第三段长度是否符合要求。T3 AT_joisc2015_f首先把每个人进门出门看成一个事件...