集训5——靶题

· · 个人记录

1.CF1991F

考虑三角形两边之和大于第三边，那要是一直不合法就是两边之和小于等于第三边，也就是排完序都有 a_i + a_{i+1} \le a_{i+2}，我们希望找到一个序列满足这个条件且序列最长。

由于长度都是正整数，于是 a_1 =a_2 = 1,a_{i+2} = a_i + a_{i+1}，发现是斐波那契。

注意到 F_{45} = 1134903170 > 10^9，这就告诉我们 45 个木棍一定能拼出 1 个三角形。我们再往里塞三个棍，就能拼出来 2 个了。

于是 r-l+1 \geq 48 时输出 YES。

剩下的暴力，但是无法 n^6，考虑一个三角形，显然大部分都是排完序三个连续木棍拼的。于是我们排完序枚举两段不交的长度为 3 的连续木棍看能不能拼。

写完发现过不了第一个询问。

2 2 4 5 10 10，按我们这么做拼不出来，于是还得看连续 6 个木棍，随便排能不能拼。

至于为什么是连续 6 个，比如你原来选的 11011011，如果一个 0 左右都是同一个三角形的棍子，那么可以把那个三角形最左边的一根换成这个 0。

因为原来是 x\le y \le z,x+y > z，你换一个 x < x' < z 过来，仍旧 x' + y > z。

不断做这样的替换。最后如果所有空位都被填掉，那么选中的就是连续 6 根；如果还有空位无法填，那么这个空位左右一定属于不同的三角形，都能在她覆盖的区间内找到连续三根组成三角形，也就被前边算过了。

2.CF2003D2

刻画一下这个过程，发现像是算出来每个序列的 mex，你要是能从别的地方给她一个，就能跳到更大的 mex。

那我们把每个序列的 mex 值称为 g，让 g 向这个序列加上 g 的 mex 建边。

然后发现能吃到的最大的 mex 就是这个点能达到的最大点。

由于我们一定是小点连向大点，所以这个扫一遍就能快速算出。

不管怎么走都劣的也就是比最大点还大的起点，直接不操作，等差数列算一下和。

写完发现样例差 eps。

就想到这。

发现有的点是可以拿到低保的。

比如 2->3 2->10，起点是 100，你能通过第一个边走到 2 之后再走第二个边到 10。其她起点都同理。

所以我们记录一下所有出度至少为 2 的点能到最大的点的最大值，以及所有的 g 的最大值作为低保。

3.CF2008H

发现给所有的都减到 \le x 不劣。

二分答案。

$$ \sum [a_i \bmod x \le mid] > \frac{n}{2}\\ \sum [a_i \le x\lfloor\frac{a_i}{x}\rfloor + mid] > \frac{n}{2}\\ \sum [x\lfloor\frac{a_i}{x}\rfloor \le a_i \le x\lfloor\frac{a_i}{x}\rfloor + mid] > \frac{n}{2}\\ $$ 发现贡献是一个 $a_i \in [kx,kx+mid]$ 状物。 维护一个桶的前缀和，这样可以快速算值域内数的个数。 然后枚举 $k$ 来 check。 ### [4.CF2013E](https://www.luogu.com.cn/problem/CF2013E) 考虑当前前缀 $\gcd$ 为 $g$，设 $A = \min_j \gcd(a_j,g),B=\gcd(g,y)$，$y$ 是一个任意的 $a$ 中能满足 $A<B$ 的值。 假设现在 $A=\gcd(g,x),B=\gcd(g,y)$，我们看一下先选 $x$ 再选 $y$ 的贡献。 选 $x$ 这步显然贡献为 $A$。 接下来前缀 $\gcd$ 变成 $A$，贡献变成 $\gcd(A,y)$。 由于 $A \mid g$，所以 $\gcd(A,y)=\gcd(A,\gcd(g,y))=\gcd(A,B)$。 我们算好了贡献，看能不能比出来大小。 因为 $\gcd(A,B) \mid B-A$ 且 $A<B$，所以 $\gcd(A,B) \le B-A$。 两边同时加 $A$，得到 $A + \gcd(A,B) \le B$。 因此，对于任意一个没有选择 $x$ 的最优方案，都可以把 $x$ 提到当前位置，且答案不会变差。所以当前一定可以选择使下一项前缀 $\gcd$ 最小的数。 对于第一个位置，直接认为 $g=0$ 即可。 ### [5.CF2014G](https://www.luogu.com.cn/problem/CF2014G) 直接模拟。 ### [6.CF2031E](https://www.luogu.com.cn/problem/CF2031E) 考虑如果我们知道 $u$ 所有儿子的子树的最小深度，假设就俩儿子，那 $u$ 的深度就是她俩 $\max$ 再加一。 思考一下，肯定越晚拿大的，大的贡献就会越少。 所以用优先队列模拟一下每次取两个的过程。 ### [7.CF2034E](https://www.luogu.com.cn/problem/CF2034E) 被这题硬控 1h。 为了方便，我们把题面中的 $n,k$ 叫做 $m,n$。 首先考虑一些显然的无解情况：$m! < n,m! = n+1$。 其次我们可以知道，每列的和就是 $\frac{(1+m)nm}{2m} = \frac{(1+m)n}{2}$，无法整除也就是 $m$ 偶 $n$ 奇同样无解。 接下来分讨 $n,m$ 的奇偶性。 - $n$ 偶，$m$ 奇/偶： 不难发现一种好的构造方式：每两行组队构造，所有奇数行直接 `next_permutation`，偶数行就看每个位置，上一个距离 $1+m$ 差多少直接填。 - $n$ 奇，$m$ 奇 首先一个显然的想法是先用 $m$ 行 $m$ 列的填出一个循环位移的方阵，剩下的按偶数做。填不了的你断言无解。 但这样真的对吗？你开开心心地写完，交上去发现 `WA on #2 test case 2`，你把有解判成无解了。 看她的输入 `137 5`。一看 $n$ 这么小，难不成能用 $3$ 行就构出来剩下的按偶数做？ 稍加思考发现，确实如此。 具体地，我们分别填： $1,2,3,\cdots,m$. $m,m-2,m-4,\cdots,1,m-1,m-3,\cdots,2$. $\frac{m}{2}+1,\frac{m}{2}+2,\cdots,m,1,2,\cdots,\frac{m}{2}$. 具体咋发现的话，手画一个 $n=3,m=7$ 的，算出来每列需要 $12$，首先我们填 $1$ 到 $m$，每列需要的就是 $11,10,9,\cdots,5$。我们再猜一下这个按奇偶放的，再减去贡献发现需要的也是一个排列，而且很有规律，于是做完了。 要注意这种情况 $n<3$ 中除了 $n=m=1$ 同样无解。 ### [8.CF2046C](https://www.luogu.com.cn/problem/CF2046C) 考虑二分城市数 $k$。 check 就枚举一个竖线，在两边直接看高度第 $k$ 小和第 $k$ 大，中间这个区间就是横线可以在的区间，看左右的这个区间有没有交即可。 ### [10.CF2062D](https://www.luogu.com.cn/problem/CF2062D) 考虑她操作的本质是啥。 不难发现就是给一个子树或者她的补集加 $1$。 考察一条边 $u \to v$： 当 $a_u > a_v$，时，把 $v$ 这侧都加一，没有提高 ### [11.CF2070E](https://www.luogu.com.cn/problem/CF2070E) 显然两个 $0$ 加一堆 $1$ 或者 $0$ 直接先手必胜。 玩一下样例，发现 `0 0 1` 是很厉害的样子。 发现往里再填一对 `0 0`，后手必胜；填一对 `0 1`，后手必胜；填一个 `0`，后手必胜；填 `0 0 1`，后手必胜；填 `0 1 1`，后手必胜。 填 `0 0 1 0`，先手必胜。 同时我们猜测在先手必胜状态下加一个 `0 0 1 0`，仍先手必胜，其余除了最开始说的状态先手都必败。 考虑基础先手必胜状态：`0 0 1` 以及全 $0$。 验证一下，发现还挺充分。 发现我不会计数，而且两种先手必胜状态拼出来的也不一定是先手必胜。 然后瞎推了推式子，写完发现样例都没过。 **就想到这。** --- 其实我的做法是对的，只是代码写炸了而已。 ### [12.CF1876C](https://www.luogu.com.cn/problem/CF1876C) 考虑建 $i \to a_i$ 的边建出一棵内向基环树。 发现如果给原图黑白染色表示 $i$ 点被没被圈。 发现如果 $i$ 是白色，那么 $a_i$ 一定是黑色。 这是因为如果 $i$ 是白色，那 $a_i$ 肯定在剩下的里，即在操作序列里，即 $a_i$ 为黑色。 发现如果一个点 $x$ 是黑色，那么一定有一个指向她的是白色。 这是因为她是黑色说明她在操作序列里，也在剩下的序列里，说明剩下序列里肯定有一个 $a_i = x$ 的。 知道这两条性质之后就很好办了。 贪心地做，如果有白色儿子，那自己就是黑的；反之自己就是白的。 环上的话，只需要保证没有奇环，偶环直接染就好了。 ### [13.CF1898E](https://www.luogu.com.cn/problem/CF1898E) 如果没有排序操作，就直接找后边第一个能匹的地方了。 那排序的作用就在于，能把后边匹的位置提到前边而不浪费中间的值。 显然如果一个字母在后边，她肯定不能把在前边比她字典序小的排过来 所以我们维护 $26$ 个队列分别表示 $s$ 中 $26$ 个字母出现的位置，前边还比当前这个小的直接弹掉，要是有一个时候填不上就无解。 ### [14.CF1907G](https://www.luogu.com.cn/problem/CF1907G) 考虑建出基环树，不在环里的而且入度为 $1$ 还是亮的，就必须做操作。 所以做一个类似于拓扑排序的东西，把非环都处理完了。 接下来环上一定会是相邻两个，一个一直推过去，然后她们两个消掉。 发现这样的答案只有两种，也就是奇推到偶或者偶推到奇。 直接算一下贡献，每个环直接取 $\min$ 就好了。 ### [15.CF1919D](https://www.luogu.com.cn/problem/CF1919D) 考察一个点，裂开的话会在她左边或者右边新增一个她的权值加 $1$，这是显然。 反过来的话，如果左边右边如果都是叶子，那说明两个叶子权值分别是她和她加一。 我们持续对这样的点往上合并，看看最后能不能合成 $0$。 考虑一个数 $x$，她能被删说明有一时刻她旁边走过来一个 $x-1$ 把她带走了。 考虑一个序列 $y,\ge x,\ge x,\cdots,\ge x,x$。 中间这些有可能被删掉，然后 $y$ 来到 $x$ 旁边，如果 $y = x - 1$，直接删掉了，右边同理。 如果中间每个点都能删掉那 $x$ 自然能删掉。 按权值从大到小归纳。处理到 $x$ 时，我们假设所有 $>x$ 的点都已经能被删掉了。 这样中间全是 $x$，$y$ 一路删过来即可。 所以直接看每个数是否都有能删掉她的就好了。 ### [16.CF1934D1](https://www.luogu.com.cn/problem/CF1934D1) 第一眼看见这题，给你 $63$ 次，而且这样例也是一位一位做的，所以我们也考虑一位一位做。 写了个从低往高不一样的直接翻，甚至过样例了。 交上去 `6 1` 直接构出来个 `6 7 5 1`。 我发现这个做法简直没有任何道理。 先把 $n<m$ 判了。 考虑一次操作，当前是 $x$，选一个 $a$，可以变成 $a$ 或者 $a\oplus x$。 考虑当前为 $x$，希望一次操作后变成 $z$。此时可以直接选择 $a = z$，另一部分就是 $x\oplus z$，因此要求 $z<x,x\oplus z<x$。 设 $z$ 最高 $1$ 位为 $r$。 - 如果 $x$ 最高 $1$ 位也在 $r$ 这，那么说明她俩的异或也小于 $x$。 - 如果 $x$ 最高 $1$ 位比 $r$ 高且 $x$ 第 $r$ 位是 $1$，那她俩的异或小于 $x$。 - 如果 $x$ 最高 $1$ 位比 $r$ 高且 $x$ 第 $r$ 位是 $0$，那她俩的异或大于 $x$。 **这告诉我们，$x$ 能够变成 $z$，充要条件是 $z$ 最高 $1$ 位在 $x$ 这里同样是 $1$。** 设 $n$ 最高，次高位 $1$ 分别为 $p,q$，$m$ 最高位 $1$ 为 $r$。 如果说 $n$ 第 $r$ 位是 $1$，直接一步就能做完了。 接下来，也就是 $n$ 第 $r$ 位为 $0$，如果 $r<q$，也就是 $m$ 最高位比 $n$ 次高位还低，那么我们构造一个 $g = m \oplus 2^q$。 这样 $g$ 最高位在 $n$ 是 $1$，$m$ 最高位在 $g$ 上是 $1$，这样可以两步做完。 接下来考虑 $q<r<p$。 看任何一个与 $n$ 最高位相同、小于 $n$ 的数 $x$。 由于 $p$ 到 $q$ 中间全是 $0$，如果想得到一个 $p$ 到 $q$ 中间的值为 $1$，显然她就会大于 $n$，不合法。 如果没有次高位而且第一个做法也做不出来就无解了。 因此，当当前数的最高位仍为 $p$ 时，第 $r$ 位恒为 $0$，所以根据前面的单步转移条件，不可能一步把最高位降到 $r$。 一旦最高位降到 $q$ 或更低，由于每次操作后数值严格减小，就再也不可能到达最高位为 $r$ 的 $m$。因此无解。 ### [17.CF1948E](https://www.luogu.com.cn/problem/CF1948E) 把点 $(i,a_i)$ 扔到平面上，那在一个团也就是任意两点曼哈顿距离 $\le k$。 我们想满足这个，然后我们发现同一个团 $a_i$ 连续一定不劣，接下来考虑怎么放。 假设现在一个大小为 $x$ 的团发现限制最严的就是 $1$ 和 $x$，越往里限制越松。 例如 $x=5$，我们构造 $a=[2,1,5,4,3]$，发现是可行的。 设这一团取的最小最大下标分别是 $l,r$，这一团大小为 $s$，那么 $r-l\ge s-1$，且 $|r-l|+|a_r-a_l|\le k$。左边至少是 $s-1+1=s$，因此 $s\le k$。 那么一个团大小上界就是 $k$。 我们按照上边的构造方案做即可。 ### [18.CF1954E](https://www.luogu.com.cn/problem/CF1954E) 看到跟值域相关的问题，想到笛卡尔树。 建一个小根笛卡尔树，显然她的操作是在子树减 $k$，根减没了直接裂成左右两棵树。 一个点最多能吃 $\lceil \frac{a_i}{k} \rceil$ 次伤害，父亲死后儿子只需要吃 $\lceil \frac{a_{fa}}{k} \rceil - \lceil \frac{a_u}{k} \rceil$ 次伤害就好了。 发现这个东西等价于 $[a_{fa},a_u)$ 有多少个 $k$ 的倍数。 考虑处理出 $c_i$ 表示 $i$ 在每个 $[a_{fa},a_u)$ 共出现多少次。 这个对于每条边 $u \to v$ 直接 $[a_u,a_v)$ 区间加一就好了。 之后查询直接枚举所有 $k$，枚举 $k$ 的倍数，求 $\sum_j c_{jk}$。 ### [19.ARC179B](https://www.luogu.com.cn/problem/AT_arc179_b) 看见 $m\le10$，考虑状压。 设 $dp_{i,s}$ 表示前 $i$ 位，当前可以填的数有哪些。 枚举一个 $h$ 填，接下来 $h$ 不能用了，但是所有 $x_i = h$ 的都可以填了。 因此 $dp_{i,s} \to dp_{i+1,s\oplus 2^{h-1} | g_h}$，其中 $g_h$ 表示所有限制为 $h$ 的位置状态。 ### [20.ARC179B](https://www.luogu.com.cn/problem/AT_arc179_b) 考虑设 $f_{i,j,k,l}$ 其中 $j,k,l\in\{0,1\}$ 表示前 $i$ 位拼出有这仨倍数的状态的最小操作次数。 转移我说不清了，你自己看吧。反正我没绷住。 ![](https://cdn.luogu.com.cn/upload/image_hosting/4qptl54o.webp) ### [21.ARC175B](https://www.luogu.com.cn/problem/AT_arc175_b) 先把 $n$ 变成 $2n$，不然说着不方便。 考虑把操作放到前缀和上，发现就是区间加 $\pm 2$ 和后缀加 $\pm 2$。 考虑先让 $sum_n$ 通过后缀加减变成 $0$，因为区间加减是左闭右开的，$sum_n$ 吃不到。 然后我们看这个东西对全局有没有积极影响，如果她加的是正数，那我们让她加给全局；如果她加的是负数，那位们只让她自己减。 接下来找到前缀和序列里的最小值 $mn$，我们假设总能找到一个包含 $mn$ 的区间让她全吃到加 $2$，那我们就疯狂操作就好了。 接下来我们来证这个事情。 假设 $mn\le-2$，我们找 $l,r$ 分别表示第一个、最后一个 $sum\le mn+1$ 的位置。 由于 $l$ 是第一次掉到 $mn+1$，所以 $sum_{l-1} = mn+2$，所以第 $l$ 个字符为 `)`；同理 $sum_{r+1} = mn+2$，第 $r+1$ 个字符为 `(`。 因此这就是我们要找的区间，随着不断加，区间也会不断变小，最终变成滚木。 因此这种区间必然存在，得证。 所以算一下贡献就好了，别忘记区间操作等价于两次后缀操作，需要取个 $\min$。 ### [22.ARC180B](https://www.luogu.com.cn/problem/AT_arc180_b) 考虑从大值往小做，每次只找前边能操作的做操作，这样能保证前边不管咋做不影响一会到下一个人的她的位置。 我们拿到前边能操作的数，按从小到大地和当前位做交换，这样满足所有条件，但是是最优吗？ 你交换一次会让逆序对数至少减 $1$，你肯定想让他们每次都只减少 $1$。 显然从小到大做，每个前边的值都不会被卡住，这样保证了每个合法的对都吃到了贡献。 这样同样也不会让后边的贡献减少，因为你找的 $l,r$ 同样是从大到小枚举的，且 $l,r$ 都比当前枚举这位大，因此不会影响后边遍历到更小的 $r$。