省集二轮 Day 3&4

· · 个人记录

模拟赛

random

大意

给你一个长度为 n 的序列，每次修改一个位置，查询该序列建出 ST 表后每段区间极差的平方，数据全部均匀随机。

n\le 5\times 10^5, q\le 5\times 10^5, V\le 2\times 10^5

题解

考虑修改一个位置，可能改变的区间长度是 O(\log n) 的，这个很好证明，均匀随机嘛。

所以我们只需要找到左边右边可能修改的区间范围，然后暴力改 ST 表就行了。

假设这个区间是 [L,R]，注意到 x 在期望下是位于区间中点左右的，因此每个点需要更新的区间是 O(1) 的。感觉很有道理。

于是复杂度变成 O(q\log n)。

tree

大意

钦定叶子节点的权值 [0,n]，每个点的权值是儿子的 MEX，求所有情况根节点的权值和。

n\le 200

题解

首先一个点权值小于等于它的儿子数量。

我们去想象一个树形 dp f(u,i) 表示 u 的权值是 i 的方案数，然后考虑这个玩意的转移发现不对劲，因为你转移形如一个积和式（行列式去掉符号），然后这玩意是图灵奖的，就做不了。

考虑指数做法，首先一个显然的做法是容斥，如果一个点它儿子的度数的最大值比较少，那你直接枚举到度数最大值就可以停了，剩下的叶子由于度数是满的但是每个的方案都一样，你可以随便一个 dp 搞掉。

第二种做法是状压，考虑按照儿子值域从小到大，记录当前考虑 1\sim i 的值域，现在还没确定的儿子集合为 s 的方案数，转移依然不考虑叶子，然后最后把没填的用叶子填上，你需要再记录一维 j 表示被叶子填的数量。

不要直接转移子集，上 SOS dp 可以做到 2^{son}poly(son)。

这个是蛾子数量很少的时候可以这么干。

想办法拼接一下两个做法。

对值域分块，对所有儿子满足度数小的跑容斥，否则跑状压。

但是不幸的是这两个之间是有关系的，所以你还需要在容斥的时候记录是否选到了状压的那些儿子，这样会变成一个 2^{B+l}，看起来很完蛋。

平衡一下复杂度这个 B+l 大概是 \sqrt {2n} 的，但是我不想考虑了。

坑了。/ll

gen

题目略了。

题解

考虑一次询问，直接就是个轮廓线。

考虑带修改，我们去把前后缀拼起来，直接拼是 O(4^npoly(n)) 的，考虑优化，我们枚举一个位置，用类似 FMT 的思路每次搞掉一位然后算贡献。

对斜线 dp 并且对于每个位置选择较短的那条斜线转移可以去掉两个 n，非常神奇，复杂度变成 O(2^nn)

杂题选讲

LOJ2764 JOIOI 塔

二分！！ useful algorithm！！

从后往前找，碰到一个 O,J 是好办的，但是碰到一个 I 你可以选择新开一个串或者干掉一个串。当你二分答案之后如果当前串的数量比 mid 小那肯定新增啊不然肯定减少啊。

你发现二分确实非常强大，他相当于提前知道了一个信息，然后你就可以照着这个信息开搞了。

LOJ3666 沙堡 2

沙堡题。

首先这个东西看起来很阴间，考虑做一个转化。

对于一个矩形，显然每一个位置只能连到它的后继，不然它的后继就没人连了，因此我们对每个位置向它的后继连边，得到的图合法当且仅当只有一个点入度为 0。

考虑维护前缀和，注意需要特判距离边界为 0 和为 1 的情况，前者是它连不出去，后者是它可能会被边界上一个奇怪的边连到，因此你讨论 25 种情况就行了。

但是太难讨论了！直接枚举三个边界是否顶到 0,1,2，做 81 次，这是好维护的。

考虑一个套路是枚举上下的 bound 然后从左往右进行一个线性 dp，这也是好维护的。

## UOJ578 校验码 推柿子好题。 考虑把 $q(x,c)$ 当中 $x$ 的次数为偶数的质因子掏出来，因为你发现这个东西它几乎是积性的。当一个数只剩下奇数质因子的时候就是 $1$。 当两个数乘起来的时候，我们依然掏出来所有的偶数次数的质因子，剩下的东西只有可能是两个一起组合起来得到一个偶数，因此其实就是 $gcd^c$。 综上，我们有： https://skip2004.blog.uoj.ac/blog/6532 $$ \sum_{i=1}^n \mu^2 (i)=\sum_{i=1}^{\sqrt n}\mu(i)\lfloor\frac {n}{i^2}\rfloor $$ 容易验证柿子的正确性，可以 $O(n^{1/3})$。 对于所有 $n=\lfloor N/i \rfloor$ 求这个柿子，可以通过根号平衡做到 $O(L+\sum_{i=0}^{M/L}(M/i)^{1/3})=O(M^{1/3})

UOJ280 题目难度提升 sol

考虑 a_i 互不相同时，我们填尽可能大的数 x，要求 x 填完之后最小的数可以填。

当 a_i 有相同元素时，加上记 x=y，那么我们一开始先填这俩，然后大->小->大->小这样下去直到把小的全部填完，然后再做互不相同，这样一定是最优秀的。

模拟是trivial的，或许。

cf16-final J Neue Spiel ×

我们首先做一个匹配，把每个点向四个方向连边，然后跑二分图匹配，这样可以判断无解。

如果有解，那么你考虑我们一定可以对于每个点找到它上一个需要走掉的点，把这个点指向那个点得到一个图，如果是 DAG 那么做完了， 如果不是的话那么一定有环，找到一个环之后把这个环的所有顶点顺次转一个角度就可以干掉这个环。

考虑这个操作一定只能进行有限次，令 \varphi(i,j) 表示 (i,j) 朝向的方向点的个数，显然这个东西求和是 n^3 的，每次缩环让势能减小，于是搞定了。

我们只需要找到一个 O(length\ of\ a\ circle) 的做法去干掉每一个环就可以保证复杂度正确。

dfs，每次从一个点开始，如果找不到那么删掉路径上所有节点，否则改掉环之后从原位置继续dfs。

CF1687E Become Big For Me×

对所有质数做扩展容斥定理。

暴力掏出来有用的数，只有 14 个。

UOJ431 time map

线段树维护 ((x^a)|b)&c

广义线段树的一条左链/右链代表的区间一定有一个端点相同。

UOJ327 去月球×

发现可以差分，建 trie 变成求 LCA。

UOJ425 strings×

大力出奇迹

另外一个模拟赛

T2

首先 n^3m 的 dp 是好做的，只需要枚举最大值，判断是否合法。

然后你联想到 NOI2019 机器人，直接进行一个插值就搞定了。

考虑 n^2，我们把原序列的笛卡尔树建出来，如果能建出来那么你直接树形 dp 就行了。

但是你不一定能建出来，没关系，考虑一个 -1，它的father是不确定的，但是和其它点几乎是没有影响的，只会有一个它小于谁谁谁的情况。

我们对着这个东西 yy 出来一个类似于扩展笛卡尔树的东西，当一对儿子的father不确定的时候，我们把它们放在同一层，即它们同为某个点的左儿子或者右儿子。

如此建完之后容易发现这棵树的信息是完备的，在上面树形 dp 可以做到 O(nm)，直接进行一个插值就 O(N^2) 了。