2025 年 8 月日祭

这个月的日祭直接写一起了，基本都在补题。

注意到 7 月份后来状态不好。

[洛谷 P4198] 楼房重建

考虑用一棵普通线段树维护，每个节点维护区间的最大值与区间内好的序列的长度，push up 的时候需要写一个类似于线段树二分的东西，时间复杂度。
[洛谷 P9824] [ICPC 2020 Shanghai R] Fountains

复杂度好神秘的一道题。~~自己写写不清楚，所以干脆看题解吧。~~
[洛谷 P6189] [NOI Online #1 入门组] 跑步

~~显然可以 oeis。~~

本题就是正整数拆分问题。考虑正整数拆分的做法。一种 DP 是设表示用了，当前和为的方案数，转移是。另一种 DP 是设表示选了个数，当前和为的方案数，转移是。发现第一种 DP 与拆分的数的值域有关，第二种与拆分的数的数量有关。所以考虑根号分治，对于的数进行第一种 DP，其它的进行第二种 DP。
[CWOI 0819 B组] C - 盲盒流水线

注意到这场因为 B 屎一样的题面搞乱了节奏？（不要给自己找借口了。）不过要是 JDS 不提醒我 A 可能要挂完。

题意是区间背包。因为是区间，容易想到用数据结构维护。注意到背包可以合并，那么写一个普通线段树的时间复杂度是，空间复杂度是。慢的原因是合并次数太多，所以考虑减少合并次数。发现这个过程是静态的，所以选择猫树。可是发现直接猫树的空间复杂度是，所以需要把询问离线下来，每个区间单独处理即可。
P13736 [JOIGST 2025] 日本浮现 / Japan Emerges

气死我了怎么绿题都场切不了。（注意到可能是做提高组模拟赛有点膨胀导致的。）

看到连通立马想到并查集（为啥我没立马想到），看到最小立马想到二分答案转化为判定性问题，判定的时候按题意模拟即可，如果两个块会相连就合并起来。
[洛谷 P13680] [IAMOI R2] 未送出的花

注意到祖先的盛开度一定比孩子大，因为如果交换两个点的盛开度会导致答案不增。所以对于每个点，它的美丽度取的点的位置是固定的，所以可以统计对于每个点，它的盛开度会被作为多少个点的美丽度（记作）。若我们选择朵花送出，相当于要选若干个点使得，最大化，发现一定是一个包含根的连通块，所以直接树上背包即可。
[CWOI 0822 B组] B - 美丽值

题意略。容易想到拆贡献，考虑一段会被计算多少次。设中有个数，剩下的个数，那么会被计算次。接下来考虑有多少个序列满足上述条件。首先从个数中选个数钦定为，那么个数就可以任意在中生成，剩下个数同理。所以总答案是。
[Atcoder ARC101C] Ribbons on Tree

考虑容斥（？，注意到我不会容斥，是怎么考虑到的），答案为，其中表示强制断开的边集为的方案数。注意到断开若干条边后，形成了若干个独立的连通块，那么每个连通块的方案数就是（当是偶数时）。所以直接树上背包即可。
[Atcoder ARC153D] Sum of Sum of Digits

好神秘的 DP。

发现难点主要在于进位。设表示考虑到第位，上一位有个数向这一位进了位，目前答案的最小值（不包含当前这一位）。对于每一位，先对按当前这一位从大到小排序，那么进位的数字一定是的一个前缀。接下来就是直接转移，枚举进位个数、当前这一位的值，然后统计当前数位的和与进位个数，再转移到下一位即可。
[CWOI 0824 B组] A - town

题意是将树分为若干个连通块，要求每个连通块的权值的异或和为，求方案数。

显然容易想到做树上背包，并且记录当前未闭合连通块的异或和。发现未闭合的连通块的异或和一定是或，所以只用设两个状态。需要特判（赛时被这个 Corner Case 创飞了。）
[CWOI 0824 B组] B - str

很显然的 DP，处理 LCP 即可。但是赛时写的什么 KMP 处理 LCP？什么东西？
[CWOI 0824 B组] C - perm

什么惊人的注意力。

显然与置换环有关。把每个置换环拿出来，设大小为，那么答案就是，其中表示大小为的置换环的解数，然后出题人注意到 ，特别地，。

Codeforces Round 1044 (Div. 2)

Link

D - Chicken Jockey

Solution.
E - I Yearned For The Mines

发现当树是一条链时是容易的（废话），所以考虑先使用最多次类操作把树分为若干条链，再用次操作检查每一条链。考虑如何在限定次数内将树分为链。我们尝试对树上的点分为以下三类：
- 链的端点；
- 链的中间点；
- 执行类操作的点。
我们可以通过一次 dfs 来确定点的类型。具体地，对于点：
- 若的儿子中存在一个中间点，或存在至少个端点，那么是操作点；
- 否则，若的儿子中恰好存在两个端点（且不存在中间点），那么是中间点；
- 否则，是端点。
于是我们就找出了需要执行类操作的点集。
F - Flint and Steel

令。容易想到一个朴素 DP：设表示炸死的苦力怕最少需要引燃多少只苦力怕，有转移，时间复杂度。考虑优化，设表示炸死的苦力怕最少需要引燃多少只苦力怕，那么 DP 转移就可以通过线段树来优化，实际复杂度。

Codeforces Round 1045 (Div. 2)

Link

D - Sliding Tree

在 CF Div. 2 D 放极弱的样例的出题人，愿你们的母亲在天堂相遇。

根据直觉容易想到与直径有关，然后就会自然地想到移动直径上的每一棵子树，然而这样是错误的。正确的做法应该是把直径的一端移到子树上，那么操作次数就应该是，其中为直径的长度。至于为什么这样是最优的应该口胡一下可以怔出来，但是不想怔了。
E - Power Boxes

实则并不难，只是赛时死磕 D 去了。赛后自己补出来了，虽然用时有点久。

设从开始的弹跳次数为，那么显然有，初始值是。显然会倒着询问。对于，若，那么我们询问即可得到的值。否则，我们可以直接推出，但并不知道的值。注意到，若，因为，我们一定可以通过一次询问直接确定。接下来，我们只需要交换与，原来的第个盒子现在成为了第个盒子，又有，所以我们可以通过一次询问直接确定。若，交换与即可。根据上述过程易证需要次询问。

Codeforces Round 1046 (Div. 1, Div. 2)

Link

B - For the Champion

被随机区分导致掉大分了呜呜呜。

注意到赛时就想到了移到角落，然后就不会了，男蹦。

移到两个角落就可以得到与了，然后就做完了。
C - By the Assignment

发现一个图是好的的充要条件是，每个环上所有点的点权都应该相同，这等价于每个边双中的点的点权应该相同。特别地，奇环上所有点的点权都应该是。所以我们只用找出每个边双联通分量，判断其中已确定点的点权是否全部相同，并且是否存在奇环即可。
D1 & D2 - From the Unknown

注意到我赛时基本会 D1 了，然后饭堂了以为自己是错的？然后开始考虑优化，想到了 D2 正解的？然后最后 D1 & D2 都没做出来？啊？

设。对于 D1，容易想到的是第一次询问个，得到的大致范围，满足（好像赛时就是推错了，导致没推出？）。接下来要确定的具体值，于是考虑询问 l 1 l 2 l 3 ... l (r - l)，有。

对于 D2，考虑优化。（以下是赛时想法）发现我们没有把利用起来。于是考虑利用根号分治与数论分块的思想，第一次询问个，若则说明，否则。若，则考虑询问个，此时每个都对应一个互不相同的；否则，沿用 D1 的思想即可。但是发现这样的询问次数依然可以达到 ……（以下是正解）发现以上有些数值取到时不一定最优，于是重新设常量表示：第一次询问个，若则第二次询问个。通过暴力可以求出，当时询问次数可以控制在以内。若精细实现，询问次数还可以再少一点。