ABC Ex 选做

Deuteron · 2024-12-13 16:52:43 · 个人记录

杂话选说：

我会喷火，你会吗？

按照题号顺序进行排列。

ABC212H

求所有长为 n ， 1 \le a_i \le m 的序列中，有多少异或和为 0 的。n \le 2\times 10^5,a_i <2^{16} 。

暴力转移是显然的，考虑你转移实际上是不断与 b_i=1 做 FWT 的过程，但你显然不能做 k 次 FWT，你先把 b_i=1 的部分做掉，发现等价于 a_i 进行 FWT 之后对系数进行对应等比数列的变换后 IFWT 回来即可。

submission

ABC218H

有 n 盏灯，你需要让恰好 k 盏亮。若 i 与 i+1 颜色不同，获得 a_i 的贡献，求最大贡献，n \le 2 \times 10^5 。

不妨 x \le \dfrac{n}{2} ，考虑进行 wqs 二分，显然让 x 盏亮的贡献 f(x) 是凸的，应用 wqs 二分多加个权值，内层 dp 直接维护上次状态即可。注意区分到底选的是亮还是不亮。

submission

ABC219H

直接复制了原题面。

在一条数轴上有 N 支蜡烛，第 i 支蜡烛长度为 A_i，且位于数轴上的 X_i 处。

时刻 0 时，N 支蜡烛都被点燃。一根点燃的蜡烛每过一时刻就会减少 1 的长度。当长度变为 0 时蜡烛将会熄灭。熄灭的蜡烛的长度不会减少。

时刻 0 时，你位于数轴上的 0 处。一时刻中你可以在数轴上左右移动不超过 1 的单位距离。当你到达某支蜡烛所在的位置时，你可以选择熄灭这支蜡烛，熄灭蜡烛的时间忽略不计。如果有多支蜡烛位于同一个位置，你可以一次性熄灭该位置上的所有蜡烛。

求时刻 10^{100} 时最大的蜡烛总长度，n \le 300 。

大神题。考虑令 dp_{l,r,k,p} 表示当前处理到 [l,r] 区间的蜡烛，时刻为 k 当前走到左侧/右侧的最大长度，转移是简单的。但是带时间维肯定做不了，考虑优化，你发现这个过程等价于每过一个时刻减去没走过的且最终会被计入答案中的蜡烛数量，把这一维计入状态中，转移时枚举新的一位是否最终被计入答案即可。复杂度 O(n^3) 。

submission

ABC221H

给定 n,m，对于每个 1\le k\le N，求长度为 k，序列总和为 n，且每个数的出现次数不超过 m 的序列个数。n,m \le 5\times 10^3 。

考虑直接 dp 显然没前途，对于这种拆分数形态的东西，考虑进行添加 0 和全局加 1 的操作，对应的转移分别为 dp_{i,j}=dp_{i-1,j} 和 dp_{i,j}=dp_{i,j-i} ，容易证明这和直接 dp 等价。考虑有出现次数的限制时，这等价于第一种转移至多连续做 m 次，你额外记一个 f_{i,j} 表示钦定上次进行的为 2 转移即可。

submission

ABC223H

区间询问 q 次，每次查 a_l \dots a_r 中的数是否能异或出 k 。n \le 4 \times 10^5,q \le 2 \times 10^5,a_i < 2^{60} 。

线性基，首先什么 ST 表，猫树一类的肯定没戏，考虑你在线性基每一位记录 t_i 表示上一次被插入是什么时候，然后你查询在对应的 r 上只考虑 t_i \ge l 的即可。具体的，插入先复制一遍原来的，然后如果遇到编号更小的直接交换，不影响正确性。

submission

ABC228H

有两个长为 n 的序列 a_i ，c_i ，你可以付出 c_i 的代价将 a_i +1 ，最后再付出 kx 的代价，x 为 a_i 的种类数。求最小代价，n \le 2 \times 10^5,a_i \le 10^6 。

先放到桶上，最终的答案一定是分成若干段，将每段的数都移到末尾，可以列出 O(n^2) 的 dp 式。注意到 dp 形如 dp_i=\min(dp_j+s(j,i)) 的形式，考虑进行斜率优化，推成啥我也忘了，反正就是可以做。。。

submission

ABC236H

给定 n,m 序列 d_i ，求满足 1 \le a_i \le m，d_i \mid a_i 且 a_i 互不相同的序列个数。n \le 16 。

考虑容斥，令 dp_S 表示 S 集合的答案，转移枚举相等的集合 T ，方案为 \lfloor \dfrac{m}{\operatorname{lcm} a_i}\rfloor ，然后考虑容斥系数 V(S) 。显然容斥系数只与 |S| 有关，满足 \sum \limits_{t_1+\dots +t_k=n} (\prod V(t_k))=[n=1] 。可以直接枚举拆分数暴力去求，也可以打表发现 V(n)=(-1)^{n-1}(n-1)! 。复杂度 O(3^n) 。

submission

ABC237H

一个字符串 S ，你要选出尽可能多的回文子串，满足选出的串之间互不为子串。n \le 200 。

大神题。重要结论是本质不同回文子串不超过 n 个，考虑在末尾加入新字符时，若出现了两个新回文串，那么短的那个在长的那个上的对称一定已经出现过。对字符串随便哈希一下，将有子串关系的 x,y 建边，原问题等价于最长反链，即最小链覆盖，在 DAG 上又等于最小链划分，这是经典问题，可以转化为二分图最大匹配求解。

submission

ABC240H

给定一个长度为 n 的 01 串，求最多可以选出多少互不相交的子串，字典序严格升序。

大神题。首先考虑 O(n^2 \log n) 做法，将所有串拉出来在 trie 上排序，然后相当于要求 r_i < l_{i+1} 这样，类似于做 LIS，使用 BIT 维护即可。

接下来考虑首先每个子串至多比上一个长 1 ，而最终最多有 \sqrt{2n} 个子串，因此最长的子串也不会超过 \sqrt{2n} 。所以只需要将长度 \le \sqrt{2n} 的子串进行计算即可。复杂度 O(n\sqrt {n \log n}) 。

submission

ABC242H

复制了原题题面。

有 m 个小球，一开始标号为 1\sim m，每个对应一个区间 [L_i,R_i]。有 n 个方块，标号 1\sim n，初始时无色。重复以下步骤直到所有的方块都被涂色：

1. 随机拿出一个小球 i
2. 将 [L_i,R_i] 涂色
3. 将小球放回去

问期望进行步骤的次数。

• 1\le n,m\le 400,1\le L_i,R_i\le n

首先 min-max 容斥，转化为 \sum \limits_{S} (-1)^{|S|+1}E(S) ，其中 E(S) 表示 S 被第一次覆盖的时间，这只与与 S 相交的区间个数有关。令 dp_{i,j,k} 为选到 i 位，相交个数为 j ，|S| 的奇偶性为 k 的方案数，枚举上一个被选到的位置再预处理出这段区间内相交的个数进行 dp 即可。复杂度 O(n^3) 。

submission

ABC246H

定义一个 01? 字符串的权值为将 ? 任意替换为 01 后的本质不同子序列个数，q 次修改，每次求出修改后的权值。

奶龙题。令 f_i 表示以 0 结尾的字符串数量，g_i 表示以 1 结尾的字符串数量，则有

• f_i=f_{i-1}+g_{i-1}+1,g_i=g_{i-1}
• f_i=f_{i-1},g_i=f_{i-1}+g_{i-1}+1
• f_i=g_i=f_{i-1}+g_{i-1}+1

分别代表 01? 的转移。可以写成矩阵的形式，然后用线段树维护一下就做完了。

submission

ABC248H

给定排列 p ，求满足极差减长度 \le k 的子段数量。