mygr main()

模拟赛， T2 发现不用边分治（ 变成启发式合并即可，考虑合并较小较小元素，较大的部分开桶记录即可 考虑将其分为两部分：”被完全包含的mex段与未被完全包含的mex段“ 有状态转移方程 $f_{i}=\max\limits_{j\in{i-k+1,i-1}}f_{j-1}+s_imex_{i,j}-s_{j-1}mex_{i,j}$ 对于被完全包含的段，可以将 $mex_{i,j}$ 视作斜率，$-s_{j-1}mex_{i,j}+f_{j-1}$ 的最大值视作截距 作李超树，mex变化对应每段的最优决策点不变 对于未被完全包含的段，由于只有一段，因此 $mex$ 固定，同时 $s_i$ 为定值，故 $s_imex$ 为定值，故可以将 $s_{j-1}$ 视作斜率 考虑固定右端点 $r$ ，那么一个合法的 $l$ 需要满足 $\max\limits_{i \in [l,r]}pre_i \le l$ 显然是一个后缀，故可以二分 或者说，设 $f_i$ 表示以 $i$ 为右端点的最小左端点，那么为 $f_{r}=\max\limits_{i\in [1,n]} pre_{i}$

模拟赛 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$ 个左括号需要被匹配的方案数 其实就是不过...

![[20250206.pdf]] 模拟赛 T1 感觉跟之前查询最大值那题很像 $$f(x)=(x \oplus a)-b$$ $$f(x_{i}) \times f(x_{i+1}) \le 0$$ 此时答案由两种可能构成： $$\begin{cases}(x \oplus a)-b=0 \ (f(x_i)) \not = (f_{x_{i+1}})\ \end{cases}$$ 上面那个显然是可以一棵trie树维护的 对于下面那个，我们先考虑判断是否存在合法答案，即是否所有数都是同号 如何判断一个区间是否有正负数呢？其实也就是判断区间内 $\oplus a$ 的最大值和最小值即可 这时候就可以上我们那四个模板了，看看哪个最适合这道题 因为单点修改，所以主席树就不合适了 我们考虑一个弱化版的问题：从左往右数第一个大于 $b$ 的数在哪里 显然找出第一个大于与第一个小于后，必定有一个满足答案 所以可以考虑在trie树上二分 对于找第一个大于的问题，我们可以考虑在trie树上每个节点维护一个 $Min$ 表示最小下标 然后在搜索过程中若有 $\oplus a$ 后与 $b$...

模拟赛 T1 首先不难发现操作2的使用范围一定是一个后缀 ，因为若并非后缀，则中间这段的修改其实并不会对答案产生影响，每次的操作数始终为 $a_n-a_1$ 我们发现实际上操作1是不受控的，每次必定只在产生差距的地方造成影响 不妨猜想后缀推平只会进行一次？好像挺显然的，若不是一次则后面再修改一定会花费更高的代价 问题就变成了如何去计算一段前缀跑 k 次的代价 发现每一段区别段的贡献是一个分段函数，所以可以考虑经典的爆仓线段树 然后就做完了？ T2 逆向的矩阵树定理？ 假设该图为一个DAG，那么有生成树数量最大为 $$\left(\frac{220}{V}\right)^{V}$$ 其是否能够比 $10^{18}$ 更大？ 显然可以 试想一下是否 DAG 的生成树数量一定比一般图更大 哦好像不行，要是 K 中出现了一个非常大的质因子那就没法构造了 但是质因数分解能拿36分（ 发现数据范围中 K 单调递增，考虑是否瓶颈在于K 总不能这真的是构造矩阵吧 外向树是入度 我怎么去构造一个矩阵，使得其行列式为 $K$...

模拟赛 T1 不清楚，润 感觉可以状压 哦好像确实可行 考虑设 $f_{i,S}$ 表示当前在第 $i$ 行，从左侧继承而来的集合为 $S$ 不妨设 $2nm-n-m=S$ 一条边出现一次的概率是 $\frac{1}{S}$ ，两次则为 $\frac{1}{S^2}$ 则一条边出现的概率为...

模拟赛 T1 是不是跑个类似单调栈的东西就行？ T2 考虑转化为计数问题 考虑一个最简单的dp，设 $f_{i,j,k}$ 表示拥有三种线段的数量的情况的答案 红 绿 杂 那么枚举所有合并的可能 当 $i,j=0$ 时，答案是显然的，其实答案最后面都可以转为杂色段的情况的贡献 当绿段与红段合并时，转化为杂色段，贡献为 $\frac{(4ij)}{(2i+k)(2j+k)}f_{i-1,j-1,k+1}$ 当红段与杂段合并时，转化为红色段，贡献为 $\frac{(2ik)}{(2i+k)(2j+k)}f_{i,j,k-1}$ 当绿段与杂段合并时，转化为绿色段，贡献为 $\frac{(2jk)}{(2i+k)(2j+k)}f_{i,j,k-1}$ 当绿绿或者红红合并时，转化为纯色段，贡献为 $\frac{(\frac{i(i-1)}{2})}{(2i+k)(2j+k)}f_{i-1,j,k}+\frac{(\frac{j(j-1)}{2})}{(2i+k)(2j+k)}f_{i,j-1,k}$ ![[day1.pdf]]

[[2025.1.20]] [[2025.1.21]] [[2025.1.22]] [[2025.1.23]]