出去玩了半个星期。
P2466 [SDOI2008] Sue 的小球
很经典的套路，直接区间 DP 不容易维护时间，考虑将时间的代价前置计算，则设 \(f_{i, j, 0/1}\) 表示得到 \([i, j]\) 最后停在 \(i / j\) 的最大得分。
那么有 \(f_{i, j, 0} = \max\{f_{i + 1, j, 0} - (x_{i + 1} - x_i) \times w_{i, j},f_{i + 1, j, 1} - (x_j - x_i) \times w_{i, j} \}\)，其中 \(w_{i, j}\) 就是会带来的后续时间代价，有 \(w_{l, r} = \sum_{i = 1}^n v_i - \sum_{i = l}^r v_i\)。
然后做完了，蓝书上好像还有一道类似题，应该是斜率优化那一章的。
牛客2025暑期多校第三场 G
牛客题都是 HoshizoraZ 老师放在模拟赛中的。
简单题。容易想到对于每条线段的两个端点加上一个随机值，然后判断有多少个不同的值即可。
牛客小白月赛 119 - F
容易发现每个连续 o 是独立的，考虑计算 \(f(n, m)\) 表示长度为 \(n\) 的 o 段且 \(m\) 刀的最小代价，显然能够 \(\Theta(1)\) 计算。
于是考虑直接背包 DP 是 \(\Theta(n^3)\)，并且没有优化空间。
考虑想一个贪心策略。朴素贪心比如对半切是假的，所以考虑反悔贪心，可以 \(\Theta(n\log n)\)。
据说 HoshizoraZ 老师是这一场月赛的出题人。
牛客 2025暑期多校第四场 L
上强度了。
显然 \(\lceil \frac{x + a_i}{2} \rceil\) 有上界 \(\frac{x + a_i + 1}{2}\) 和下界 \(\frac{x + a_1}{2}\)，则答案显然也有上界和下界。
可以通过推式子得到答案的下界是 \(\frac{x}{2^{r - l + 1}} + \frac{a_l}{2^{r - l + 1}} + ... + \frac{a_r}{2}\)，上界在这个式子的基础上多出来一堆 \(\frac{1}{2^k}\)，可以使用等比数列求和，但会发现和下界相差不超过 \(1\)，于是答案一定是下界的上取整。
令 \(f(l, r) = a_l + 2a_{l + 1} + ... + 2^{r - l}a_r\)，则答案可以写作 \(\lceil \frac{x + f(l, r)}{2^{r - l + 1}} \rceil\)。
发现在 \(r - l + 1 > 30\) 时 \(x\) 没有贡献所以考虑暴力处理每个 \(30\) 块然后进行倍增。
记 \(g(l, r) = \lceil \frac{f(l, r)}{2^{r - l + 1}} \rceil\)，\(h(l, r) = 2^{r - l + 1} - f(l, r) \bmod 2^{r - l+ 1}\)，则 \(30\) 内的答案为 \(g(l, r) + [x \geq h(l, r)]\)。
考虑如何在倍增的时候转移这个东西，假设我们已知 \([l, m]\) 和 \([m + 1, r]\) 的信息，要计算 \(A = g(l, r) + [x \geq h(l, r)]\) 的 \(g\) 和 \(h\)。我们先跳 \([l, m]\)，跳到 \(x' = g(l, m) + [x \geq h(l, m)]\)，然后再跳 \(g(m + 1, r) + [x' \geq h(m + 1, r)] = A\)。
所以有 \(g(l, r) = g(m + 1, r) + [x' \geq h(m + 1, r)] - [x \geq h(l, r)]\)，那么分成几种情况讨论：
- \(g(l, m) \geq h(m + 1, r)\)，则让 \(g(l, r) = g(m + 1, r) + 1\)，这时候答案已经对了，\(h(l, r)\) 取 \(\infty\) 即可。
- \(g(l, m) = h(m + 1, r) - 1\)，则 \(g(l, r) = g(m + 1, r)\)，此时只有当 \(x \geq h(l, m)\) 时答案才能再多 \(1\)，所以 \(h(l, r) = h(l, m)\)。
- \(g(l, m) < h(m + 1,r) - 1\)，则 \(g(l, r) = g(m + 1, r), h(l, r) = \infty\)。
最后查询的时候先把不足 \(30\) 的部分暴力走完然后倍增跳即可。
可能有点问题，毕竟这个东西靠语言着实不好描述。
牛客 2025暑期多校第五场 C
好诡异的题。
若 \([l, r]\) 必败，则 \([l - 1, r]\) 和 \([l, r + 1]\) 必胜，\([l - 1, r + 1]\) 必败。进一步 \(l + r = k\) 的状态具有相同的胜败态，考虑二分找到 \([l' + d, r' - d]\) 合法但 \([l' + d + 1, r' - d - 1]\) 不合法。
令 \(L = l' + d, R = r' - d\)，则继续二分找到分界点使得 \([L + lm, R]\) 合法，\([L + lm + 1, R]\) 不合法。同理找出 \(rm\)。
则我们可以断言若 \(lm\) 和 \(rm\) 其中之一为奇数则先手必胜。
CF1554D
史诗级构造题，差点被击杀。
注意到只需要构造两段奇偶性不同的 \(a\) 然后中间放一个 \(b\) 即可。
P8986 [CTT2021] 基因编辑
真比构造简单吧。
\((x, y)\) 合法当且仅当 \(suf_{y, 2} < pre_{x, 1} < l < r < suf_{y, 1} < pre_{x, 2}\)。其中 \(pre\) 和 \(suf\) 记录的是从 \(1 \sim n\) 和 \(n \sim 1\) 前两次出现的位置。
要求 \(y - x + 1\) 最小，则对于 \(pre_{x, 1}\) 我们记录 \(f\) 表示前缀中找到 \(suf_{y, 1}\) 最靠前的的 \(suf_{y, 2}\)，最后统计时再 check 以下 \(pre_{y, 2}\) 满不满足条件即可。这样做正确性显然，因为如果最靠前的 \(suf_y\) 都不满足条件那往后的也一定不满足 \(pre_{x, 2}\) 的限制。
PR #9 A 比赛
直接树形 DP \(\Theta(n^3)\) 是比较简单的，考虑优化。
你会发现从原来的叶节点换另一个叶节点往上比赛的过程中只会改变某些部分，而另一些部分是不会改变。所以考虑类似删物背包的方式进行分治，每次一半的 DP 值都可以直接处理不会变，有 \(f_x = f'_x \times \underset{y}{\sum} \frac{f'y \times b_x}{b_x + b_y}\)，其中 \(f'\) 表示上一层的 DP 值（因为这个比赛过程相当于一棵满二叉树从最底层开始一步步向上）。
然后分治到叶节点算答案的时候也和这个类似。按照我们刚才的过程，每个点的 \(f_p\) 都对应的赢到某个层数的概率，所以直接不断乘上 \(x\) 赢的概率即可。
放个代码。提交记录 #1210026。
P13564
好诡异的构造题！但是好简单的喵。大概 Div2 C 难度的喵。
考虑先尽量对于每个关键点选 \(k - 1\) 个点连成环，会发现可能会有关键点不满 \(k - 1\) 个点，或者有关键点没有非关键点匹配。
我们发现这两种情况都是把能连的连了然后让最后一个非关键点连到其它环上即可。
P13565
考虑一定不可能让当前的最高位 \(1\) 再左移，所以不妨从高到低考虑每个位，尝试对每个位进行调整，然后就做完了。
P13567
好恶心的题目！要不是这个题卡了我这么久我就有时间做 T3 就能 AK 了！
但还是人菜写不对二分导致的。
考虑这种题目一定要转化成线段树维护区间加，考虑 DFS 序。不妨将点按照与根的距离为第一关键字，DFS 序为第二关键字排序。这样子我们对于一次修改对于与根的距离为 \(d_u + x\) 的区间进行二分，找到 DFS 序位于 \([u + 1, u + sz_u - 1]\) 的即可。
然后还要往上找 \(x\)，倍增做即可。查询也和修改差不多，代码挺魔怔的。
记录详情