模拟赛

题面

T1

假设从 $l$ 到 $r$ 有两条路径 $A,B$，且 $B$ 的字典序更大，则走 $B$ 一定比走 $A$ 更优

所以我们发现这个决策也是有比较的，考虑设 $f_{i}$ 表示到达第 $i$
个位置的最小字典序字符串，那么有

$$f_{i}=a_i+\max_{x_i-x_j \in [L,R]}f_j$$

其中的加号表示集合加

我们重定义一下字符串比较的方式，通过比较某类数的数量的LCP来判断大小关系

发现这跟之前那题很像，都是改变一部分的值，所以考虑使用 主席树+哈希 优化整个修改的过程，我们就得到了 $O(logn)$ 的比较方式

然后我们再开一棵线段树表示区间比较的最大值

然后就结束了？

两个log，害怕

哦滑动窗口，不用了

事实上是一个log的

T2

上下界网络流？

似乎需要考虑成环

T3

感觉这个 “总的左括号数” 就长得很 GF 的样子

考虑设 $f_{i}$ 表示插入 $i$ 个左括号的合法箱子数，考虑求出其对应的 GF

卡特兰数吗？

考虑设 $g_{i,j}$ 表示插入了 $i$ 个括号，剩余 $j$ 个左括号需要被匹配的方案数

其实就是不过 $y=x+1$ 这条直线的方案数，那么有 $f_{i}=C_{2i}^{i}-C_{2i}^{i-1}$

我们都知道有 $$[x^n]\left(\frac{1}{1-x}\right)^k=C_{n+k-1}^{k-1}$$
欸等下，是不是跟那个旅游那题有点像

考虑根号分治

设当前插入的括号数为 $x$

若 $x \le \sqrt k$ ，则因为数量较小，则背包枚举其加入

若 $x < \sqrt k$ ，则

不对好像，n个盒子

我感觉还是要GF，处理这种不均等递推的问题

但是这个GF实在是处理不出来，可能 EGF可以？

算了感觉 $O(n^3)$ 极限了

$$
C_{2i}^{i}-C_{2i}^{i-1} \Rightarrow C_{2i+2}^{i+1}-C_{2i+2}^{i}\

$$

$$\frac{i+1}{i}C_{2i}^{i-1}=C_{2i}^{i}$$
$$C_{2i}^{i}-C_{2i}^{i-1}=\frac{1}{i}C_{2i}^{i-1}$$
$$C_{2i+2}^{i+1}-C_{2i+2}^{i}=\frac{1}{i+1}C_{2i+2}^{i}$$

下午讲题

不妨设 $F$ 表示卡特兰数生成函数

$$\begin{eqnarray} && x^m^n \
&=& \sum_{i=0}^{n}C_{n}^{i}(-1)^iF^{n-i} [x^k]Fx^{ik} \
\end{eqnarray}$$

设 $T=[x^k]F$

$$\begin{eqnarray} &=& \sum_{i=0}^{n}C_{n}^{i}(-1)^iF^{n-i} Tx^{ik} \
\end{eqnarray}$$
问题就变成了如何去求 $[x^{m-ik}]F^{n-i}$

$$\frac{72}{n}^{n}$$