Codeforces Round #606

A. As Simple as One and Two

题意：一个长度为$n$的字符串$s$。删掉最少的字符，使得不包含one或者two作为子串。

$1 \le n \le 1.5 \cdot 10^5$

题解：首先考虑把所有的two消掉，那么删掉o肯定是最优的。之后考虑删掉所有的one，也删o就好了。拿个栈维护即可。

题意：给出$n$个点$m$条边的无向连通图。给出$a$和$b$，求出有多少对$(x,y)$，使得从$x$到$y$的路径一定会经过$a$和$b$。

$4 \le n \le 2 \cdot 10^5, n-1 \le m \le 5 \cdot 10^5, 1 \le a, b \le n$

题解：求出割点，如果$a$和$b$其中一个不是割点，那么答案就是$0$。否则求出割点两侧节点个数相乘即可。

题意：有$n$个数$a_1,a_2,\dots,a_n$。你要选出一个子集，然后填到一个矩形里面，使得每行每列里的数都互不相同。求出矩形最大能够多大。

$1 \le n \le 4 \cdot 10^5, 1 \le a_i \le 10^9$

题解：假设矩形大小为$x \times y$ ($x \le y$)，那么只要所有数出现不超过$x$次就是可行的。那么就枚举$x$，把超过$x$次的数截断成$x$。然后$y$就是剩下所有数个数除以$x$。

题意：有一棵$n$个点的树，一开始每个节点上有个棋子。按照边的输入顺序考虑每条边，如果边的两个端点上都有棋子，那么选择其中一个棋子拿掉，并记录所在节点编号。求出这样操作之后，所有可能的节点编号序列有多少，对$998244353$取模。

$2 \le n \le 2 \cdot 10^5$

题意：有$4$块石头，一开始在数轴的$a_1,a_2,a_3,a_4$处。你的目标是把它们移动到$b_1,b_2,b_3,b_4$处。石子的顺序不一定要保持一致。每次可以选择两个不同的坐标$x$和$y$，要求上面各至少有一个棋子，然后把在$x$处的移动到$2y-x$处。

用不超过$1000$步完成。

$-10^9 \le a_i, b_i \le 10^9$

题意：给出一个字符串$s$，令$t_i$是把$s_i$换成*后得到的字符串，求出有多少字符串是集合${s,t_1,t_2,\dots,t_n}$里某个字符串的子串。

$1 \le |s| \le 10^5$