AT 比赛场祭

littlebug · 2024-05-26 11:06:10 · 个人记录

喵喵喵~

abc355

A 水，判断是否出现加上一坨 if，过。

B 水，但是题意看了好几遍，才看懂是求 i，使得 c_i \in a 且 c_{i+1} \in a，于是就 O(n^2) 枚举 a 中全部元素，O(n) 枚举 c 的元素，n \le 100，暴力可过。

不过中间忘记 || (c[l+1]==a[i] && c[l]==a[j])，看了半天/kk

C 还是水，但是调了半天。统计行、列、对角线最大值，有一个 =n 的就输出。但是中间有一次不知道怎么了竟然认为行、列、对角线都要 =n，莫名其妙，然后又一堆奇怪的错误，导致 0:30 才 A 掉。

D 水，一眼二分了，非常板。

E 交互不会，跳。

F MST板子，但是好像要用 LCT，不会，摆了。

总结：虽然涨了点分，但是还是祭飞了，为什么你 E 要是交互啊喂？？？

讨厌，没看见 F 的数据范围 c_i,w_i \le 10。。。

abc356

A 水，STL 里 reverse() 一下就可以。

B 水，直接统计。

C 是一个爆搜，O(2^n \times m)，大概 3e6，开写，没想到竟然一遍过样例了/jy ，我爆搜之前光写炸的。

D 二进制玩意儿，因为是 \& 的 \rm popcount，所以考虑对于 m 的每个二进制位为 1 的分别统计，最后求和。设当前统计到了 m 的第 l 位，统计 1 \sim n 的第 l 位也为 1 的个数。则第 l 位的贡献为 ((n>>(l+1))*i)>>1，不过当 (n>>l)&1 为 1 时，需要额外加上 n-(n>>l<<l)+1，其中 i=1<<(l+1)。

abc357

糖丸了，就 AC3，掉大分。

AB 水，不写。

C 递归一下，每次将矩阵划分成 9 个区域，复杂度 O(3^{2n})。

D 想到等比数列求和，但调半天二分没调过，啊啊啊我竟然不知道等比数列求和公式，最后用公式写了，结果差一点就交上，赛后马上 A 了。/kk

E 图的形态好像是一个基环树，但当时想到基环树的时候已经只剩 10min 了，认为写不完就没写。/kk

abc358

A 水。

B 模拟一下即可。

C 爆搜，注意代码细节。

D 贪心一下，将 \{a\},\{b\} 排序后，从小到大枚举 i，然后尽可能地给每个人最少的糖果。

然后 EFG 好像都可做（最水的 G），不过我一会儿想做这个一会儿想做那个的，导致最后一道题也没过QwQ，以后必须读题之后要用心针对一个题了！

abc359

AB 水。

C 考虑将所有点都移动到所在矩形的左一半，然后分讨一下。设 xl,yl 为两点的 x,y 坐标差。

• 若 yl \le xl，那么先在 y 坐标上移动 yl 格（同时向 t 的 x 坐标上的方向移动），然后只在 x 坐标上移动即可，答案为 yl+ \lfloor \frac{xl-yl}{2} \rfloor，除以二是因为矩形的长为 2。
• 否则，直接在 y 轴移动，顺便就可以把需要在 x 轴上需要的距离移动了，因为在 y 轴上一格就是一步，所以答案为 yl。

D 写了写区间 dp，然后不会转移了，摆。

E 从 1 到 n 枚举 i。设 f_i 为坑 i 的答案。

• 如果 h_i 比 h_1 \sim h_{i-1} 都大，那么第 1 \sim i-1 个坑就必须使其高度和 h_i 相同，所以 f_i=i \times h_i + 1。
• 否则，要找到 i 之前第一个 \ge h_i 的位置，设为 last_i，那么 last_i \sim i-1 的坑就需要和 h_i 高度相同，而在 last_i 之前的可以用 f_{last_i}-1 转移过来，所以答案为 f_{last_i} - 1 + (i-last_i) \times h_i + 1。

然后用单调队列预处理出 last 数组即可。

arc180

只会一题，B/C 根本无思路。

A 考虑把字符串切开，因为相邻两个 s_i 和 s_{i+1} 若相同，则一定不会被消除，所以遍历一遍，每遇到一个 s_i = s_{i+1}，在 s_i 后面切一刀，分别计算每一段的答案，然后乘起来即可。这时，每一段的 s_l,s_{l+1},\dots,s_r 一定是 ABABABAB... 的形式，通过手打了一个表发现，若一段这样的字符串长度为 len，则答案为 \lceil \frac{len}{2} \rceil，然后就过了。

没了，摆，玩 florr 去（

abc360

A 看错字母吃了一发罚时/kel

B 有点逆天，读错题意一次，用了我将近 0.5h。考虑把 s 切开，每个 w 个字符切一刀，然后从上往下看，如果有一个完整的串严格等于 t，则 yes，枚举个 w，分别判断一遍即可。

C 开 n 个 vector，分别存 a_i 相同的 i 所对应的 w_i，然后每个 vector 保留一个最大值，其他的计入答案就可以惹。

D 好水，双指针 + 二分，把蚂蚁按照朝向（右 l，左 r）排序之后对每个 l_i，找可以与其碰到的 r_j 区间（=t 单位时间后在 l_i 左边的 - 最开始就在 l_i 左边的），加起来即可。

E 概率期望题，本身这种题我就没做过多少，柿子退不出来就摆啦！

掉分*2

abc361

哦哦哦我好厉害，abc 竟然过了 3 道题/cf

A 水题

B 逆天（最近 abc 光这样），先是写了个判断长方体 2 的 8 个顶点，然后 WA*2，摆了去搞 C，写完水的 C 之后翻犇发现 B 可以暴力，试着交了下，竟然过了/jy ，本地可是根本 T 飞的啊喵……

C 排序后，容易证明最后答案一定是一个连续的区间，所以暴力枚举每个可能区间记录最小值即可。

D bfs+状压，不过赛时没调出来/kk ，不知道为啥样例 #3 寄掉惹，然后就导致了我状压写魔怔想把某个人状压掉（？）的局面。虽然不知道不用状压行不行吧……

然后感觉 E 和 F 都可以做出来（事实上确实可以），不过还是时间问题，下次我决定了，过掉 A 之后从 F 往前倒序开题！最近 abc 好像是整体难度没变，但是简单题变 ex 惹，难题变简单惹。

补 E，首先如果答案需要是一个回路，则需要将每条边走 2 遍；于是在不是回路时可以有以某个点为根的两条链只走一次，也就是树的直径，于是答案为树的边权和 \times 2 减去树的直径。

补 F，因为样例 #2 中 b=2 的个数为 (10^9)^2，所以 b \neq 2 的个数只有 1003332 个，所以可以暴力枚举出 b \neq 2 的个数，然后加上 b=2 的个数（\lfloor \sqrt b \rfloor）即可。不过 ex 的是，快速幂会炸 ll，而且 sqrt() 的精度还有问题/kel ，而且用 sqrt() 样例 #2 还可以过……所以只能手写个开方向下取整惹。

abc362

AC*3，棒（

由于倒序开题。

F 推了大概 10min+，不会。

E 考虑 dp，用 map 离散一下公差，设 f_{i,j,k} 表示结尾为 a_i，长度为 j，公差为 k 的等差序列个数，则可得转移方程为

C 贪心。

D 一大堆做法，我用的是并查集，大概还可以 set、十字链表、暴力用数组存（？）

做法是在四个方向分别开一个并查集，维护每个点向每个方向能看到的第一个点。不过因为一堆rz错误调了半天（/dk

不过 E 一眼了（其实 D 也是，不过仅限于一眼解法），所以……

为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？

/fn

abc371

再也不做 abc 的 ABC 了，原因：懒太恶心了

D 离散化一下，建个线段树求和，然后 WA 了，不知道哪里错了。

E 先假设全部元素都不同，方案数为 \sum \limits _{i=1} ^n (i \times (n-i+1))。考虑每两个相同且中间没有相同元素的元素（就是 \dots , x , {\color{red} \dots} , x , \dots，其中 \color{red} \dots 里面没有 x）对答案的影响，也就是包含这个区间的方案数，设两个元素的位置为 l,r，则方案数为 l 左边区间的长度 \times r 右边区间的长度，即 l \times (n-r+1)。开个数组记录该元素上一次出现的位置即可。

abc372

D 单调队列板子。

E 因为 k \le 10，所以暴力并查集维护前 10 大即可。

F 没想出来，想到 dp 但不会处理环。

G 是 半平面交 + 类欧，紫 + 紫（虽然据 dalao 们所说的，好像到不了黑），NOI 级算法不会呜呜呜/dk

abc378

F<E

D 简单爆搜。

E 看了看，似乎可以通过移动 r 来求出所有对应的 l 的答案（？但是没想出来。

F 由于环上每个点的度数只能为 3，所以度数 >3 的点先踢出去。

容易得出结论，点对 (u,v) 合法当且仅当 u,v 的度数都为 2，u \leadsto v 上的点的度数都为 3。所以考虑一个类似树形 dp 的方法统计答案。设当前 dfs 到的结点为 u：

若 u 能和 u 的祖先形成合法点对，则答案 +1，这个可以在 dfs 过程中记录上一个合法点（度数为 2 且到 u 的路径上的点度数都为 3）实现，不过因为要求构成的图是简单图，所以不能有重边，即 last = ufa 时不记录答案。

这样计算完了两个点互为祖先后代的情况，然后考虑两个点分别在 u 的两个子树内的情况。设 nxt_u 为在 u 的子树中可以从 u 开始到达的度数为 2 且 路径上所有点都为 3 的点的个数。显然这个是可以 O(n) dp 的。然后就好求了，乘法原理把每两个子树匹配一下即可。

WA × 15（悲

补 F，换了一点点思路（第一种情况根据 u 和 nxt_i（i 为 u 的子节点）统计）过了（）

补 E，考虑先转为前缀和形式 s_r - s_{l-1}。因为 s_i 可以取模，所以当且仅当 s_{l-1} > s_r 的时候答案需要 +M，然后拿 BIT 维护逆序对即可。

G 要用杨表，不补了。

天依可爱！

abc379

切了 AB 之后开 C，结果写假了，吃一发罚时，然后还是没思路，跳。

开 D，想了想也不会。

开 E，本来想写个高精，结果发现复杂度爆了。

回去看 D，嗯，维护一个偏移量即可，过了。

看 C，发现可以从后往前遍历，记录每个需要填空的区间，贪心一下，然后交上去 WA × 3……搓了几个样例发现都没问题，然后就去看 E 了。

但是 E 还是不会，开 F。

发现 F 水啊！把询问离线下来，从左到右维护一个单调队列，每次可以得到 r 后面能看见的数，而 l 能看见的一定包含于 r 能看见的，又因为 l 不能看见某些数当且仅当 (l,r] 内有大于这个数的数，所以用个 ST 表维护区间最大值，然后因为单调队列是单调的（废话），于是二分即可。

然后就赛时没写完，虽然赛后提交了一发也 WA 就是了（）

补 F，死因：把 a[n] 写成 n。

补 E，考虑统计每一个数位在不进位的时候得数是多少，可以选一个较小的 n 手动模拟一下，然后就出结论了。设输入的数从左往右为 a_i，设 s_i 表示 \sum \limits _{j=1} ^i j \times a_j，相当于给每个数赋了一个等于其下标的权的前缀和，则答案为 \sum \limits _{i=1} ^n 10^{n-i} \times s_i。求出每一位之后进行一次进位即可。

补 G，考虑按照从上到下，从左到右的顺序填数，因为 n \le 14（假设 n \le m），所以可以状压 dp，这时对 (i,j) 有影响的只有 (i-1,j) 和 (i,j-1)，所以可以把 dp 数组滚一下，只留最后 m 个数即可，用只 umap 存。转移是容易的。

天依可爱！

abc380

经典调！线！段！树！调！不！出！来！

难度降序 D>E>F

C 数组越界罚时 ++

D s 可以看做一个整体，不重要，假设 s 只有一个字符。考虑 [1 , 2^k] 和 [2^k+1 , 2^{k+1}] 的字母是正好大小写反转的，于是可以按照 2^{now} 从大到小把 k 降到只剩 0/1 并求出反转次数即可。然鹅赛后发现这玩意一个 \sout {\rm popc} 就可以解决……

E 线段树维护相同颜色段，打懒标记，出现次数是在每次 update 的时候统计的，不过细节巨（？）多，额也可能是我实现的原因，需要分左右两边 update，还要处理区间包括 x 的情况……

补 E，嗯，的确是麻烦了，啊啊啊原来一只 dsu 就解决了，赛时怎么没想到/dk ，这 dsu 板子题呀喵

补F，可爱博弈论，一看数据范围，啊？爆搜？还真是（

补 G，可爱期望，考虑对于一个长度为 k 区间期望逆序对数是多少。设不改变时逆序对数为 sum。因为将 [l,r] 打乱之后把原序列划分成了 3 个区间 [1,l-1],[l,r],[r+1,n]，而这 3 个区间两两之间不影响，所以只需要计算 [l,r] 的期望逆序对数就可以了。因为任意两个数构成逆序对的概率为 \frac 1 2，所以长度为 k 的区间的期望逆序对数为 \frac 1 2 \times C_n^2 = {\displaystyle \frac {k \times (k-1)} 4}（设为 t）。设 [l,r] 内原本逆序对数为 now，则答案为 sum - now + t，sum 和 now 可以 BIT 维护。对于每个区间这样统计答案之后求平均数即可。

天依可爱！

abc381

还是只会四题 /cf

这场出题人有点魔怔。

A 11/22 String
B 1122 String
C 11/22 Substring
D 1122 Substring
E 11/22 Subsequence
F 1122 Subsequence

D 就是分奇偶性把所有连续段（满足 a_{2i} = a_{2i+1}）拿出来放到一个 vector 里，对于每个连续段统计答案，每次检查上一次出现的这个数在哪里即可，但是细节问题罚时 +=2。

EF 根本没思路。

补 E，因为要求一个最大值，然而直接做不好做，所以考虑二分，二分 / 一侧的数的个数，于是只需要检查在 [L,R] 内是否存在由 x 个 1，1 个 /，x 个 2 组成的子序列即可，这个是容易的，预处理 1,2,/ 的每个位置，从 L 开始贪心就行了。

补 F，由于 a_i \le 20，所以考虑指数级算法，发现答案最多为 40，于是可以状压 dp，设 f_{S} 为选了集合 s 时对应的最小子序列右端点（虽然我也不知道怎么想出来的，但似乎可以从贪心的角度思考），则枚举 S 的每个子集 T，满足 S 中元素在 T 中只有一个不存在，然后在 T 的右边拼上这个元素即可，具体地，在 T 的右端点右边贪心地找两个该元素，使得右端点最小，这个过程可以预处理 nxt_{i,j} 表示位置 i 后面第一个元素 j 在哪里。设 S - T = \{i\}，则 f_S = nxt[nxt[f_{T},i],i]。dp 过程中时统计答案即可。

G 是黑题。

天依可爱！

abc382

D 爆搜。

E 期望状物，没读懂样例（悲，所以 20min 果断跳。

F 一眼了，自底向上依次下落，用个线段树维护区间最小值，支持区间平推，每次下落询问区间内最小值就是答案，然后再将区间最小值更新。写错一点细节导致罚时 ++。

摆的最早的一次，但 E 是真的理解不了。

补 E，dp！设 f_i 为获得 i 张稀有牌的期望开包次数，考虑枚举新的一包牌中的稀有牌数量，则 f_i = 1 + \sum \limits _{j=0} ^i f_{i-j}g_j，其中 g_i 表示开一包可以获得 i 张稀有牌的概率，但是这样因为两边都有 f_i 所以没法转移，于是考虑把右边的 f_i 移过来，得到 f_i = \frac 1 {1-g_0} ( 1 + \sum \limits _{j=1} ^i f_{i-j} g_j )。可以在 O(nx) 内转移。

然后求 g，发现直接做不好推，所以考虑加一维状态，设 h_{i,j} 表示在一包牌中选前 i 张，有 j 张牌是稀有牌的概率，分讨当前牌是不是稀有牌，则 h_{i,j} = p_i h_{i-1,j-1} + (1 - p_i) h_{i-1,j}。于是 g_i = h_{n,i}。

• 2 \times 10^k
• 3 \times 10^k + 32
• 4 \times 10^k + 40
• 8 \times 10^k

毕竟范围比较大嘛，所以全都判一遍是否满足条件就可以了。

不过 clang 能过，GCC 神秘 WA 掉的代码 ++

天依宝宝可爱！

abc390

只会 3 题 > <

B 开始寄了一发，不知道哪错了。后来在 DE 搞不出来的时候，发现是 eps 被卡了。于是耗时 67min 才过 B。

D 打了个爆搜，剪了点枝卡了点常但是还是寄了。

E 看起来像背包，不会。想到二分答案，但是发现解法的复杂度依赖于 a_i，于是假了。

补 D，考虑如何不乱搞地剪枝，可以将问题转化为把一串数任意放到 n 个格子里。挨个枚举显然有一大堆重复算的，所以不妨钦定 a_i 只能放在 1 \sim i 号格子里，于是只有 n! 种方案，但是这已经 4e8 了，还要用 uset 计数，一定会 T 飞。于是考虑继续剪枝，发现当 a_i 以前选的数都集中在前面几格时，后面几格都是 0，于是 a_i 会多次填到为 0 的格子里，造成了重复计算，所以枚举的时候，前后两个格子都是 0 就直接 break 即可。

发现在 uset 中 splitmix64 没有原版 hash 跑的快，splitmix64 跑了 1836ms，而原版 hash 只跑了 1439ms，当然这是在用的 clang 下测的，GCC 更慢。不过却发现 GCC 的 umap 比 clang 的 umap 跑的快（

补 E，嗯，很好的啥都想到了，就是没想到 01 背包（甚至还是个 01 背包裸的板子）。然后甚至连二分都不用，直接枚举 2 种推第 3 种就行了。

补 F，可以看出 f(L,R) 相当于把 a_{[L,R]} 中的数丢到一个数轴上，求连续段个数，然后就不会了。这时候需要有一步转化，连续段个数就相当于满足 x \in a_{[L,R]},x+1 \notin a_{[L,R]} 的 x 个数，然后就能做了，从 1 到 n 这 n 个数分别计个数即可。计数部分考虑统计一个数 x 可以「控制」的区间，即上一个 x（防止重算）或 x+1 到下一个 x+1，乘法原理即可。

arc191

A 挺简单的，n \ge m 直接贪心。n < m 则 1 \sim n-1 直接贪心，然后 s_n 一定可以选 t 中最后一个还没选的（设为 a），而如果 a 后面有已选中的字符（设为 b），则可以通过操作时将 a 与 b 应该交换的 s 中的字符 交换，实现不改变 s_n；也可以通过类似的方式使得 t 中的一个未选中的字符与 s_n 交换。

然后就 WA*7，不知道错哪，于是跳之。

B 不会，只能推出来 x 的取值范围，因为 x \bmod n \le x，于是 x \oplus n \le x，于是 x \ge n；又因为 x \bmod n \le n，而如果 x 太大，异或上 n 之后一定 > n 了，所以 x 可能的最大取值为 2^{n \text{在二进制下的最高位} + 1} - 1（也就是一堆 111），后面不会做了。

最后才发现异或可以拆开，a \oplus b = a + b - (a \& b)，于是简单推下式子可以得到 x \& n = n，做完了。

补 A，发现自己想多了。可以先按理想情况做，判一下如果 t 最后一个还没操作就把它放在末尾。然后没了。

不过 WA*8，讨厌字符串，细节过多，不补了。

天依宝宝可爱！

abc391

省流：赛后 43s 过 F。

D 考虑每一列自底向上的第 i 个一定是同时消失的，所以用这个来计算一个方块消失的时间，注意如果一行不能构成 w 个，那么之后的就都没法消失了。猜了个结论：一“行”（上面的定义）方块从上面掉到底下只跟它的高度有关，好像挺对的，没举出反例来就这么写了。

然后 WA*20，可能是猜错了，但不知道错哪，跳之。

E 一眼了，递归处理每个 [i,i + 3^k) 即可，不过我的写法码量有点大，写了 20min 左右一遍过了。

这时候只剩 10+min 了。

F 更一眼了，优先队列维护即可，但是忘记判 vis 硬控我 2min，结束前 1min 想到，于是没写完。

然后就有了上面的悲（？）剧。

总结：本场 abc F<E<D。

补 D，拼尽全力无法战胜。不过在 @wusixuan 大佬的帮助下过了，死因：忘记按照 y 自底向上排序，唐诗了。

补 G，原题是 P4590 和 P10614。dp 套 dp 典题。考虑算 LCS 中的那个 dp：

设 g_{i,j} 为 s_{1 \sim i} 与 t_{1 \sim j} 的 LCS，有转移：

g_{i,j} = \min (g_{i-1,j} , g_{i,j-1} , g_{i-1,j-1} + [s_i = t_j])

可以发现，每个 g_{i,j} 与 g_{i,j+1} 要不相等，要不后者比前者多 1，于是对于 g_i 进行差分后可以得到一个只包含 0,1 的数组，同时原数组和差分数组构成双射关系，于是直接转换是可以的。这个 dp 还有一个性质就是，如果要求 g_i，只需要知道 g_{i-1}、t 与 s_i 即可。

然后考虑设计状压 dp。设 f_{i,s} 为长度为 i，与模式串 b 进行 LCS 的 dp 所构成的 g_{n} 的差分数组为 s，的方案数。那么转移就是显然的了，先从小到大枚举 i，然后枚举 s，然后考虑下一个位置填哪个字母即可，再现场把 g_{i+1} dp 出来，设得到的差分数组为 t，那么则有转移：

于是这样做就可以了。

统计答案的时候，一个 s 所对应的 LCS 长度显然就是 {\rm popc}(s)。

需要注意两个优化剪枝，一是可以把 f_{i,s} 为 0 的状态直接剪掉，因为这部分起不到任何作用；二是可以把每个 s,c（s 为差分数组，c 为在末尾加的字符）在 LCS 的 dp 后对应的 s' 预处理出来或者记忆化，避免重复做同样的事。

于是 3 紫 + 2 紫题解，水之！

天依宝宝可爱！

abc394

近几个月第一次过 5 题（）

F<<<<<<<<<<<<<<<<E

D 忘记判空次一发罚时。

E 想了很长时间没思路，然后想到了双向 bfs，写了，WA 了，调半天没调出来。

剩了 10min+，去看了看 F，发现竟然一眼了，树形 dp 板子，然后 10min 切了。

早知道先开 F 了啊啊/fn

补 E，发现赛时做法的死因就在那个 \times 2 + 1 上，因为每次取 \min T 了于是改成第一次 bfs 到就记为答案，但是这样是错误的，因为有可能第一次 bfs 到时 \times 2 + 1，但是后来有更优的只 \times 2 的方案。

于是参考官解，把这个过程反过来做，先把每个点与每条边入队，然后由此向外扩展，就有效地避免了上面的问题。

天依宝宝可爱！

abc395

依旧过 4 题。

D 一开始想用 set，但是发现假了，然后想用可撤销 dsu 状物，然后在 dsu 板子上改了半天发现好像不是 dsu 了，但是好像挺对的，开了 3 层点，最底下一层是每只鸽子，上一层是鸽子对应的原本的笼子，第三层是每个笼子在 swap 后所对应的真实笼子……

喜报：场祭写到这里的时候突然发现 D 错哪了然后过了（）

……然后记录一个 t_i 表示第三层对应的第二层的点，操作二在第三层找点 x,y，对应到第二层 t_x,t_y 之后对于这两个点进行重新连边。操作一直接第一层向第二层连边，然后这里错了，应该是先从第三层找点，然后 x 的边连到 t_y 上。

说句闲话，看到 t_y 想到了天依。

E<<<<<D。考虑建正反边并标记，然后跑 dij，并对于一个点分开算当前状态是正还是反的最短路，即 dis_{u,0/1} 表示 1 \leadsto u 且到达 u 时是正 (1) / 反 (0) 状态的最短路，后面就是 dij 板子了。

剩 20min 看了 F，想到了二分，但是不会。

abc396

好像是第一次过 6 题喵 > <

不过

好的那没事了，原来一道评蓝的也没有呀（）

E 一眼图论题，建图 u_i \xleftrightarrow {w_i} v_i，w_i 表示 u_i 和 v_i 上填的数需要构成的异或和。考虑确定一个点 u，然后 bfs 算出每个点需要和 u 异或的数 b_i，顺便可以判当一个点对应两个值的时候就无解。然后把每个 b_i 按照二进制位拆开，按位统计一下，贪心地，1 多就在 u 上填 1，反之亦然，设这样得到的数为 x，答案 a_i 就为 x \oplus b_i。

不过刚开始看错题意罚时 ++

然后忘判图不连通罚时 ++

然后发现 F 好像很简单，拆成每次整体 +1 的操作，注意到一次操作时变化的数只有操作后刚好 =m 的数，设这个数为 a_i，则显然 a_i 和它后面的每个 \ne a_i 的数都形成了逆序对，且这些逆序对在操作后消失；a_i 和它前面的每个 \ne a_i 的数都没有形成逆序对，不过在操作后会形成。于是，答案的变化量就可以算出来了，均摊 O(n)。

G 没看，不过我相信自己即使看了也做不出来的。

补 G，嗯题解看不懂，不补了。

天依宝宝可爱！

abc397

4 题。

A 手滑敲错，没测样例就交次一发罚时！

D 想到的是预处理完全立方数，然后二分，但是交上去之后，发现好像可以炸 __int128，卡时无效，跳了。

E 好像一眼了，但是树形 dp 的细节有点多，调了一会儿。具体地，从底向上贪心（或者叫 dp？），遇到长度 =k 的就砍掉，然后对于一个 u 判一下她叶子结点的长度情况，能通过 u 连起来的直接连起来，最后如果有连不起来的就无解。

F 想到了只出现一次贡献一定为 1，然后把长度 >1 的都转化成区间（左端点为第一次出现的位置，右端点为最后一次出现的位置），求最大区间覆盖，其中区间中的数出现 2 次的区间贡献为 2，>2 的贡献为 3，看起来挺对的，但是剩 2min 写完却发现 >2 时还要判区间覆盖过程中选择的区间是不是一定没划分成了 3 份，例如样例 #2 的那种情况就不能。于是没时间写了，虽然看起来好像也不怎么对吧。

补 D，哦哦初中数学题，但是初中数学也是数学，所以不会。

首先：

于是设 d = x-y，那么 d | n，但是这样直接枚举是 O(\sqrt n) 的。

不过注意到：

于是 d 是可以 O(\sqrt [3] n) 枚举的。

然后：

于是只需要检查关于 y 的方程 3dy^2 + 3d^2y + d^3 = n 有没有正整数解就可以了，可以二分解决。最后答案为 (d+y,y)。

当然，由于【】的出题人卡了精度，所以要增大二分边界，但是会炸 ll，所以考虑因为 d|n，所以原方程两边同时除以 d，可以转化为 3y^2 + 3dy + d^2 = n/d，这样就能把二分边界开到 1e9 了。

补 F，线段树题。考虑先确定一个点，假设确定靠右的那个点，于是只需要求把左边这一块划分为两个子串的最大贡献即可。

设选定的右边的点为 i，左边的为 j，原序列划分为 [1,j],(j,i],(i,n]，那么可以注意到在 i \gets i+1 的时候，对于每个 j，其产生的贡献的变化量是容易确定的。具体地，如果设 pre_i 为 a_i 上一次出现的位置，那么只有在 j \ge pre_i 的时候，i \gets i+1 才会产生 +1 的贡献，否则没有贡献变化。然后发现这个东西可以拿一个线段树维护，就做完了。

G 是网络流。

天依宝宝可爱！

abc398

不会读题怎么办？/dk

D 开 set 维护所有烟雾的位置，然后全局维护一个偏移量即可。

E 交互题。看起来像个二分图，但是它是一棵树，所以统计距离 \ge 3 且为奇数的点对，塞到一个 set 里即可。然后想来想去没想明白哪里来的必胜策略，毕竟这些构不成奇环的点对都是相对独立且不相互影响的啊，这结果不就是固定的嘛……然后这么打了，结果只过样例（）

跳了。

F 字符串题，首先想到 hash，但没发现可以做，于是在用 KMP 去乱搞，发现通过某种奇怪的方式，可以通过样例和手搓的样例，于是这么交了，然后 WA 了。

没了。

补 E，死因：没注意到题面中说了可以选择先后手，它说了好几遍我都没发现唉……真的糖丸了啊啊啊啊啊啊…………

补 F，嗯很好的 hash 可以做，每个字符随一个值，然后维护个前缀后缀和，每个位置就可以 O(1) 判了。

糖。

天依宝宝可爱！

abc399

E<<<<<<<D

D 看起来挺简单的，开个 map 维护 (a,b) 出现的位置就可以了，但是因为各种不知名原因挂了 4 发，于是跳了。

E 嗯可做，考虑把 s_i \to t_i 看成限制，首先如果两个相同的字符对应不同的字符，那么一定无解，这个判下出度即可。于是最后就剩下了一个基环树状物，考虑到对于一个环可以通过加一个外部点的方式来断环成链，这样操作数 +1，如果没有外部点（t 中不存在的点）就无解。

然后 WA 了。

发现如果一个环的某个点 v 有其他入边 (x,v)，那么可以通过第一步将 v 在环上的上一个点 u 向 x 连边（操作），从而不花费额外的操作数完成对环的操作。

过了。

然后发现是原 P9013，甚至还一模一样……逆天的。

开 F，尝试二项式定理展开，但是发现好复杂，于是回去改 D 了。

D 改了个 if 条件的位置，然后就过了（？

补 F，设 s 为前缀和数组，推柿子：

然后这里是赛时没想到的，因为 s_{l-1} 有个 -1 不好处理，于是考虑 l \gets l-1，然后就好做了。

发现最后一个 \sum 可以前缀和，所以总复杂度 O(nk \log k) 做完了。

天依宝宝可爱！

abc401

不过为什么 bitset 改一点就会出现神奇的 RE 信息呀呜呜/kel

D 字符串题，不可爱，特判了一大堆才过。

E 第一眼是 dsu 维护与连通块相邻的点，但是写了写发现有一堆小点在开始连不上时，复杂度会退化到 O(n^2) 左右。然后想用 bitset，调了 6737151min 然后……RE！

最后 10min 看了 F，发现一眼了，换根 dp 出以每个节点为端点的最大长度，然后枚举 T_1 里面的点，二分一下哪些 T_2 中的点选直径哪些选新边就行了。这时候以为是假的来着，然后赛后发现就是正解……

呜呜呜早知道先开 F 了/dk /dk /dk ，下次一定 EF 同时看再决定开题顺序了/kel

补 F，其实「以每个节点为端点的最大长度」可以直接用 \max({\rm dist}(u,x) , {\rm dist}(u,y)) 求，其中 x \leadsto y 是直径，显然根据直径的定义，这个东西是成立的。

补 E，题目提示我们要用 set（雾。可以发现我们只关心与 1 所在的联通块有边相连的点是哪些，于是想到可以拿一个 set 维护这些点，每次加点的时候看看加的点是否在 set 里面，如果在就用这个点更新 set，最后答案就是 set 的大小，是否有解判一下被更新的点的个数就可以了。

不过需要注意，每次更新的时候都要考虑编号 \le 当前点的点是否可以更新。而且这样复杂度是对的，因为只遍历编号 \le 当前点的点，所以有效避免了多余的判断。

G 是最大流。

天依宝宝可爱！

abc402

D 瞪了 5min，看了样例之后才发现是判平行，显然 x_i + y_i = x_j + y_j \pm n 就是平行的，减去这个即可，但是 WA 了，10min 发现不了哪里错了，跳。

E 爆搜，但是由于期望不怎么会，浪费了点时间。

F 一眼 meet in the middle，写写写，过样例了，然后 T 了……发现没有标记 vis，改了一下还是 T，摆了。不过我 4e7 为啥会 T 呀……

补 F，哦原来是统计的时候，可以直接二分 < x - m 的最大 y 呀，于是把 vector 换成 set（据说可以去重），然后就不 T 了。

但是 WA 了，无论怎么改都是 WA 3 个点，不调了扔了 www

补 D，数组开小！/fn /fn /fn

G 只有 5 人过了，大概率是黑题。

天依宝宝可爱！

abc404

上大分了耶 > <

E 一眼看出来了贪心策略，然后发现这个 O(n \log n) 就可以做，但是因为 n \le 2000 觉得做法可能假了，但是看起来挺对的，于是这么写了然后过了（？具体地，显然一个位置有几个球都是等价的，于是从后往前贪心，对于 a_i > 0，尽量往 a_j>0 的位置转移，如果没有则往 j 能达到左边界最靠左的位置转移。

G 可以看出是多个 p_{r_i} - p_{l_i-1} = s_i（p 为 a 的前缀和数组）的限制条件，所以直接差分约束就好了，不过忘记每个元素都 >0 耗了点时间。

天依宝宝可爱！

abc405

E 由样例 #1 解释，得出当 a,b,c,d 都为 1 时，只有 ABCD、ABDC、ACBD、BACD、BADC 这 5 种情况合法，注意到 A 一定在左边的两个位置，D 一定在右边的两个位置，B 在前三个，C 在后三个。

推广到多个数，可以发现 A 和 D 一定是无交的，所以考虑设最后一个 A 的位置为 i，第一个 D 的位置为 j，那么就可以划分为三个部分，[1,i] 全为 A B，(i,j) 全为 B C，[j,n] 全为 C D，且每个区间内任意排列。

显然这样可以不重不漏，抛开复杂度不谈，答案即为：

但是枚举 i,j 的复杂度是 O(n^2) 的，本来想化简来着，但是推了老半天柿子没搞出来，然后发现直接从组合意义角度考虑就行。可以发现当 i 确定时，后面两个部分的 B D 是有序的，所以直接算 C 在哪些位置，然后方案就是唯一的了，所以答案就成了：

开 F，显然可以转化为给定一堆左端点严格递增的区间，每次询问一个与上面区间没有相同端点的 [l,r]，求与 [l,r] 相交的线段条数。发现首先可以维护差分处理出来经过每个位置的线段个数，这样把左右端点的个数加起来，就得到了相交和被包含两种关系的数量之和。然后用个 BIT 维护一下，就可以被包含的数量。

但是样例 #2 一直不过……不知道为什么 qaq

补 F，查出来了！死因：把一个 m 写成了 n……足够逆天的。

但是怎么还是 WA 的呀……

诶怎么换成统计 [l,r] 内的点数，然后减去包含的区间就过了……

所以到底为啥呀？/kel

G 是莫队。

天依宝宝可爱！

abc406

4 题喵。

C 分别预处理 nxt_{0/1} 表示下一个满足 a_{i-1} > a_i < a_{i+1} 和 a_{i-1} < a_i > a_{i+1} 的位置，然后对于每个 i 满足 a_i < a_{i+1} 的可选区间的 l = \max(nxt_{0,i+1} , nxt_{1,i+1})，r = \min(nxt_{0,l+1} , nxt_{1,l+1})。注意到第一个限制条件实际上是没用的，因为满足第三四个限制条件的时候长度至少为 4。

E 一眼数位 dp，但是没调出来，跳。

F 一眼树剖，但是再次出现神秘 RE，不会了，话说 exitcode 4 还是第一次见呢。

补 E，死因：忘记判 j 为负的情况，显然这时候是很奇怪的，于是在 j = 0 时直接返回 (0,1) 即可。

然后 T，发现当 j > i+1 时，可以直接返回 (0,0)，似乎剪枝效果非常非常非常非常非常非常大。

怎么感觉评测姬在嘲讽我 /fn

F 死因：忘记输入 q！

G 是铜牌。

天依宝宝可爱！

abc408

糖丸了。

D 思路是枚举中间点，两边分别判断全设为 0 还是全设为 1 最优，用前缀和预处理下 0,1 的个数。但是 WA*23 不知为啥。

E 不会。

F 注意到一个状态转移到它能转移的状态中最高的那个是最优的，所以这样建个 DAG 然后找最长路径即可。卡在对于一个 1 分别求左边右边能转移到的最高的位置上了，一开始想的是 BIT 浪费了不少时间，最后发现 set + 二分就可以。

但是最后没调出来，set 不知道哪里错了。

于是就过 3 题qwq！

补 F，死因：set 存的是 pair，所以二分中 second 应该注意取值，uppb 应该取极大值而不是极小值。

然后还有个小错误，就是多个数相同的时候不应该只取最左边或最右边，应该两边都取，不然无法处理形如 2 2 3 1 的情况。

这样少了一个 WA……诶不对……a_i 是 1 \sim n 的排列啊……？

调不出来了不调了。

补 D，注意到把 [l,r] 都变成 1 的代价为 c_r - c_{l-1} + d_n - (d_r - d_{l-1}) = d_n + (c_r - d_r) - (c_{l-1} - d_{l-1})，其中 c 是 0 的个数的前缀和，d 是 1 的个数的前缀和。所以确定一端求另一端最值就可以了……

补 E，需要运用一些我没有的东西（脑子）。

注意到最小的路径按位或和 就相当于 最小的 x 满足 1 \sim n 存在一条路径上面的权值或和 \le x。于是考虑贪心，首先 x = 2^{30} - 1 一定满足条件，然后从大到小遍历每个二进制位依次判断是否可以删除就可以了，这个可以类似最小生成树做。

G 是 P5179，题解区说是类欧。

天依宝宝可爱！

abc409

A 一发 B 两发也是没谁了。

D 简单贪心，l 选第一个 a_i > a_{i+1} 的 i，r 在上面的基础上，选第一个 a_j > a_l 的 j 即可。

E 注意点叶子结点上的电子数 a_i 无论是往其父亲转移还是父亲往它转移，总会走连向其父亲的那条边，且正好有 a_i 个电子用这条边转移。所以不妨直接往父亲转移，这样显然不会更劣，转移完成的叶子结点就删掉，会发现又得到了新的叶子节点，就这样类似于拓扑排序的做即可。

F 没看见 n,q \le 1500 硬控 10min，导致赛时没调出来，实际上就是 STL + dsu 的简单应用。

但是 set 被卡了，必须用 priority。实名怀疑出题人的目的就是为了让大家知道 set 很慢，priority 很快。

以后能用 priority 的再也不用 set 了/ll

set 2000ms+ T 飞，priority 只跑了 208ms（（

G 需要用到 FFT。

天依宝宝可爱！

arc200

A 一点思路没有。

B 考虑乱搞，随便拍一些大质数上去，再乘上一些 10 来应对 lcm，然后 WA*2。

补 B，降大智/ll

无解是容易的，故只考虑有解的情况。

注意到如果 a + b = c，那么 a,b 互质是一定能构造出方案的，而互质不一定必须是质数，只要 gcd 为 1 就可以了。因为 10^k 的因数只有 2,5，所以只要让两个数中一个只有 2,5 两个因数，另一个没有就可以了。具体地，可以选择 8 \times 10^{a-1} 和 8 \times 10^{b-1} + 1 这两个数，显然满足条件，而且两个 8 相乘一定能足够进位。

然后是 a + b > c 的情况，扣几个 10 出来作为公因数就可以了，不过同时要注意不要让其它的 2,5 因数混进来。具体地，a 可以取 10^{a-1}，b 为了不包含多余的因数 2,5，可以取 10^b - 10^{a+b-c-1}，这样显然不会产生进位（因为是 1 \times \ldots）。

补 A，这个真的想不到了，不过想到了之后会很简单 xd

天依宝宝可爱！

abc412

412 是阿绫生日，不知道能不能活到 abc712。

3 题哦哦哦！

C 连续两次看错题意并且还都写出了解法（）

D 暴力寄了，没过样例。

E 本来以为是区间内素数个数，写出来才发现假了。

以后再也不 不手动模拟一下样例就去写代码了/ll

天依宝宝可爱！

abc415

C 暴力状压 dp。

D 第一眼看上去是数学题，还是数论，于是直接跳了。赛后才发现是极简单的贪心（）

E 直接 dp。不明白为什么那么多人去写二分。

F 好水，线段树维护即可。不过实现原因导致我的 pushup 又臭又长，调了挺久的。

补 D，气气气/fn

天依宝宝可爱！

abc416

D 简单贪心。E Floyd 的简单应用。F 树上背包，但是分讨。

然后就寄了，没调完。

哦哦 F 的弱化版是 CF 原 CF633F。

补 F，调了一会儿发现假完了。不调了。/愤怒

abc417

D 是 A-F 最难（确信

D 有两个观察。第一个是 p,a,b 的值域都很小，只有 V = 500，可以考虑复杂度为 O(nV) 的做法；第二个是 x 很大，不过当 x 过大的时候，显然操作序列的一个前缀一定是全减的。

发现 1 \sim i 全减的这个阈值（即满足条件的最小 x）是可以求的，令 v_i 为 1 \sim i 全减的阈值，考虑同时满足达到 i-1 的阈值 与 前面全减后的剩余价值仍然能 > p_i，有递推式：

可以发现求出来这个之后，就只需要考虑初始值不大的情况了，不过对于每个出发点都要求一遍，自然能想到 dp，令 f_{i,j} 表示从 i 开始操作，初始值为 j 的最终答案，考虑 j 与 p_i 的大小关系，显然有转移：

发现 j 只需要处理到 1000 就可以了，所以复杂度正好 O(nV) 以及一个常数 2。

然后 WA*1，怒砍 25min 发现是 x > v_n 的时候，忘记特判结果 <0 的情况了。也是这个让我没时间写 E 了。

E 不怎么会，开 F，发现是线段树板子，3min 切了。

回来写 E，还是不会，准备拿 dij 乱搞一下，然后就没写完（）

赛后 12min 一发过 E 了……应该是因为复杂度 O(nm \log m) 里的第一个 n 根本跑不满导致的。