~10-11 部分题解。

密码xoi。

删去了部分一句话题解。

10.1

T4 euclid

看 $$ 最长的 $$ 的位置。

建出后缀数组后，发现本质上就需要查询 $$ 前面第一个 $$，以及后面的第一个 $$。

直接做有些麻烦。

换维后，把 $$ ，一个个插入，变成了可持久化线段树上二分，就好了。

---

10-2

T1 safe

首先逆序对二分图，直接转成顺序对两个团。

顺序对一定有传递性，所以我们选出来的必定是两条上升子序列。

判定性问题不难。可以 $$ 表示做到 $$ 最后是否取负，另一个子序列结尾最小值。

那最优化就可以按位贪心。如果这一位取负的话，后面能接上，那就可以，否则不行。

T3 euclid

妙妙博弈。

考虑如果现在在 $$ 这个点，如果 $$ 这个子树对方必赢，那不可能走到 $$。

否则我们对于对方必输的点维护一个 $$ 表示这个点 $$ 在至少拥有多大的时候，在这个点开始能赢。

如果他能到达能对面输的点，并且这个点权值要小于当前点权值，他能赢。

---

题解感觉就很妙妙呀，就是不管是谁，每次都只能走权值更小的点，否则是负收益。

然后看谁走最后一步。完事了！！！

T4 keter

很怪的题呀。

conclusion 1:

$$ 里面整点凸包最多有 $$ 个点。

考虑选的斜率 $$ ，一定是一条斜线一条斜线的 $$。

然后求和就是 $$ 级别的，点数是 $$ 级别，那自然是 $$。

直接背包的复杂度是 $$，$$ 是可选斜率个数。

根据结论，我们可以换维做到 $$。

然后根据一个贪心，如果我们要选 $$ 那么 $$ 一定被选光了。

conclusion 2:

合法的 $$ 级别也是 $$ 的。

证明很不严谨，并且似乎常数很大？

$$

这个 $$ 不太会分析，那就当成是 $$ 的吧！！。

$$

在 $$ 的时候，$$ 有的区分。

分别积分一下，得到 $$ 的界。

然后 $$ ,总复杂度 $$

---

10-5

T3 euclid

记住后缀排序，基数排序是从后往前排的。

感觉从高位往低位做很困难，但是反过来就容易了。

从低向高合并，如何判断这一位是 $$ 还是 $$，递归到子问题！

也就是将新的字符串重新标号，然后变成 $$ 的子问题。

T4 euclid+

赞美保证有解。

首先一个obs是如果 $$ 那么能得到他们的交，一定也合法。

然后由于一定是长的区间包含，短的区间；不难想到从短往长去合并区间。

由于保证有解，我们一定要么没有与其相交的区间，要么相交。

如果此时被覆盖，那么那两个拼起来的区间，一定和该区间有交，那么把两段交拼起来。也是合法的。

不相交正确性显然。

相交的话，考虑与他前面交的极长那段，和后面极长那段，不难发现这两段都是合法的。然后本质上就是不交情况。

然后拿并查集维护连续段就好。

10-6 skipped

10-8

T3

式子简单的，就折线嘛。

主要是如何处理 $$。

我们可以直接扩域 $$ 这样乘法运算就是，互质部分直接乘，因子部分直接加。

求逆也很简单，做完了。

T4

发现这东西类似链覆盖呀。

考虑链覆盖的时候我们在干什么，我们最后减去了链边的贡献。

也类似的考虑，我们先让每个状态直接连到 $$ 然后，考虑合并两条链的贡献。

那就直接减去原先这条链的贡献，就好。

网络流建模，就是左边的点，连向右边的点，一个右边的点，实际上会回到左边，接上继续做。

然后直接费用流就行。

10-11

T3

李超树/维护凸包。

现在想想，是个很板子的李超。自己却做成了“维护最大子段”。

T4 euclid

Q1

如果我们知道了每个连通块的大小，如何知道构成的树的个数。

$$,$$

$$

所以答案就是 $$。

然后我们先二项式反演一下。变成求钦定 $$ 条边相同的答案。

然后一个连通块的贡献就是 $$ 了。

发现如果我们要去维护 $$ 那么必然会 $$。

正确的解决办法是考虑 $$ 可以变成在这个连通块里任意选一个点的方案数。

然后此时我们只需要知道最上面的点所在连通块被没被选即可。

这样变成 $$ 的了。

---

10-11

T3

积和式的求解是难的，但是判断积和式是否 $$ 是容易的。

这个题如果我们钦定后，那么判断积和式减去他的超集是否为 $$ 就好。

所以还是经典套路，把每条边随机一个权值，放入。然后计算行列式的值。

值得注意的是：行列式交换两行是要变号的！！！！。

T4

被暴力过了。/kk

树上 $$ 背包是存在 $$ 的做法的，直接按 dfs 序做，如有神助。

当然这只能处理包含根的答案。

再套上个点分树就好了。