Red Right Hand

Safe：做出来，觉得简单的题
Euclid：做出来，但不觉得简单的题
Keter：没做出来/看题解做出来/过题但根本不知道为什么过了的题
Apollyon：无法自行解决的题目

[TOC]

1. CF871E - Restore the Tree [Euclid]

题面

有一棵 $n$ 个点的树，有人从上面挑了 $k$ 个点，并告诉了你这 $k$ 个点中每个点到所有点的距离（相当于给你了一个 $k\times n$ 的距离矩阵），请你构造一棵符合条件的树，无法构成则输出 $-1$

$2\le n\le30000,1\le k\le\min(200,n)$

题解

考虑随便从这 $k$ 个点中挑出一个点作为根，那么我们能确定每个点的深度，由此，我们可以求出这 $k$ 个点到根的路径上有哪些点，我们称这些点组成了「已知树」

接下来，我们考虑所有不在「已知树」中的点 $x$，对于这 $k$ 个点中的每个点 $y$，我们知道 $dep_y,dep_x,dis(x,y)$，那么我们可以求出 $dep_{lca(x,y)}$，而我们又知道 $y$ 到根的路径，因此我们知道 $lca(x,y)$

一个点 $x$ 会产生 $k$ 个 lca，这 $k$ 个 lca 一定要在一条到根的链上，我们将这 $k$ 个 lca 中最深的称为 $x$ 的「切入点」

我们将所有不在「已知树」内的点按深度考虑，依次往「已知树」上挂，我们对「已知树」的每个点维护当前考虑的深度向上一层的该点的子孙 $link$，然后将新来的点它的「切入点」的 $link$ 下面，到下一个深度时更新对每个「已知树」中的点的 $link$（这个「已知树」不包含后来挂上去的点）

复杂度 $O(nk)$

2. CF839E - Mother of Dragons [Keter]

题面

有一个 $n$ 个点的无向图，你需要给每一个点赋一个实数点权 $a_i$ 使 $\sum a_i=k$，一条边 $(u,v)$ 的权值为 $a_ua_v$，求权值和的最大值

$1\le n\le40,1\le k\le1000$

题解

结论：最优方案是取出原图的最大团，并将 $k$ 的权值平均分给团中的点

证明先鸽着。

我们只要找出最大团即可解决这个问题，考虑折半解决，我们枚举其中一半的点的集合，然后统计另一边的点集最大能为多少，复杂度 $O(2^{\frac n2}n)$

3. CF838D - Airplane Arrangements [Keter]

题面

有 $n$ 个位置，$m$ 个人，第 $i$ 个人会从第 $a_i$ 个位置出发，向左或向右行走，找到第一个没有被标记的位置，然后标记这个位置并消失，如果一个人没有找到符合条件的位置，那么你就是失败的。

求有多少安排每个人出现位置以及行走方向的方法，使得你不是失败的，答案对 $10^9+7$ 取模

$1\le m\le n\le10^6$

题解

打表得 $ans=2(n-m+1)(2(n+1))^{m-1}$。

说明：

考虑我们在 $n$ 后面再添加一个位置 $n+1$，并将它看做一个环，$1$ 与 $n+1$ 相邻，那么人们会在这个环上逆时针/顺时针走，你是失败的当且仅当第 $n+1$ 个位置被标记

考虑由于这 $n+1$ 个位置的地位是均等的，因此在 $n+1$ 被标记的概率是 $\frac{m}{n+1}$，未被标记的概率是 $\frac{n+1-m}{n+1}$，答案为 $\frac{n+1-m}{n+1}(2(n+1))^m$，即原式。

4. CF814E - An unavoidable detour for home [Euclid]

题面

求有多少 $n$ 个点的无权无向图，满足：

第 $i$ 个点的度数为 $d_i$
第 $1$ 个点到任意一个点的最短路存在且唯一
第 $1$ 个点到第 $i$ 个点的最短路长度不小于第 $1$ 个点到第 $i-1$ 个点的最短路

$3\le n\le50,2\le d_i\le3$

题解

按最短路长度分层转移，考虑题目要求使得这个无向图第 $i$ 层的每一个点有且仅有一条边与第 $i-1$ 层的点相连

我们令 $dp(i,j)$ 表示前 $i$ 个点，最后一层有 $j$ 个点的方案数

那么 $dp(i,j)=\sum_{1\le k\le i-j}dp(i-j,k)\times ways$，其中 $ways$ 表示 $[i-j-k+1,i-j]$ 与 $[i-j+1,i]$ 为相邻层时 $[i-j-k+1,i-j]$ 内部与 $[i-j-k+1,i-j]$ 和 $[i-j+1,i]$ 之间的边的方案数

由于 $[i-j-k+1,i-j]$ 中的每一个点都要与上一层连边，因此它们在考虑范围内的度数为 $1$ 或 $2$，我们可以将 $[i-j+1,i]$ 内的点视作度数为 $1$ 的点，但我们需要保证这些点不直接相连，考虑容斥统计，我们枚举度数为 $2$ 的点成环的个数，经过一番组合计数得到：

$ways=\sum_{c=0}^bcyc_c\binom bc\left(\sum_{i=0}^{\lfloor\frac x2\rfloor}(-1)^i\binom x{2i}\frac{(2i)!}{i!2^i}\frac{x+a-2i}{(\frac{x+a-2i}2)!2^{\frac{x+a-2i}2}}\frac{(\frac{x+a-2i}2+b-c-1)!}{(\frac{x+a-2i}2-1)!}\right)$

其中 $cyc_c$ 表示 $c$ 个度数为 $2$ 的点形成若干个环的方案数，不难 dp 得出

总复杂度 $O(n^5)$

5. CF802C - Heidi and Library (hard) [Keter]

题面

你有一个容量为 $k$ 的书架，初始为空，你在任意时刻可以扔掉一本书或者花费 $c_i$ 的代价购进第 $i$ 本书

第 $i$ 天会有人来看第 $a_i$ 本书，此时你需要保证你的书架里有这一本书

问满足所有人所需要的的最小代价

$1\le n,k\le80$

题解

好像有人讲过，但我完全不会。。。

费用流。

很明显我们第 $i$ 天后只有可能扔掉第 $a_i$ 本书

我们将“第 $i$ 天买的书留到第 $j$ 天扔掉”视作第 $i$ 天的书留到第 $j-1$ 天卖掉（并贡献 $-c_{a_i}$ 的代价）然后在第 $j$ 天又买进来一本书，这样我们可以保证每天都买一本书

我们给每天买的这本书建两个点，入点 $x_i$ 出点 $y_i$~~（其中 $x_i$ 的意义为“买进的第 $a_i$ 本书”，$y_i$ 的意义为“最后第 $i$ 天买进的书去哪了”）~~那么我们需要连如下一些边（$(u,v,w,c)$ 表示 $u\rightarrow v$ 流量为 $w$，费用为 $c$ 的边）：

$(S,x_i,1,c_{a_i})$，这条边一定会被流，表示当日买进了第 $a_i$ 本书
$(y_i,T,1,0)$，这条边一定会被流，表示第 $i$ 天买进的书被扔掉/卖掉了
$(x_i,y_i,1,0)$，表示第 $i$ 天买进的书当天就被扔掉了
$(x_i,x_{i+1},k-1,0)$，表示第 $i$ 天书架里的书留到了第 $i+1$ 天，注意这里容量是 $k-1$，因为下一天还要买进来一本书
$(x_{i-1},y_{lst_i},1,-c_{a_i})$，其中 $lst_i$ 表示 $i$ 以前最大的 $j$ 使得 $a_j=a_i$，这表示在第 $lst_i$ 天的书留到第 $i-1$ 天被卖掉了

复杂度 $O(费用流)$

6. CF773D - Perishable Roads [Keter]

题面

给定一个 $n$ 个点的带权无向完全图，现在有一个首都，你需要给每个点指定一个出边，使得从任意一个点出发沿着出边走均能到达首都，而且从每个点出发经过的边权最小值之和最小，请对每个点作为首都的情况求出最小值

$2\le n\le2000$

题解

结论 1：答案一定是一条链

证明：考虑如果路径上有 $a\rightarrow c,b\rightarrow c$，我们不妨假设 $w_{a\rightarrow c}\le w_{b\rightarrow c}$，那么我们将 $b\rightarrow c$ 改为 $b\rightarrow a$ 更优

我们将所有边的边权都减去最小边的边权，这样经过最小边的路径答案一定是 $0$，最后再将答案加上最小边的边权乘 $n-1$

设这条路径上的点为 $a_1,a_2,\cdots,a_n$，边的边权依次为 $w_1,w_2,\cdots,w_{n-1}$

结论 2：设第 $k$ 条边为路径上的第一个最小边的下标，那么对于所有 $1\le i\le k-3$，有 $w_i>w_{i+1}$

证明：如果 $w_i\le w_{i+1}$，我们连 $a_{i+2}\rightarrow a_k,a_{i+3}\rightarrow a_{i+4}\rightarrow\cdots\rightarrow a_k$，那么答案一定不会更劣

那么我们只需要考虑 $w_{k-2}$ 与 $w_{k-1}$ 的大小情况，如果 $w_{k-2}>w_{k-1}$，那么答案为 $dis_{a_1,a_k}$ 的最短路；如果 $w_{k-2}\le w_{k-1}$，那么答案为 $2w_{k-2}+dis_{a_1,a_{k-2}}$

考虑这样的话我们建源点，向每个点 $i$ 连长度为 $2\min e_{u,i}$ 的边，这样能涵盖这两种情况的答案，跑一边最短路即可

复杂度 $O(n^2)$

7. CF687E - TOF [Safe]

题面

dfs(v)
{
     set count[v] = count[v] + 1
     if(count[v] < 1000)
     {
          foreach u in neighbors[v]
          {
               if(visited[u] is equal to false)
               {
                    dfs(u)
               }
               break
          }
     }
     set visited[v] = true
}

main()
{
     input the digraph()
     TOF()
     foreach 1<=i<=n
     {
          set count[i] = 0 , visited[i] = false
     }
     foreach 1 <= v <= n
     {
          if(visited[v] is equal to false)
          {
               dfs(v)
          }
     }
     ... // And do something cool and magical but we can't tell you what!
}

给定输入的 $n$ 个点 $m$ 条边的有向图，TOF 函数内会用某种方式对每个 $i$ 重排 neighbors[i]，求所有可能的重排方式中，之后 dfs 调用次数的最小值

$1\le n,m\le5000$

题解

搁这搁这呢。。。

题面翻译：给定一张有向图，你需要删掉其中的一些边，把它拆成若干个内向基环树，使得原来有出度的点现在仍有出度，要求环长之和最小

考虑缩点后显然答案为所有出度为 $0$ 的强联通分量内的最小环之和，可以用 bfs 求出，特判一下强联通分量为一个点的情况

复杂度 $O(n^2)$

8. CF639E - Bear and Paradox [Safe]

题面

有 $n$ 道题，第 $i$ 道题的初始分数是 $p_i$，███████ 做完第 $i$ 道题需要 $t_i$ 的时间，我们定义 $T=t_1+t_2+\cdots+t_n$

如果 ███████ 在第 $x$ 时刻做完第 $i$ 道题，那么 ███████ 会获得 $p_i(1-\frac{cx}T)$ 的分数。不难发现，███████ 一共有 $n!$ 种做这些题的顺序，这些顺序中能获得最大的分数的我们称为「优秀的」

现在你需要求最大的 $c\in[0,1]$，使得对于任意「优秀的」方案，不存在 $i,j$ 满足 $p_i>p_j$ 且 ███████ 在 $i$ 上获得的分数小于在 $j$ 上的分数

$1\le n\le150000$

题解

显然可以二分，考虑怎么判断

推一下可以发现「优秀的」顺序一定满足 $\frac{p_i}{t_i}$ 递降，每个 $\frac{p_i}{t_i}$ 相等的段可以随意调换顺序

我们按 $p_i$ 从小到大考虑，那么可知，我们只要考虑 $p_i$ 段中可能位置最靠前的以及 $p_{i+1}$ 段中可能位置最靠后的会不会破坏要求

复杂度 $O(n\log W)$

9. CF1286C2 - Madhouse (Hard version) [Euclid]

题面

有一个长度为 $n$ 的串，你不知道它是什么。

你每次可以询问一个区间 $[l,r]$，会存在一个人告诉你 $s[l:r]$ 的所有子串，但这个人有些精神疾病，于是她告诉你的所有串都是乱序的，并且每个串内部的字符也被随机重排了

你可以进行至多 $3$ 次询问，并且这个人返回给你的子串不能超过 $\lceil0.777(n+1)^2\rceil$ 个，否则你会被██████████████。

你需要猜出这个串是什么。

$1\le n\le100$

题解

这个 $0.777$ 是骗人的，根本用不了那么多。

考虑你询问一个区间 $[l,r]$，那么你就能得到 $\{s[l],s[r]\},\{s[l+1],s[r-1]\},\cdots$

那么如果我们询问了一个长度为奇数的区间，我们就可以确定中间的位置

因此，我们分两种情况考虑：

$n$ 是奇数，我们询问 $[1,n],[1,\frac{n-1}2],[1,\frac{n+1}2]$
$n$ 是偶数，我们询问 $[1,n-1],[\frac n2,n],[\frac n2,n-1]$

不难发现这样可以推出答案

注意特判 $n=1$ 的情况

10. CF1218A - Bubble Reactor [Safe]

题面

你有一张 $n$ 个点 $n$ 条边的无向图，你首先需要选定一个点将其标记，接下来你需要重复 $n-1$ 次“选择与一个已标记的点直接相连的未标记点并将其标记”，标记一个点会获得“与该点直接或通过若干未标记点相连的点的未标记点个数”的收益，求最大收益

$3\le n\le15000$

题解

流汗黄豆。

找到环后直接在环上区间 dp，复杂度 $O(n^2)$，能过。

11. CF1201E - Knightmare (easy/hard) [Euclid]

题面

交互题。

$n\times m(2|n,2|m)$ 的国际象棋棋盘上 $(x_1,y_1)$ 有一只白马，$(x_2,y_2)$ 有一只黑马，白马先走，游戏轮流进行，每次每人走一步，白马的目标点是 $(\frac n2,\frac m2)$，黑马的目标点是 $(\frac n2+1,\frac m2)$，如果一只马到了目标点并且另一只马一步之内杀不掉它，那么它就赢了，同时如果一个马被杀掉了，那么活着的那只马就赢了，如果经过 $350$ 步仍无法分出胜负那么平局

交互库邀请你和她一起玩这个游戏，由于交互库很有礼貌，所以她让你选择你要用哪只马，你想获胜。

$1\le n\le1000$

题解

我们称 $(x_1,y_1)$ 为 $W$，$(x_2,y_2)$ 为 $B$，$(\frac n2,\frac m2)$ 为 $tW$，$(\frac n2+1,\frac m2)$ 为 $tB$

首先不难发现肯定有一只马无法吃掉另一只马，我们的策略分如下几种情况（这里假设黑马吃不掉白马，反过来情况类似）：

$dis(W,tW)\le dis(B,tB)$，选白马，按最短路线往 $tW$ 走，原因显然
$dis(W,tB)\le dis(B,tB)+1$，选白马，按最短路线往 $tB$ 走，这时黑马距离 $tB$ 一定为偶数，下一步黑马必定会跳到距离 $tB$ 为奇数的位置上，而距离 $tB$ 如果是 $1$ 则会被白马杀死，因此距离至少为 $3$，而 $tB$ 到 $tW$ 恰好为 $3$ 步，将白马移动过去即可
否则，选黑马，按最短路线往 $tB$ 走，白马不会追上你。

这样不会超过 $350$ 步，可以通过此题

12. CF1158D - Winding polygonal line [Euclid]

题面

有 $n$ 个点，你要连一条不自交的折线经过这里的所有点（且只能以这些点为起点/终点/拐点），这条折线上会有 $n-2$ 次转向，给出长为 $n-2$ 的字符串 $s$，由 L 和 R 组成，表明第 $i$ 次转向是左转还是右转，要求构造一条符合要求的折线。

$1\le n\le2000$

题解

我们称构造出的答案为 $p_1,p_2,\cdots,p_n$

构造策略如下：

首先考虑前两个点，我们钦定 $p_1$ 为 $y$ 坐标最小的点，将，然后如果 $s_1=L$，我们钦定剩余点极角排序后半圆内，最靠逆时针方向的点为 $p_2$，否则我们钦定最靠顺时针方向的点为 $p_2$

然后对于 $s_i(1\le i\le n-2)$（我们现在已 $p_i,p_{i+1}$，求 $p_{i+2}$），分四种情况讨论：

$s_i=L,s_i=s_{i+1}$，以 $p_{i+1}$ 为中心极角排序，取 $p_{i+2}$ 为 $\overrightarrow{p_ip_{i+1}}$ 这条射线的顺时针半平面中的最靠逆时针的点
$s_i=L,s_i\neq s_{i+1}$，以 $p_{i+1}$ 为中心极角排序，取 $p_{i+2}$ 为 $\overrightarrow{p_ip_{i+1}}$ 这条射线的顺时针半平面中的最靠顺时针的点
$s_i=R,s_i=s_{i+1}$，以 $p_{i+1}$ 为中心极角排序，取 $p_{i+2}$ 为 $\overrightarrow{p_ip_{i+1}}$ 这条射线的逆时针半平面中的最靠顺时针的点
$s_i=R,s_i\neq s_{i+1}$，以 $p_{i+1}$ 为中心极角排序，取 $p_{i+2}$ 为 $\overrightarrow{p_ip_{i+1}}$ 这条射线的逆时针半平面中的最靠逆时针的点

昂，就这样，是不是看起来很对呢/cy ~~我也不知道为啥对~~

13. CF1140F - Extending Set of Points [Euclid]

题面

对于一个平面直角坐标系内的点集 $S$，我们定义运算 $f(S)$ 为：如果存在一个点 $(a,b)\notin S$ 且存在 $x,y$ 使 $(x,b)\in S,(x,y)\in S,(a,y)\in S$，那么我们将 $(a,b)$ 加入 $S$，如此往复，直到不能加点为止，此时的 $S$ 为运算的结果

现在有一个点集 $T$，初始为空，有 $q$ 次操作，每次加入或删除一个点，每次操作后求 $|f(S)|$

$1\le q,x_i,y_i\le3\times10^5$

题解

如果我们将每个 $x$ 坐标建点 $a_i$，将每个 $y$ 坐标建点 $b_i$，$(x_i,y_i)$ 视作在 $a_i$ 与 $b_i$ 之间连一条边，那么答案就等于每个连通块内 $a$ 点的个数乘上 $b$ 点的个数的乘积之和

我们对时间轴建线段树，将每条边存在的时间区间打到线段树的懒标记上，最后在离线在线段树上 dfs，用可撤销并查集维护答案，复杂度 $O(q\log^2q)$

14. CF1103C - Johnny Solving [Euclid]

题面

你有一张 $n$ 个点 $m$ 条边的联通无向图以及一个整数 $k$，保证这张图中每个点度数不小于 $3$，你可以选择以下两个任务中的任意一个完成：

PATH：找到一条点数 $\ge\frac nk$ 的路径
CYCLES：找到 $k$ 个长度 $\ge3$ 且不为 $3$ 的倍数的环，且这些环满足每个环都有一个独特的点不在其他环内出现

$1\le k\le n\le2.5\times10^5,1\le m\le5\times10^5$

题解

我们找出原图的一棵 dfs 树，如果这棵树深度超过 $\frac nk$，那么我们就能够完成 PATH 任务

否则，这棵树至少有 $k$ 个叶子，而每个叶子至少有两条回边 $v_1,v_2$，那么 $u\rightarrow v_1\rightarrow u$，$u\rightarrow v_2\rightarrow u$，$u\rightarrow v_1\rightarrow v_2\rightarrow v$ 中至少有一个环长不是 $3$ 的倍数，那我们就能完成 CYCLES 任务

15. CF1067E - Random Forest Rank [Keter]

题面

有一棵 $n$ 个点的树，每条边有 $\frac12$ 的概率被删除，求邻接矩阵的秩的期望

$1\le n\le5\times10^5$

题解

乍一看是道 dp 题，没想到是个线代题。

考虑矩阵的秩等于非零子式的最高阶数，出于某些原因，我们只用考虑关于左上-右下对角线对称的子式~~（editorial 也没给证明我能怎么办）~~

考虑这样的子式一定对应着原图的一个导出子图，那么这样的子式也是一个森林

考虑一个矩阵的行列式为 $\sum_{\pi}(-1)^{sgn(\pi)}\prod_{i=1}^n A_{i,\pi_i}$，对于一个排列 $\pi$，它的贡献非零当且仅当 $A_{i,\pi_i}$ 均为 $1$，这意味着 $i\rightarrow \pi_i$ 这些边在这个子图中均存在，会形成若干个环，但是森林里没有环，因此只能全是一条边的两个端点形成的环，而这就是原图的一个完美匹配，只有完美匹配的排列才会对行列式做出贡献，所以行列式非零的子图一定有完美匹配。

又因森林的完美匹配唯一，所以如果有完美匹配一定恰好有一个排列对行列式做出贡献，所以如果有完美匹配那么一定行列式非零

因此我们要找到最大的行列式非零的子式，相当于找到最大的有完美匹配的子图，相当于找到原图的最大匹配

因此秩的大小等于最大匹配边数的$\times2$

那么我们需要求出最大匹配数的期望，我们令 $f_u$ 表示只考虑 $u$ 子树内的边，$u$ 与儿子匹配的概率

我们以“能往下匹配就往下匹配”的方式来最大匹配，那么 $u$ 不与儿子匹配的情况当且仅当儿子都已经匹配或边断掉，由此我们可以得到转移式 $f_u=1-\prod (\frac12f_v+\frac12)$

复杂度 $O(n)$

16. CF1060F - Shrinking Tree [Keter]

题面

给定一棵 $n$ 个点的树，$n-1$ 次操作，每次操作随机选一条边 $(u,v)$，将 $u,v$ 所连的所有其他点连到一个新点上，并将 $u,v$ 删除，这个新点的编号在 $u,v$ 中随机选

对于每个 $i$，求 $i$ 这个编号留到最后的概率

$1\le n\le50$

题解

我们对每个点分别求解，求解点 $i$ 时我们将其设为根

设 $siz_u$ 为 $u$ 子树内的边数，定义 $f_{u,i}$ 表示 $u$ 的子树内，钦定前 $siz_u-j$ 次操作均没有删掉 $u$ 这个编号，在这种情况下 $u$ 留到最后的概率

考虑怎么合并子树 $v$，设我们合并完的状态为 $g_i$

首先我们需要加入 $u\rightarrow v$ 的边，我们考虑枚举这条边倒数第几步被删，设其为 $j$，那么：

$j\le i$，说明 $j$ 这一步没有钦定，那么 $g_{i}\leftarrow \frac12f_{v,j-1}\times\frac1{siz_v+1}$
$j>i$，说明 $j$ 这一步被钦定，那么 $g_i\leftarrow f_{v,j-1}\times\frac1{siz_v+1}$

接下来考虑如何合并这棵树与 $u$ 已经计算的子树，设我们合并完的状态为 $h_i$，那么我们枚举最后 $a+b$ 次操作内有 $a$ 个在已经计算的子树内，有 $b$ 个在新子树内，那么转移式为：$h_{a+b}\leftarrow f_{u,a}g_b\frac{\binom{a+b}a\binom{siz_u-a+siz_v-b}{siz_u-a}}{\binom{siz_u+siz_v}{siz_u}}$

复杂度 $O(n^4)$

17. CF1033F - Boolean Computer [Safe]

题面

有 $n$ 个 $w$ 位的二进制数 $a_1,a_2,\cdots,a_n$，有 $m$ 次询问，每次给出一个位运算函数 $f$，用一个长为 $w$ 的由 A，O，X，a，o，x 组成的字符串表示，分别表示两个数从高到低的第 $i$ 位进行 AND，OR，XOR，NAND，NOR，NXOR 操作，求有多少有序对 $(i,j)$ 满足 $f(a_i,a_j)=0$

$1\le w\le12,1\le n\le3\times10^4,1\le m\le5\times10^4$

题解

考虑枚举其中的一个操作数，另一个操作数的每一位就只有 0，1，任意三种情况，那么我们可以用 $O(w3^w)$ 的复杂度预处理出这部分的答案，这样的总复杂度是 $O(w3^w+mw2^w)$，无法通过

考虑我们枚举操作时从 $0$ 到 $2^w-1$，二进制位改变的次数是 $O(2^w)$ 量级的，所以我们计算 $i$ 时可以继承 $i-1$ 的信息，然后修改与 $i$ 不同的位，这样我们把复杂度降到了 $O(w3^w+m2^w)$

18. CF1012D - AB-strings [Fuck you] [Decommissioned]

题面

给定两个由 a，b 组成的串 $s$ 与 $t$，每次操作可以分别交换两个串的一个前缀（不一定长度一样，可以为空，可以为全串），问最少要多少次操作才能使其中一个串全是 a，另一个串全是 b，并给出构造

$1\le|s|,|t|\le2\times10^5$

题解

I tried.

特判题给爷爬。

19. CF962G - Visible Black Areas [Safe]

题面

给定一个简单 $n$ 边形，保证所有边都平行于坐标轴，给定一个矩形，求只保留 $n$ 边形在矩形内的部分（不含边界），会有多少连通块

$1\le n\le15000$

题解

不懂为啥这题还 *2800

直接无脑扫描线，用 set 维护当前的连续段

复杂度 $O(n\log n)$

20. CF938F - Erasing Substrings [Keter]

题面

给定一个长为 $n$ 的串，令 $k=\lfloor\log_2n\rfloor$，你要进行 $k$ 次操作，第 $i$ 次删除一个长为 $2^{i-1}$ 的子串，求最后剩下的串字典序最小的可能

$1\le n\le5000$

题解

不难，但是我没做出来。降智了/cy

令 $dp_{i,S}$ 表示前 $i$ 位，使用了 $S$ 集合中的操作，是否可能成为最小值，每次转移时我们先对每个为真的 $dp_{i,S}$ 将 $dp_{i+1,S}$ 赋为真，然后 $j={0\rightarrow 2^n-1}$，如果 $dp_{i+1,j}$ 为真那么将 $dp_{i+1,j\cup\{x\}}(x\notin j)$ 赋为真，最后再检查有哪些是最小值

复杂度 $O(n^2\log n)$