-
[ARC205D] Non-Ancestor Matching 题解
赛时没打这场 ABC。 设 的重儿子是 ，以 为根的子树为 ， 的大小是 ， 中最多能选出 个点对。定义点 是好的，当且仅当 。接下来分点 是不是好的分类讨论： 若点 是好的：显然有 。 若点 不是好的：我们尝试让 成为好的。具体地，我们可以在 中先选取一些点对，并且从 中删去这些点，使得 减小，从而使点 成为好的。在 中最多可以选取 个点对，所以 的最小值是... -
[AT TTPC2015 O] 数列色ぬり 题解
鲜花MX NOIP 模拟赛 T3，补题时只找到了一篇 十年前的日文题解，并且目前洛谷里这道题唯一一个讨论甚至还是提供翻译，并且也是七年前的了。这题真冷门。 下文中，最长上升子序列简写为 LIS，最长下降子序列简写为 LDS。 注意到红色的元素构成了一个单调递增的子序列 ，蓝色的元素构成了一个单调递减的子序列 。在最优情况下，若 恰好是 LIS，且 恰好是 LDS，那么答案为 ；否则，... -
2025 年 9 月日祭
鲜花 (2025.9.1)注意到我停课了。 另外注意到我今天上午做了三道题，下午也许是在尝试改上一场 CF 的 Div. 1 E，顺便学习了一下反射容斥。学了之后发现改不出来，于是放弃了，并开始补日祭。总之就是下午一道题都没做？啊？什么效率？但是我不是挺认真的吗？啊？ MX NOIP 3Link A - Novelist 略。 B - Bicycle Tour 根据部分分容易想到从小... -
[ABC420G] sqrt(n²+n+X) 题解
一眼根号复杂度。 这道题应该有很多做法。我的做法是尝试消掉 ，使得关于 只出现了一次项。 设 那么就可以枚举 解出 ，当 是整数是才是合法解。 是根号级别的，但是为了保险， 的值域可以开大一点。 赛时提交记录，稍微卡了点常，所以写法有点沟槽。应该不卡常就用 set 去重也能过。 -
[CF2133D] Chicken Jockey 题解
Upd. 修了一点笔误。 显然是 DP，并且是稍微想一想就能发现性质的 DP。 首先攻击的形式一定钦定若干个生物，打死这些生物，使得剩下的生物形成若干个堆叠。对于每个堆叠，我们再从下往上依次一个个打死。容易发现，若 是一个独立的堆叠，需要的攻击次数是 ，减一与加一是因为除了第一个生物都会受到 的跌落伤害。设前缀和数组为 ，那么上式就是 。 注意到，为了减少攻击次数，我们会尽量增加摔落伤害... -
[ARC203C] Destruction of Walls 题解
看到 就显然分讨了。 Case 1： 此时显然无解。 Case 2： 此时答案即为从 走到 的方案数，即 。 Case 3： 即在 Case 2 的基础上再选一堵墙拆除。发现对于任意一条从 到 的路径，都可以选择其余任意一堵墙拆除。故答案为 。 Case 4： 发现此时又产生了两种情况。一种是路径长度依旧为 ，另一种是路径长度为 。 Case 4.1：路径长度为 即在 ... -
[ARC203B] Swap If Equal Sum 题解
首先，必要条件是两个序列的和相同。 容易发现，操作是可逆的。所以考虑将 和 变为一种相对规则的形式，比如单调。由于单调不降与单调递增是对称的，所以接下来讨论单调不降。 现在的问题是，能否将一个序列通过若干次操作变为单调不降的。考虑简化操作，变成： 交换 0 与 0 0 （或）交换 0 1 与 1 （或）交换 1 0 与 1 注意到，当序列之和（即 的数量） 时，我们一定可以把所有的... -
[ARC203A] All Winners 题解
手模几个样例之后，容易发现构造： 对于每个队伍，令其中 个人始终获胜，其中 个人始终战败。 那么对于每一个始终获胜的人，都可以匹配到 个其他队伍的始终战败的人。同理，对于每一个始终战败的人，都可以匹配到 个其他队伍的始终获胜的人。 当 是奇数时，每个队还各有 个人未被匹配。此时我们只能令其中一个人始终获胜。 综上所述，答案为 。代码就懒得放了。 -
2025 年 8 月日祭
这个月的日祭直接写一起了，基本都在补题。 注意到 7 月份后来状态不好。 [洛谷 P4198] 楼房重建 考虑用一棵普通线段树维护，每个节点维护区间的最大值与区间内好的序列的长度，push up 的时候需要写一个类似于线段树二分的东西，时间复杂度 。 [洛谷 P9824] [ICPC 2020 Shanghai R] Fountains 复杂度好神秘的一道题。自己写写不清楚，所以干脆看题... -
自述
Here’s something encrypted, password is required to continue reading.
