主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
AT 比赛场祭
最后更新于 2025-06-15 22:19:22
作者
littlebug
分类
个人记录
复制 Markdown
查看原文
更新内容
喵喵喵~ --- ### abc355 [](https://atcoder.jp/contests/abc355/standings?watching=little__bug) 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 [](https://atcoder.jp/contests/abc356/standings?watching=little__bug) 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 [](https://atcoder.jp/contests/abc357/standings?watching=little__bug) 糖丸了，就 AC3，掉大分。 AB 水，不写。 C 递归一下，每次将矩阵划分成 $9$ 个区域，复杂度 $O(3^{2n})$。 D 想到等比数列求和，但调半天二分没调过，啊啊啊我竟然不知道等比数列求和公式，最后用公式写了，结果差一点就交上，赛后马上 A 了。/kk E 图的形态好像是一个基环树，但当时想到基环树的时候已经只剩 10min 了，认为写不完就没写。/kk --- ### abc358 [](https://atcoder.jp/contests/abc358/standings?watching=little__bug) A 水。 B 模拟一下即可。 C 爆搜，注意代码细节。 D 贪心一下，将 $\{a\},\{b\}$ 排序后，从小到大枚举 $i$，然后尽可能地给每个人最少的糖果。 然后 EFG 好像都可做（最水的 G），不过我一会儿想做这个一会儿想做那个的，导致最后一道题也没过QwQ，以后必须读题之后要用心针对一个题了！ --- ### abc359 [](https://atcoder.jp/contests/abc359/standings?watching=little__bug) 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 [](https://atcoder.jp/contests/arc180/standings?watching=little__bug) 只会一题，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 [](https://atcoder.jp/contests/abc360/standings?watching=little__bug) 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 [](https://atcoder.jp/contests/abc361/standings?watching=little__bug) 哦哦哦我好厉害，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 [](https://atcoder.jp/contests/abc362/standings?watching=little__bug) AC\*3，棒（ 由于倒序开题。 F 推了大概 $10min+$，不会。 E 考虑 dp，用 `map` 离散一下公差，设 $f_{i,j,k}$ 表示结尾为 $a_i$，长度为 $j$，公差为 $k$ 的等差序列个数，则可得转移方程为 $$f_{i,j,k}= \sum_{i'=1}^{i-1} f_{i',j-1,k}$$ $f_{i,1,k}$ 都为 $1$，然后 $O(n^4)$ 暴力转移，过样例，然后 WA+RE（ 然后因为只剩 $40min+$，所以赶快去切了 ABD，竟然不会 C 呜呜呜（当时脑抽惹qwq）。 G 是 AC 自动机板子，所以去洛谷上抄了篇tj，不过莫名其妙的 WA 了（？ 连掉 $4$ 场，赢（bushi 补 C，首先 $\sum l>0$ 或 $\sum r<0$ 则无解。否则设 $s=\sum r$，从前往后贪心地取 $l_i$，每次将 $s$ 减去 $r_i - l_i$，直到 $s=0$，后面的都取 $r_i$ 即可。 补 E，设 $f_{i,d,len}$ 表示第一项为 $a_i$，公差 $d$，长度为 $len$ 的等差序列个数。则从 $n \sim 1$ 枚举第一项 $a_i$，然后从 $i+1 \sim n$ 枚举第二项 $a_j$（酱紫就确定公差惹），然后从 $2$ 开始枚举 $len$，则将 $f_{i,d,len}$ 加上 $f_{j,d,len-1}$，这样可以保证考虑到所有情况qwq。 --- ### abc366 [](https://atcoder.jp/contests/abc366/standings?watching=little__bug) 集训回来第一场比赛，上大分！ 总结：在比赛前给 AT/CF 表白会导致上分。 切 A。 B 没看清题意吃了一发罚时。 C `map` 切掉，不过注意不能直接 `map.size()`。 D 三维前缀和，~~因为懒得手推 bdfs 了一下式子~~。 到目前为止，这场 abc 似乎比以前的都简单（？ E 看了眼题面就确定不会惹。 开 F，发现 $k \le 10$，考虑从这里下手。首先我们需要排个序，使得先选前面的比先选后面的结果小，也就是 $f_i(f_{i-1}(x)) < f_{i-1}(f_i(x))$，推一下式子： $$ \begin{aligned} f_i (f_j (x)) < f_j (f_i (x)) & \Leftrightarrow a_i (a_j x + b_j) + b_i < a_j (a_i x + b_i) + b_j \\ & \Leftrightarrow a_i a_j x + a_i b_j + b_i < a_j a_i x + a_j b_i + b_j \\ & \Leftrightarrow a_i b_j + b_i < a_j b_i + a_i \end{aligned} $$ 发现 $f_i$ 与 $f_j$ 的先后顺序与 $x$ 无关，于是直接排序。 然后 dp。 - 设 $f_{i,j}$ 表示在前 $i$ 个函数中选 $j$ 个且**以第 $i$ 个结尾**（就是套在最外面的那个函数）的最大值； - 设 $s_{i,j}$ 表示在前 $i$ 个函数中选 $j$ 个的最大值（**不一定要选第 $i$ 个**）。 于是就好转移了，先循环 $i$，再循环 $j$。 - $f_{i,j} = a_i \times s_{i-1,j-1} + b_i$，就是 $i-1$ 个中选 $j-1$ 个的最大值再选上第 $i$ 个的值。 - $s_{i,j} = \max(s_{i-1,j} , f_{i,j})$，这个就不用解释惹。 当然第一维可以滚掉，不过没必要qwq。 然后一遍过，快乐地上分啦~（还是第一次 perf 上蓝呢！） --- ### arc182 [](https://atcoder.jp/contests/arc182/standings?watching=little__bug) 上青啦！上青啦！上青啦！ B<<<<<<<<<<<<<<<<A 看了 $10min$ A之后，发现不会，所以直接跳，开 B。 浅浅喷一下：$k \ne K$（自己体会（雾 B 在知道了 $k \ne K$ 之后，想到对于 $n$ 个数分开考虑，先在 $k=3$ 时打了个表，发现每个数可以构成的数好像有关联。 设 $A$ 为选择的数，$B$ 为可以构成的数。 设对 $x$ 的一次**转移**为 $\lfloor \frac{x}{2} \rfloor$，$x$ 的一次**逆转移**为 $2x$ 或 $2x+1$。那么一个数的 $B$ 就为 $x , \lfloor \frac{x}{2} \rfloor , \lfloor \frac{x}{4} \rfloor , \dots , 0$。 所以 $2x$ 与 $2x+1$ 进行一次转移后所形成的数都为 $x$，那么它们在继续转移后构成的数就都是相同的了，这很显然是不优的，因为在 $A$ 中增加一个数，在 $B$ 中也只增加了一个数。 显然，每个数在进行好多次转移最后都会变成 $0$，所以我们不妨倒着想，使得每个数在进行 $k$ 次逆转移后不同，且 $k$ 尽可能小。 这里可以对逆转移打个表找规律，但我们~~注意力惊人~~可以发现，逆转移不就是一个完全二叉树上的一个节点和转移到它的两个子节点吗？！又因为限制 $A_i \le 2^K - 1$（~~这里是大 K~~），提示我们这颗完全二叉树的深度为 $K-1$（第一层深度为 $0$）。 于是问题就转化成了，在深度为 $K-1$ 的完全二叉树上选 $n$ 条链（可以相交、重复），使得经过的节点最多。 bfs 贪心即可。 然后回来看 A，发现可以直接 dp，第一次看的时候忽略了必须进行 $q$ 次操作。 因为必须进行 $q$ 次操作，所以第 $i$ 次操作一定不能与它后面的操作冲突，所以直接 $O(q^2)$ 先枚举 $i$，再枚举 $j$（$j > i$），转移的时候，因为只有 $v_j < v_i$ 的时候 $i$ 才可能影响到 $j$，然后不能使 $i$ 选择的区间影响到 $j$（一个选左边，一个选右边），记录 $f_{i,0/1}$ 表示第 $i$ 个的左/右区间是否可选。 最后答案用乘法原理求。 --- ### abc367 [](https://atcoder.jp/contests/abc367/standings?watching=little__bug) 糖糖糖糖糖糖，D 超级简单前缀和没看出来，E 在离结束 $15min$ 才出思路没写完（） A 水，注意 $c<b$ 要将 $a,c$ 加上 $24$。 B…………………………py 很轻松，但是没想到，我搞了半天啊啊啊还是最后暴力分讨的（） C 爆搜。 然后开 D，不会，开 E，不会，开 F，不会，G 没开。 过了很……长……一……段……时……间……原来 F 这么水（），简单搞个随机数哈希一下，然后每次查询用前缀和优化查一下区间和是否相同即可。AT 不可能卡随机化的。 不过居然上分了（？/jy --- ### abc368 [](https://atcoder.jp/contests/abc368/standings?watching=little__bug) 掉大分！ B 多读入了一个数导致 $2$ 发罚时 C 没看清题意 $1$ 发罚时 E 最短路没推出来 F 没学会 SG 函数导致的 G 没注意到答案在最后一句话上 然后没有然后了 D 考虑在 $v$ 中随便找一个点为根，然后贪心，只要一个点必选就把ta和根的路径上的点全选上。 我为什么没看 F 啊啊啊，第二天早上发呆的时候想了下原来这么简单（ --- ### abc370 [](https://atcoder.jp/contests/abc370/standings?watching=little__bug) A 没读清题意吃一发罚时 B 因为写了个 `qwq` 搞反了 $i,j$ C 贪心。 D 一大堆做法，我用的是并查集，大概还可以 `set`、十字链表、暴力用数组存（？） 做法是在四个方向分别开一个并查集，维护每个点向每个方向能看到的第一个点。不过因为一堆rz错误调了半天（/dk 不过 E 一眼了（其实 D 也是，不过仅限于一眼解法），所以…… 为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？为什么不先开 E？ /fn --- ### abc371 [](https://atcoder.jp/contests/abc371/standings?watching=little__bug) 再也不做 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 [](https://atcoder.jp/contests/abc372/standings?watching=little__bug) D 单调队列板子。 E 因为 $k \le 10$，所以暴力并查集维护前 $10$ 大即可。 F 没想出来，想到 dp 但不会处理环。 G 是 半平面交 + 类欧，紫 + 紫（虽然据 dalao 们所说的，好像到不了黑），NOI 级算法不会呜呜呜/dk --- ### abc378 [](https://atcoder.jp/contests/abc378/standings?watching=little__bug) 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 [](https://atcoder.jp/contests/abc379/standings?watching=little__bug) 切了 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 [](https://atcoder.jp/contests/abc380/standings?watching=little__bug) 经典调！线！段！树！调！不！出！来！ 难度降序 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 [](https://atcoder.jp/contests/abc381/standings?watching=little__bug) 还是只会四题 /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 [](https://atcoder.jp/contests/abc382/standings?watching=little__bug) 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}$。 $O(n^2 + nx)$，做完了。 知道为啥读不懂样例了，以后做期望要搞清楚求的是谁的期望。 G 还是黑题。 天依可爱！ --- ### abc383 [](https://atcoder.jp/contests/abc383/standings?watching=little__bug) abc 还是只能过 $4$ 题/cf 感觉 A-E 平均难度比之前难。 C 多元 bfs。D 因为只有 $x = p^8$ 或 $x = p_1^2 p_2^2$ 时 $x$ 恰好有 $9$ 个因数，所以预处理 $10^6$ 质数，暴力统计即可，注意不要爆 `ll`。 E 先想到建最小生成树，然后想了 dp 和贪心，但是还是不会做。 F 看起来好麻烦，不会。 CLIST E\*1600 F\*1688 怪不得我做不出来（ F 怎么是背包这种我学了 $2$ 年多也学不会的东西/kk（真的，认为背包是最难的 dp）。 补 E，考虑在最小生成树的过程中计算答案，~~然后就做完了~~。因为是从小到大连边，所以考虑在连边 $(u,v)$ 的时候，把与 $u$ 连通的点和与 $v$ 连通的点两两相连，贡献都为当前边的边权，这样显然能保证总贡献最小。 补 F，背包背包背包背包背包，根据题面的提示，我们设 $f_{i,j}$ 为用前 $c$ 种**颜色**，容量为 $j$ 时的最大价值。转移考虑 $3$ 种情况：不选 / 第一次选颜色 $c$ / 不是第一次选颜色 $c$ 即可，$f_{c,j}=\max(f_{c-1,j},f_{c-1,j-p_i}+u_i+k,f_{c,j-p_i}+u_i)$，注意要像背包一样倒序转移，注意 $c$ 可能不连续，需要离散化。 G 不是黑题。 天依可爱！ --- ### abc384 [](https://atcoder.jp/contests/abc384/standings?watching=little__bug) 上青！ A-E 一眼了。 D 倍长，然后对于每个 $i$，前缀和数组上二分 $s + pre_{i-1}$ 看看是否出现即可。 E bfs + 优先队列。 F 一眼想到 01trie，发现似乎可做，于是开写，但是只过了样例 #1，估计是统计的时候炸了。 补 F，原来是计数题而不是位运算题呀。因为直接算有点难以优化，所以考虑 $2^d$ 的贡献。设 $f_d$ 为满足 $2^d~|~(a_i + a_j)$ 的所有 $(a_i + a_j)$ 之和，答案即为 $\sum \limits _{d=1} ^{\log V + 1} \frac {f_{d-1} - f_d} {2^d}$。然后考虑如何 $O(n)$ 计算 $f_d$，推式子： $$ \begin{aligned} 2^d~|~(a_i + a_j) & \Rarr a_i + a_j \equiv 0 \pmod {2^d} \\ & \Rarr a_i \equiv - a_j \pmod {2^d} \end{aligned} $$ 于是开个 `map` 存 $- a_j$，遍历过程中统计就可以了。 复杂度 $O(n \log V)$，不过似乎写的常数有点大，跑了 $2s$。 G 是莫队。 天依可爱！ --- ### abc385 [](https://atcoder.jp/contests/abc385/standings?watching=little__bug) E<<<<<<<<<<D 写了半天 D WA*15 了之后去开 E，发现 E 这么水（恼 D 考虑把每次行走记录为一些横线和一些竖线，同时也用 $x$ 坐标与 $y$ 坐标分别为关键字将房子分组，然后分别二分统计即可，注意统计完了一段房子就要删掉。然后就 WA*15 了。 E 暴力枚举每个点 $u$ 为根，记录 $u$ 的每个儿子的度数，暴力枚举 $y$ 的取值即可。因为一条边只会被算 $2$ 次；暴力枚举 $y$ 时均摊一下会发现最多计算 $\sum {\rm deg}_i$ 次，所以总复杂度是 $O(n)$ 的。 补 D，哦原来可以先不管重复，都插入 `set` 里去重呀。糖。 补 F，很好啊一眼了，根据人类智慧只判断距离近的几个数就行了。不过看了题解，发现不是这么做的，只需要判断 $x$ 坐标相邻的两个点，因为无论两个点之间存在一个多高的点，都可以证明只判断相邻的 $2$ 个即可（考虑画个三角形，看三条边的斜率）。 但是精度问题硬控我 $0.5h$，原来快写浮点数没有 `printf` 精度高啊，记住了，以后再也不用快写浮点数了。/ll 天依可爱！ --- ### abc386 [](https://atcoder.jp/contests/abc386/standings?watching=little__bug) 日常 abc 只过 $4$ 题。 D 拿个 `map` 分别记录行列，然后在保证没有 `W` 在 `B` 左上方就行，具体地，对于行，按照每行从大到小遍历，维护一个出现 `B` 的 $\max$ 列，后面的 `W` 不能比这个 $\max$ 大。列同理。 E 爆搜，但是 T 了，然后卡时，交了几发（罚时 += inf）之后 WA*2 过不去了。 赛后发现是因为忘记可能 $k=1$，然后 $O((n-k)!)$ 就寄了，需要 $O(k!)$，所以判一下 $k$ 和 $n-k$ 大小来选择方案即可。 补 F，原来这么水，考虑字符串编辑距离的那个 $O(nm)$ dp，又因为 $k \le 20$，所以只对同一个 $i$ 的前后分别 $k$ 个字符进行 dp 即可。具体地，可以设计状态 $f_{i,dj}$ 为 $s$ 的前 $i$ 个字符，$t$ 的前 $i + dj$ 个字符的编辑距离，类似地转移即可，类似的答案即为 $f_{n,m-n+k}$。 补 G，挺厉害的一道计数，有点麻烦。感觉这辈子不可能自己想出来了。 **Part 1** 一个 trick：对于任意一个图 $G$，设 $G_k$ 为该图中所有 $< k$ 的边组成的图，$c(G_k)$ 为这个图的联通块数量，边权区间为 $[0,w_{\max}]$，则图 $G$ 的 MST 边权和等于 $\sum \limits _{k=1} ^{w_{\max} + 1} (c(G_k) - 1) = - (w_{\max} + 1) + \sum \limits _{k=1} ^{w_{\max} + 1} c(G_k)$。 证明：考虑在 MST 中一条边权为 $w$ 的边的贡献，这条边在 $G_k$ 中当且仅当 $k > w$，这时对连通块数是没有影响的；但是当 $k \le w$ 时，这条边就会断开，连通块数量 $+1$，此时 $k$ 的取值范围为 $[1,w]$，正好有 $w$ 个，于是就可以转化了。$-1$ 是因为要扣掉 $G_k$ 原有的那个连通块。 这个 trick 有一个良好的性质，就是不用去处理 MST 了，而是转为连通块的计数。 **Part 2** 既然 Part 1 里说边权区间为 $[0,w_{\max}]$，那么我们不妨把题目的边权区间转化为 $[0,m-1]$，最后再加上一个 $m^{\frac {n(n-1)} 2} \times (n-1)$。 设 $ans$ 为答案，$S$ 为所有 $m^{\frac {n(n-1)} 2}$ 个图组成的集合，则可以列出式子： $$ \begin{aligned} ans & = m^{\frac {n(n-1)} 2} \times (n-1) + \sum _{G \in S} \left( - m + \sum _{k = 1} ^m c(G_k) \right) \\ & = m^{\frac {n(n-1)} 2} \times (n-1) - m^{\frac {n(n-1)} 2} \times m + \sum _{G \in S} \sum _{k = 1} ^m c(G_k) \\ & = m^{\frac {n(n-1)} 2} \times (n-1-m) + \sum _{G \in S} \sum _{k = 1} ^m c(G_k) \end{aligned} $$ 但是这么还是不好做，于是可以不考虑图 $G_k$ 是长什么样的，直接对**每个连通块**进行计数，设 $G_k'$ 为 $G_k$ 的所有连通块集合： $$ \begin{aligned} ans & = m^{\frac {n(n-1)} 2} \times (n-1-m) + \sum _{G \in S} \sum _{k = 1} ^m c(G_k) \\ & = m^{\frac {n(n-1)} 2} \times (n-1-m) + \sum _{G \in S} \sum _{k = 1} ^m \sum _{H \in G_k'} 1 \\ & = m^{\frac {n(n-1)} 2} \times (n-1-m) + \sum _{k = 1} ^m \sum _{G \in S} \sum _{H \in G_k'} 1 \end{aligned} $$ **Part 3** 第一个 $\sum$ 可以直接枚举，考虑如何计算 $\sum \limits _{G \in S} \sum \limits _{H \in G_k'} 1$。 因为最后求的是 $H$ 的数量，于是可以从这里入手，设 $H$ 有 $V$ 个点，$E$ 条边，则需要考虑下面几种边： - 一条边的两个顶点都在 $H$ 中。 - 如果该边也在 $H$ 中，那么因为限制了一条边出现的条件是其边权 $< k$，于是边权的取值范围为 $[0,k-1]$，共 $k$ 种情况；因为 $H$ 中共有 $E$ 条边，于是答案乘上 $k^E$。 - 如果该边不在 $H$ 中，那么因为这条边不在 $H$ 中，于是其边权一定 $\ge k$，取值范围即为 $[k,m-1]$，共有 $m-k$ 中情况；显然这种边共有 $\frac {V(V-1)} 2 - E$ 条，于是答案乘上 $(m-k)^{\frac {V(V-1)} 2 - E}$。 - 一条边只有一个顶点在 $H$ 中，另一个顶点不在 $H$ 中。同上，这种边的边权取值范围也为 $[k,m-1]$；因为每个在 $H$ 中的点都可以和每个不在 $H$ 中的点连一条边，于是共有 $V(n-V)$ 条，答案乘上 $(m-k)^{V(n-V)}$。 - 一条边的两个顶点都不在 $H$ 中。随便取即可，答案乘上 $m^{\frac {(n-V)(n-V-1)} 2}$。 于是可以得到： $$ \sum _{G \in S} \sum _{H \in G_k'} 1 = k^E \times (m-k)^{\frac {V(V-1)} 2 - E} \times (m-k)^{V(n-V)} \times m^{\frac {(n-V)(n-V-1)} 2} $$ 所以可以枚举 $V$（即下面式子中的 $i$）和 $E$，再算上从 $n$ 个点里面选 $i$ 个共有 $\binom n i$ 个，答案转化为： $$ \begin{aligned} ans & = m^{\frac {n(n-1)} 2} \times (n-1-m) + \sum _{k = 1} ^m \sum _{i=1} ^n \sum _{E = 0} ^{i(i-1)} \binom n i \times k^E \times (m-k)^{\frac {i(i-1)} 2 - E} \times (m-k)^{i(n-i)} \times m^{\frac {(n-i)(n-i-1)} 2} \\ & = m^{\frac {n(n-1)} 2} \times (n-1-m) + \sum _{k = 1} ^m \sum _{i=1} ^n \binom n i \times(m-k)^{i(n-i)} \times m^{\frac {(n-i)(n-i-1)} 2} \sum _{E = 0} ^{i(i-1)} k^E \times (m-k)^{\frac {i(i-1)} 2 - E} \end{aligned} $$ **Part 4** 观察这个式子，我们发现它是 $O(n^3m)$ 的，枚举 $E$ 消耗的时间复杂度达到了 $O(n^2)$，不可以接受，需要把这个优化掉。注意到，式子中只有后两项与 $E$ 有关，即 $k^E \times (m-k)^{\frac {i(i-1)} 2 - E}$，所以考虑快速计算这个东西。 设 $f_i$ 为有 $i$ 个点的 $H$ 的 $\sum \limits _{E = 0} ^{i(i-1)} k^E \times (m-k)^{\frac {i(i-1)} 2 - E}$，则： $$ ans = m^{\frac {n(n-1)} 2} \times (n-1-m) + \sum _{k = 1} ^m \sum _{i=1} ^n \binom n i \times (m-k)^{i(n-i)} \times m^{\frac {(n-i)(n-i-1)} 2} \times f_i $$ 可以在 $O(nm)$ 内计算出。那么如何在大约 $O(n)$ 的时间复杂度内递推出 $f_i$ 呢？ 容斥！ 其实是个比较典的 trick 了，即在点数为 $i$，一条边有 $k$ 种可能出现，$m-k$ 种可能不出现，所形成的连通图的数量。 也就是用总方案数减去非连通块的方案数。显然总方案数为 $m^{\frac {i(i-1)} 2}$，即所能构成的不同图的个数；非连通块即出现 $> 1$ 个连通块，于是可以枚举连通块大小，**固定点 $\bm 1$ 在连通块内**，其它点与连通块分隔开，然后随便选即可，和上面算 $H$ 的数量的方法有些类似。 $$ f_i = m^{\frac {i(i-1)} 2} - \sum _{j=1} ^{i-1} \binom {i-1} {j-1} \times (m-k)^{j(i-j)} \times m^{\frac {(i-j)(i-j-1)} 2} \times f_j $$ 为什么要固定点 $1$ 呢？因为不这样的话就会导致算重，毕竟连通块外的点随便选也可能构成连通块，这样就算重了。而固定了点 $1$ 之后，算的就是 $1$ 所在的连通块的方案数了，不考虑 $1$ 不在内的连通块的情况，于是就不会算重了。 求 $f_i$ 需要 $O(n)$，加上前面求 $ans$ 总复杂度 $O(n^2m)$，终于做完了。 然后就被 $0^0 = 1$ 硬控了 30min。 [突发奇想想把所有式子放到一块看看](https://www.luogu.com.cn/paste/xnnc3oxp)，视觉效果挺不错的。 天依宝宝可爱！ --- ### abc387 [](https://atcoder.jp/contests/abc387/standings?watching=little__bug) 神奇 abc 之 F<C 诶还是只过 $4$ 题。 C 一眼数位 dp，所以跳了，细节过多的题我是写不了的。 D bfs 下即可，注意每个点有横竖两种状态。 E 推了一会儿没推出来。 然后开 F，一眼了！按照 $i \to a_i$ 连边，然后得到一个图，因为在同一个环内的数只能相等，所以跑个 Tarjan 缩点，然后得到一个 DAG，就可以 dp 了，设 $f_{u,i}$ 为点 $u$ 的值取 $i$ 的方案数，则可以得到式子：$f_{u,i} = \prod \limits _{(v,u) \in E} \sum \limits _{j \le i} f_{v,j}$，把第二个 $\sum$ 前缀和优化掉，复杂度在 $O(nm)$ 左右，最后答案即为 $\prod \limits _{out_u = 0} \sum \limits _{i} f_{u,i}$。 还剩 $40min$，回去搞 C，写了半天，寄了。 数位 dp 不可爱！ 补 C，发现比数位 dp 简单 $6737151$ 倍的做法，分成两块计数，一部分是整块即可以表示为 $[a \times 10^b,(a+1) \times 10^b - 1]$ 的形式的，这些数全部都符合条件，答案即为 $a^b$。另一部分是剩下的散块，考虑按照位数从大到小把当前散块拆成一些整块和一个更小一位的散块，因为整块是可以 $O(1)$ 直接算的，所以就不用 dp 了。 补 F，原来是人类智慧题啊，因为范围是 $[n,2n)$，所以可以小数暴力，大数用小学知识构造 $2,3,5$ 的倍数，发现以下这些数是可行的： - $1 \times 10^k + 10$ - $2 \times 10^k$ - $3 \times 10^k + 32$ - $4 \times 10^k + 40$ - $8 \times 10^k$ 毕竟范围比较大嘛，所以全都判一遍是否满足条件就可以了。 不过 clang 能过，GCC 神秘 WA 掉的代码 ++ 天依宝宝可爱！ --- ### abc390 [](https://atcoder.jp/contests/abc390/standings?watching=little__bug) 只会 $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](https://atcoder.jp/contests/abc390/submissions/62230988)，而原版 hash 只跑了 [1439ms](https://atcoder.jp/contests/abc390/submissions/62230988)，当然这是在用的 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 [](https://atcoder.jp/contests/arc191/standings?watching=little__bug) 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 [](https://atcoder.jp/contests/abc391/standings?watching=little__bug) 省流：赛后 43s 过 F。  D 考虑每一列自底向上的第 $i$ 个一定是同时消失的，所以用这个来计算一个方块消失的时间，注意如果一行不能构成 $w$ 个，那么之后的就都没法消失了。猜了个结论：一“行”（上面的定义）方块从上面掉到底下只跟它的高度有关，好像挺对的，没举出反例来就这么写了。 然后 WA\*20，可能是猜错了，但不知道错哪，跳之。 E 一眼了，递归处理每个 $[i,i + 3^k)$ 即可，不过我的写法码量有点大，写了 20min 左右一遍过了。 这时候只剩 10+min 了。 F 更一眼了，优先队列维护即可，但是忘记判 vis 硬控我 2min，结束前 1min 想到，于是没写完。 然后就有了上面的悲（？）剧。 总结：本场 abc F<E<D。 补 D，[拼尽全力无法战胜](https://www.luogu.com.cn/discuss/1053054)。不过在 @[wusixuan](https://www.luogu.com.cn/user/1038826) 大佬的帮助下过了，死因：忘记按照 $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$，那么则有转移： $$ f_{i+1,t} \gets f_{i+1,t} + f_{i,s} $$ 于是这样做就可以了。 统计答案的时候，一个 $s$ 所对应的 LCS 长度显然就是 ${\rm popc}(s)$。 需要注意两个优化剪枝，一是可以把 $f_{i,s}$ 为 $0$ 的状态直接剪掉，因为这部分起不到任何作用；二是可以把每个 $s,c$（$s$ 为差分数组，$c$ 为在末尾加的字符）在 LCS 的 dp 后对应的 $s'$ 预处理出来或者记忆化，避免重复做同样的事。 于是 $3$ 紫 + $2$ 紫题解，水之！ 天依宝宝可爱！ --- ### abc394 [](https://atcoder.jp/contests/abc394/standings?watching=little__bug) 近几个月第一次过 $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 [](https://atcoder.jp/contests/abc395/standings?watching=little__bug) 依旧过 $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 [](https://atcoder.jp/contests/abc396/standings?watching=little__bug) 好像是第一次过 $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 [](https://atcoder.jp/contests/abc397/standings?watching=little__bug) 4 题。 A 手滑敲错，没测样例就交次一发罚时！ D 想到的是预处理完全立方数，然后二分，但是交上去之后，发现好像可以炸 __int128，卡时无效，跳了。 E 好像一眼了，但是树形 dp 的细节有点多，调了一会儿。具体地，从底向上贪心（或者叫 dp？），遇到长度 $=k$ 的就砍掉，然后对于一个 $u$ 判一下她叶子结点的长度情况，能通过 $u$ 连起来的直接连起来，最后如果有连不起来的就无解。 F 想到了只出现一次贡献一定为 $1$，然后把长度 $>1$ 的都转化成区间（左端点为第一次出现的位置，右端点为最后一次出现的位置），求最大区间覆盖，其中区间中的数出现 $2$ 次的区间贡献为 $2$，$>2$ 的贡献为 $3$，看起来挺对的，但是剩 2min 写完却发现 $>2$ 时还要判区间覆盖过程中选择的区间是不是一定没划分成了 $3$ 份，例如样例 #2 的那种情况就不能。于是没时间写了，虽然看起来好像也不怎么对吧。 补 D，哦哦初中数学题，但是初中数学也是数学，所以不会。 首先： $$ x^3 - y^3 = (x-y)(x^2 + xy + y^2) $$ 于是设 $d = x-y$，那么 $d | n$，但是这样直接枚举是 $O(\sqrt n)$ 的。 不过注意到： $$ \begin{aligned} & (x-y)^2 = x^2 + 2xy + y^2 > x^2 + xy + y^2 \\ \Longrightarrow & (x-y)(x^2 + xy + y^2) < (x-y)^3 \\ \Longrightarrow & n = (x-y)^3 > d^3 \\ \Longrightarrow & d < \sqrt [3] n \end{aligned} $$ 于是 $d$ 是可以 $O(\sqrt [3] n)$ 枚举的。 然后： $$ \begin{aligned} x^3 - y^3 & = (d+y)^3 - y^3 \\ & = d^3 + 3d^2y + 3dy^2 \\ & = 3dy^2 + 3d^2y + d^3 \end{aligned} $$ 于是只需要检查关于 $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 [](https://atcoder.jp/contests/abc398/standings?watching=little__bug) 不会读题怎么办？/dk D 开 set 维护所有烟雾的位置，然后全局维护一个偏移量即可。 E 交互题。看起来像个二分图，但是它是一棵树，所以统计距离 $\ge 3$ 且为奇数的点对，塞到一个 set 里即可。然后想来想去没想明白哪里来的必胜策略，毕竟这些构不成奇环的点对都是相对独立且不相互影响的啊，这结果不就是固定的嘛……然后这么打了，结果只过样例（） 跳了。 F 字符串题，首先想到 hash，但没发现可以做，于是在用 KMP 去乱搞，发现通过某种奇怪的方式，可以通过样例和手搓的样例，于是这么交了，然后 WA 了。 没了。 补 E，死因：没注意到题面中说了可以选择先后手，它说了好几遍我都没发现唉……真的糖丸了啊啊啊啊啊啊………… 补 F，嗯很好的 hash 可以做，每个字符随一个值，然后维护个前缀后缀和，每个位置就可以 $O(1)$ 判了。 糖。 天依宝宝可爱！ --- ### abc399 [](https://atcoder.jp/contests/abc399/standings?watching=little__bug) 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$ 为前缀和数组，推柿子： $$ \begin{aligned} & \sum _{1 \le l \le r \le n} \left( \sum _{l \le i \le r} a_i \right) ^k \\ = & \sum _{1 \le l \le r \le n} ( s_r - s_{l-1} ) ^k \end{aligned} $$ 然后这里是赛时没想到的，因为 $s_{l-1}$ 有个 $-1$ 不好处理，于是考虑 $l \gets l-1$，然后就好做了。 $$ \begin{aligned} = & \sum _{0 \le l < r \le n} ( s_r - s_l ) ^k \\ = & \sum _{0 \le l < r \le n} \sum_{j=0}^k \binom k j (-s_l)^j s_r^{k-j} \\ = & \sum_{j=0}^k \binom k j \sum _{0 \le l < r \le n} (-s_l)^j s_r^{k-j} \\ = & \sum_{j=0}^k \binom k j \sum _{r = 1} ^n s_r ^{k-j} \sum _{l = 0} ^{r-1} (-s_l)^j \end{aligned} $$ 发现最后一个 $\sum$ 可以前缀和，所以总复杂度 $O(nk \log k)$ 做完了。 天依宝宝可爱！ --- ### abc401 [](https://atcoder.jp/contests/abc401/standings?watching=little__bug) 不过为什么 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 [](https://atcoder.jp/contests/abc402/standings?watching=little__bug) 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 [](https://atcoder.jp/contests/abc404/standings?watching=little__bug) 上大分了耶 > < 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 [](https://atcoder.jp/contests/abc405/standings?watching=little__bug) 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`，且每个区间内任意排列。 显然这样可以不重不漏，抛开复杂度不谈，答案即为： $$ \sum _{i=a} ^{a+b} \sum _{j=d} ^{c+d} \binom {i-1} {a-1} \binom {j-1} {d-1} \binom {a+b+c+d-i-j} {a+b-i} $$ 但是枚举 $i,j$ 的复杂度是 $O(n^2)$ 的，本来想化简来着，但是推了老半天柿子没搞出来，然后发现直接从组合意义角度考虑就行。可以发现当 $i$ 确定时，后面两个部分的 `B` `D` 是有序的，所以直接算 `C` 在哪些位置，然后方案就是唯一的了，所以答案就成了： $$ \sum _{i=a} ^{a+b} \binom {i-1} {a-1} \binom {a+b+c+d-i} c $$ 开 F，显然可以转化为给定一堆左端点严格递增的区间，每次询问一个与上面区间没有相同端点的 $[l,r]$，求与 $[l,r]$ 相交的线段条数。发现首先可以维护差分处理出来经过每个位置的线段个数，这样把左右端点的个数加起来，就得到了相交和被包含两种关系的数量之和。然后用个 BIT 维护一下，就可以被包含的数量。 但是样例 #2 一直不过……不知道为什么 qaq 补 F，查出来了！死因：把一个 `m` 写成了 `n`……足够逆天的。 但是怎么还是 WA 的呀…… 诶怎么换成统计 $[l,r]$ 内的点数，然后减去包含的区间就过了…… 所以到底为啥呀？/kel G 是莫队。 天依宝宝可爱！ --- ### abc406 [](https://atcoder.jp/contests/abc406/standings?watching=little__bug) 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 [](https://atcoder.jp/contests/abc408/standings?watching=little__bug) 糖丸了。 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$ 的排列啊……？ 调不出来了不调了[。](https://atcoder.jp/contests/abc408/submissions/66371766) 补 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 [](https://atcoder.jp/contests/abc409/standings?watching=little__bug) 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](https://atcoder.jp/contests/abc409/submissions/66592886)（（ G 需要用到 FFT。 天依宝宝可爱！ --- ### arc200 [](https://atcoder.jp/contests/arc200/standings?watching=little__bug) A 一点思路没有。 B 考虑乱搞，随便拍一些大质数上去，再乘上一些 $10$ 来应对 lcm，然后 WA*2。 天依宝宝可爱！
正在渲染内容...
点赞
3
收藏
1
