8.11~8.17

越来越菜了，越来越摆了

P13566 「CZOI-R5」青蛙的旅行

有点弱智的题目。

直接 \(f_{i, j, w}\) 然后用前缀和优化一下转移即可，代码有点难写。

记录详情

AGC049D

人类智慧题。

考虑题目要求相当于差分递增。直接计数不好做，我们考虑构造一个构造方式与答案序列的双射。

首先有一个发现是 \(A\) 数组一定是一个单谷凸包，于是考虑凸包的最低点，不妨先让最低点在 \(A\) 的最左侧。那么我们要经过一些操作让差分递增的同时总和为 \(M\)。

先将整个数组的所有值设为 \(X\)，这样差分数组全为 \(0\)。考虑通过操作将 \([i, n]\) 的差分数组加一，对应在 \(A\) 数组上可以是 \(A_j \leftarrow A_j + j - i + 1\)。这种构造方式与答案序列显然形成了双射。

那么拓展一下，如果最低点为 \(A_M\)，那么我们可以通过使 \([i, M - 1]\) 的差分数组加一和 \([i, n]\) 的差分数组加一实现构造。但这样算方案会算重，因为可能 \(A[L \sim R]\) 都等于 \(A_M\)，所以我们要钦定 \(A_M\) 为最靠左的最低点。我们可以通过将 \([1, M - 1]\) 的差分数组提前减一达成这一目的。

会了这个算方案数是简单的。我们每次操作都会贡献 \(\frac{L(L + 1)}{2}\) 的贡献，这相当于一个完全背包，并且物品数是 \(\sqrt M\) 级别的。我们需要动态维护物品插入删除，这也是简单的。

Submission #68432624

牛客周赛 82 - D

弱智组合数学题。

但是我怎么把 998244353 打成了 1e9 + 7 喵？

牛客 2025 暑期多校第八场 F

看着很神秘的样子，显然要状压。会发现如果 \(S_{i, j}\) 为 \(i, j\) 相同的状态集合，那么 \(S_{i, j}\) 的子集都不合法，所以可以做一个高维后缀和（AND 卷积）。

然后这样卡不过去，考虑每个子集状态仅有 \(0, 1\)，用 bitset 优化一下就可以了。

P13712

签到题，发现每种操作最多执行一次，于是枚举一下即可。

P13713

写的时候糖了，一直在想 \(110110110\) 的循环，调了很久也才 85 pts。

最后发现好像直接 \(01010101\) 是不是就好了？

CF2129C1

操作限制 \(550\) 次所以相当于一次操作要确定至少两个。会发现 \(?)\) 可以确定一个，要确定两个必须同时知道一对 \(()\)。

不妨先二分出第一个使得 \(F(1 \sim i) > 0\) 的位置，则 \(S_{i - 1} = (, S_i = )\)。如果找不到说明 \(S_1 = ), S_n = (\)。

然后考虑随便构造一个可以同时判定两个的串即可。比如 \(?)()?)()()\)。

CF2129C2

发现没有利用好 \(k\)，所以优化一下 C1 构造的串，发现要让所有可能的答案互不相同，考虑二进制分解，则可以构造 \(?))?)())?)()())?)()()()())......\)。

由于 \(k \leq 1000\)，所以最多可以同时判定 \(8\) 个，可以通过。

CF2129C3

考虑继续优化，会发现每次每个 \(?)\) 都只和右边的 \(()\) 配对太蠢了，考虑左右都放一点 \(()\)。于是你会发现对于左边 \(l\) 个 \(()\)，右边 \(r\) 个 \(()\) 如果中间的 \(?)\) 合法那么会增加 \((l + 1)(r + 1)\) 个括号对。于是考虑令 \(l = 2^{\lfloor \frac{k}{2} \rfloor} - 1, r = 2^{\lceil \frac{k}{2} \rceil} - 1\)。这样最多一次可以判定 \(12\) 个括号，可以通过 C3。

确实是一个神仙题。

P13714

做法很多很多。可以神秘优化建图，还可以像标算三进制状压。

记录一个爆标做法，记 \(F_S\) 表示将集合 \(S\) 归位的最小代价，\(G_{S_0, S_1}\) 为将 \(S_0\) 集合都是 \(0\)，\(S_1\) 集合都是 \(1\) 的操作的最小权值。

发现 \(G\) 记不下来，但我们会发现我们只需要知道和 \(y\) 的关系，所以转而记 \(G_{0_S}, G_{1_S}\) 分别表示 \(or\) 和 \(and\) 操作中 \(S\) 中的位都和 \(y\) 相同的最小操作权值。转移可以枚举子集，时间复杂度 \(\Theta(3^n)\)。

P5492 [PKUWC2018] 随机算法

赛时的诡异做法。

首先最大独立集大小可以高维前缀和 \(\Theta(n2^n)\) 求。

然后考虑三进制状压，\(0\) 为没考虑，\(1\) 为选进独立集，\(2\) 为被独立集中的点排斥，设 \(F_S\) 表示取到 \(S\) 的概率。那么答案就是 \(1\) 的个数与最大独立集大小相等的 \(S\) 的概率相加。

直接做是 \(\Theta(3^n)\) 的烂完了，但注意到合法的状态很少，于是全部搜出来后再 DP 即可。

代码比较困难。

CF724E

根本想不到能用 DP 模拟最小割。

首先最大流模型很好建，然后考虑转化成求最小割。设 \(f_{i, j}\) 表示前 \(i\) 个点剩下 \(j\) 个与 \(S\) 连边的点，那么转移分为第 \(i\) 个点割和 \(S\) 的边和 \(T\) 的边。转移分为割连 \(S\) 的边或连 \(T\) 的边，如果割连 \(S\) 的边则要把与 \(j\) 个点的连边都割掉。

CF2128E1

显然要二分答案，但是不能直接二分能不能取到 \(v\)，一是没有单调性，二是没办法判定。

由于要求最大值，所以我们可以二分是否存在 \(\geq v\) 的中位数，这显然有单调性。判定的时候我们考虑一个经典 trick，令所有 \(< v\) 的 \(a_i\) 都为 \(-1\)，反之为 \(1\)，若存在区间 \([l, r]\) 的和 \(\geq 0\) 则存在中位数 \(\geq v\)。即 \(s_r - s_{l - 1} \geq 0\)，对于 \(r\) 维护一个最小的 \(l - 1\) 即可。

最后假设我们得到了最大的 \(v\)，那么我们只需要找一个区间和 \(\geq 0\) 的区间输出即可。但我发现好像没有人证明这个。

首先如果要判定一个区间的中位数恰好为 \(v\) 我们不只要判定以上情况。令 \(> v\) 的数的 \(b_i = -1\), \(\leq v\) 的 \(b_i = 1\)。设它的前缀和数组为 \(s'\)，则如果区间中位数恰好为 \(v\) 需要满足 \(s_r - s_{l - 1} \geq 0 \and s'_r - s'_{l - 1} \geq 0\)。

我们知道对于 \(v\) 来说存在 \(s_r - s_{l - 1} \geq 0\)，即区间内 \(< v\) 的数的个数不超过 \(\geq v\) 的数的个数，那么如果对应的 \(s'_r - s'_{l - 1} < 0\) 说明 \([l, r]\) 内 \(> v\) 的数的个数多于 \(\leq v\) 的数的个数，于是对于 \(v + 1\) 来说它也满足 \(< v + 1\) 的个数不超过 \(\geq v + 1\) 的数的个数，与 \(v\) 的最大性矛盾。

综上所述，我们只需要对于二分出来的 \(v_{max}\) 找一个 \(s_r - s_{l - 1} \geq 0\) 的区间输出即可。

CF2127E

挺有趣的题目。

看过去不太能直接 DP，所以先分析一下性质。贪心的想，设 \(u\) 没有染色，则 \(u\) 子树内如果只有一种颜色不同的点对，那么 \(c_u\) 就是这个颜色；否则如果有超过一种，那么 \(w_u\) 一定会加入答案，并且为了让向父亲走的点尽量满足答案，\(c_u\) 一定是染 \(u\) 子树中出现过的颜色。如果 \(u\) 已经染过色了也差不多的分析。

考虑对每个点 \(u\) 用一个 set 记录出现过的颜色，那么上述相当于一个 set 合并的过程。我们考虑直接启发式合并复杂度就对了。

这样做了后你会发现存在若干个子树结构内全部没染色，会发现我们一定尽量全染父亲的颜色，才能让父亲不算入贡献。

由于 set 还要带一个 \(\log\) 所以总复杂度是 \(\Theta(n\log^2 n)\) 的。

CF1763C

注意到当 \(n > 3\) 时我们一定可以通过操作将除最大值外的数变成 \(0\)，所以最后的值是 \(v_{max} \times n\)。

当 \(n \leq 3\) 时直接暴力讨论一下即可。

牛客周赛 R105

A

输出 lowbit(x) 与 x - lowbit(x)。

B

模拟

C

注意到一个格子不管是 \(0\) 是 \(1\) 都会同时影响到一行一列，换句话说只有 \(k\) 为偶数时有解。构造解考虑令若干个 \(a_{i, i}\) 为 \(1\)。

D

注意到只有两个 \(2\) 在一起可以造成 \(2\) 的贡献，否则造成 \(1\) 的贡献，于是贪心地放一下即可。

E

直接求没法做，因为异或不能分配。

考虑拆位，对于每个点 \(u\) 我们预处理出邻域中 \(0\) 和 \(1\) 的数量，然后分 \(u\) 是 \(0\) 或 \(1\) 计算贡献即可。

F

注意到首先我们构造的序列一定单调递减，其次前面的数一定是后面的数的倍数，即 \(f(i) = a_i\)。到这里直接 DFS 然后优化一下就过了。

精益求精一点，考虑 DP 设 \(f_{i, j, k}\) 表示前 \(i\) 个数 \(f(i) = j\)，总和能否凑出来 \(k\)，可以直接转移，按理来说进行一点小优化限制一下 \(k\) 的范围 \(O(n^5)\) 能过。