CodeForces 随机做题

唯一真随机系列。所以里面有不少 trash。

CF1372F (*2700)

交互题，无非就是要做到一点：把他给你的抽象的操作转化成“能通过这些操作得到什么具体的，和题目有关的信息”。

首先容易发现，如果我们知道了每个数出现的次数就可以还原出来整个序列。考虑从这方面入手。

然后考虑，先询问 $[1,n]$ 的众数显然可以得到一个数的出现次数。然后如果想要直到其他数的呢？那我们就要尽量避免问到同样的数。

具体地，若 $[1,n]$ 的众数 $x$ 出现次数为 $y$ ，考虑将当前序列分成若干个长度等于 $y$ 的块，剩下一个不满的单独一块。此时就有很好的性质了：

每种数至多作为众数返回 $2$ 次，因为它最多在两块中出现。
当前的 $x$ 一定在至少一块中作为众数出现一次。原因显然。

那么先考虑确定当前 $x$ 的出现区间，这样就可以递归成若干个子问题去找其他数。事实上这是简单的。

首先，若 $x$ 刚好占了一块的位置。那么询问这块返回的一定是 $(x,y)$ 。容易判断。

否则，考虑 $x$ 一定不包含于那个返回 $x$ 为众数的块。于是设返回了 $(x,y')$ ，那么询问这一块的前 $y'$ 个，就能知道 $x$ 是这一块的前 $y'$ 个还是后 $y'$ 个。又因为我们知道 $y$ ，于是剩下的 $x$ 位置也能一并求出（前一块的后 $y-y'$ 个或后一块的 $y-y'$ 个）。

然后只需要把 $x$ 给去掉，对于每一块剩下的部分分别当作子问题处理即可。这样每种数只会被查询到 $3$ 次。

但是容易发现一个问题：上面提到每种数至多作为众数返回 $2$ 次。如果这里去到 $2$ 是不是就寄了？

但是发现，如果一个数 $x$ 占一个块的前缀，并且在前面的块出现过。那么只要有一次询问到的众数是 $x$ ，只需要更新 $x$ 的出现次数，并且把 $x$ 去掉，对于剩下的部分继续做即可。

容易发现这样只需要从左到右做，由于后面部分的块长一定大于这个 $x$ 的出现次数 $y$ （否则众数是 $x$ ，块长为 $y$ ），所以只需要 $3+1=4$ 次。刚好足够。这样问题就解决了。

CF431D (*2100)

容易发现 $n$ 和 $2n$ 的 $1$ 的个数一样。所以当 $[n,2n-2]\to [n+1,2n]$ 时满足条件的数的个数不减。二分后数位 dp 即可。

CF507E (*2100)

bfs 跑出来最短路图算最少经过边数，然后在这个 DAG 上拓扑排序算最少改变边数即可。

CF141D (*2300)

把关键点拎出来，建图跑最短路就行。

CF1004F (*2600)

经典结论，固定左/右端点，不同的区间 OR/AND/ $\gcd$ 只有 $O(\log V)$ 种。考虑在这题中怎么运用。

对于算所有子区间的问题，要不离线扫描线，要不就类似猫树分治，合并时算跨区间的贡献。这题显然是后者。所以考虑对于每个区间维护不同的前/后缀 OR 集合。这个信息合并是简单的，只需要再记录区间 OR 和。至于算贡献，暴力 $O(\log^2 V)$ 可过，但是不难注意到由于前/后缀 OR 都是单增的，所以可以直接双指针，总复杂度 $O(q\log n\log V)$ 。

CF768C (*1800)

蠢到不行的脑筋急转弯。发现 $a_i\le 1000$ 所以相同的缩成一个段一起做即可。

CF40C (*2300) $\color{blue}\Diamond$

直接数分割成的部分数是难做的， $\color{blue}\Diamond$ 不过这种问题可以考虑平面图的欧拉公式： $|V|-|E|+|F|-1=|C|$ 。其中 $V$ 是点集， $E$ 是边集， $F$ 是分割成的平面集， $C$ 是连通块集。

然后考虑怎么算。此时还有一个观察：由于这个平面图是由圆组成的，每一个圆相当于图的一个环，而环上 $|V|=|E|$ 。也就是说，只需要对于其中一个 $(K,z)$ 集合，算出来这个圆一共被分成了多少段记作 $x$ ，那么答案就是 $x+|C|+1$ 了。

还需要注意，这里我们将一个不和其他任何圆在弧上相交的圆视作 $|V|=|E|=1$ 的连通块。

然后考虑算这个 $x$ 。枚举左侧的集合的每一个圆，不难发现和这个圆弧相交的右侧的圆的 $r$ 是一段区间。每和一个圆相交，就会多分出来 $2$ 段弧。但是要特判相切的情况。此时只会多一段。

最后就是算 $|C|$ 。不难发现对于两个集合都是 $r$ 的一段前缀及后缀的圆不与其他圆有交。直接数就行。

CF435E (*2500)

做过 Mex Mat 那题容易发现，这个条件和 $a_{i,j}=\operatorname{mex}(a_{i-1,j},a_{i,j-1},a_{i-1,j-1})$ 有点相似。考虑类似地，往对角线的方向寻找规律。

一个猜测是我们一定有 $a_{i,j}=a_{i-2,j-2}$ 。但是会发现这是不对的，可以构造出：

121
343
212

或

132
241
132

似乎无法继续了。但是继续手玩，不难发现（以第一种情况为例子）这三行最终的填法一定是

12121212...
34343434...
21212121...

而后面的行也一定是这样 ababab 型的。

那么我们现在就只用考虑所有 $a_{i,j}=a_{i-2,j-2}$ 的情况了。于是可以填出来：

12??12
34??34
??12??
??34??

然后发现其实整个矩形已经确定了，是

可以考虑 $(2,4)$ 这个位置只有唯一填法。

不难发现这种填法中每行也都是 ababab 型的。

于是综合上面两种情况得证。即要不所有列是 ababab 型，要不所有行是。构造是简单的。

CF1117E (*2200)

最优的方法应当是，对于这种只能获得部分有关编号的信息的，直接拆成 $k$ 进制做。可以做 $26^3$ 。

CF2035F (*2500)

容易想到二分。但是显然没有单调性。不过发现如果 $x$ 次操作可行， $x+2n$ 次一定也行。所以每次检查 $[mid,mid+2n]$ 内是否有可行的。检查是简单的，只用 dp 每个子树的操作都进行完后这棵子树内最少剩下多少要消掉即可。

CF611E (*2400)

先钦定 $a\le b\le c$ 。容易发现对于一个 $t_i$ ，实际上可能最优的决策不会很多。

对于 $t_i\le b$ ，一定只用一个数满足。
对于 $c<t_i\le b+c$ ，一定用两个。
对于 $t_i>b+c$ ，只能用三个。
对于 $a+b<t_i\le c$ ，一定只用 $c$ 。
剩下的可能用 $a+b$ 可能用 $c$ 。

同时，对于只能用一个/两个的，可行决策有包含关系。比如，如果可以用 $a$ ，就一定能用 $b$ ；如果能用 $a+c$ ，就一定能用 $b+c$ 。

再考虑一个问题：如果知道了分别用 $a,b,c,ab,ac,bc,abc$ 操作数量，怎么求出最小操作次数。首先 $abc$ 一定单独做。 $ab,ac,bc$ 两两不能一起做,所以这里需要 $ab+ac+bc$ 。剩下 $a,b,c$ ，分别可以和 $bc,ac,ab$ 一起做。剩下需要 $\max(a-bc,b-ac,c-ab,0)$ 次。

但是事实上还可以用上面的包含关系调整。不过注意到上面的式子是上个差值的形式，所以把一个 $ab$ 变成 $ac$ 和把一个 $b$ 变成 $c$ 是等价的。于是只需要考虑 $a,b,c$ 的调整。

容易发现，令 $a-bc=x,b-ac=y,c-ab=z$ 。这相当于可以在 $x$ 中取任意个给 $y$ ， $y$ 给 $z$ 同理。所以答案就是 $\max(z,\left\lceil\frac{y+z}2\right\rceil,\left\lceil\frac{x+y+z}3\right\rceil)$ 。

于是回到原问题，只需要枚举 $5$ 种情况中的最后一种选多少个 $c$ ，多少个 $ab$ 即可。复杂度 $O(n)$ 。

CF671C (*2800)

考虑枚举每一种因数 $x$ 第一、二和倒数第一，二次出现位置记作 $a,b,c,d$ ，那么 $[1,c-1],[a+1,d-1],[b+1,n]$ 的所有子区间的答案都要和 $x$ 取 $\max$ 。

这个东西直接维护是不好做的，但是发现如果按因数从大到小做，就变成了覆盖。而对于每个位置 $i$ ，已经覆盖的 $[i,*]$ 是 $[i,n]$ 的一段前缀 $[i,f_i]$ 。于是只需要维护这个 $f_i$ 就可以知道这次覆盖的贡献了。可以直接无脑吉司机。但是不难发现 $f_i$ 单调不降。于是线段树二分也是可以的。

CF506D (*2400)

直接有脑根分。对于出现次数 $<\sqrt m$ 的颜色，直接预处理出每对联通的点对 $(x,y)$ ，答案 $+1$ 。这部分，由于每条边带来的贡献不超过 $\sqrt m$ ，所以总复杂度是 $O(m\sqrt m)$ 。

否则直接在询问的时候枚举该颜色，看 $u,v$ 是否在这个颜色的同一连通块中即可。 $O(q\sqrt m)$ 。

CF2041H (*2300)

首先显然可以对于所有 $i\le n$ 求出长度为 $i$ ，只有 $><$ 的方案数，然后在里面任意插入 $=$ 。然后考虑 $k$ 的限制，发现这等价于没有连续的 $k-1$ 个相同的符号。于是简单 dp 即可。

CF962F (*2400)

首先建出 dfs 树，那么每条非树边都对应树上一条某个点到祖先的路径。结论就是，如果有两条这样的路径在边上相交，那么这两条路径上的所有边以及对应的非树边被包含在了至少两个简单环内。证明不难。所以简单树上差分解决。