最后

· · 个人记录

2023.3.25 距离联合省选 2023 还有一周。

不知道这是否会成为旅途的终点。

NOIP 失利之后，我跌跌撞撞走到了这里。

现在反而没那么紧张了。

我为这个梦想已经付出了太多太多。

我的 OI 不会被 T1 没换行的这 100 分而击倒的。

最后一周了，不想做题，也做不动了，复习一下前面做过的题，当个杂题选做好了。

一些要记着用的东西：

联合省选 2022 D1T1

简单模拟题，把字符串存下来然后搜索即可。

标识符和任意 ASCII 的区别比较丁真，多读几遍应该没啥问题。

但这种题很阴间啊，因为不能对拍，还是应该自己造几组。

联合省选 2022 D1T2

把一组 (\max,\min) 放在 \max -k 上去统计贡献，那么相当于对于每个 i 求出所有区间都在 [i,i+k] 的方案，然后容斥一下减去 [i,i+k-1] 的方案。

然后考虑一下选出一条链后，每一个区间对于每个 i 的贡献是一个分段函数，可以分成三段。

复杂度 $O(n^3)$，小卡常。 小技巧：多次 dfs 可以改成先 dfs 一次记录 dfs 序，后面就不用递归了，这样会快很多。 ### [联合省选 2022 D1T3](https://loj.ac/p/3702) 不会，感觉是流。 大概会了，没代码。 先考虑性质 C，也就是所有上下组合给的贡献相同。 就是考虑由于要连成一条链，所以每个点一个出点一个入点，然后去跑二分图匹配，唯一的问题在于可能会出现环。 重要的条件是**每个人都会有一条学术消息**，因此在前面或者后面补上就可以破环。 没有性质 C，证明一下得到不满足性质 C 的边一定匹配最优。 怎么说，感觉就是顺着思路，然后瞎证明一下的题，看来还是比较需要勇气。 ### [联合省选 2022 D2T1](https://loj.ac/p/3703) 把每个素数看成是二进制一位，那么 $<\sqrt{a_i}$ 的可以状压，然后 FWT 一下，没啥意思。 大样例很弱啊，还是要对拍。 ### [联合省选 2022 D2T2](https://loj.ac/p/3704) 建出括号树，贪心从上向下。 $y=1$ 的部分是简单的，直接贪，用 set 维护。 $y\ne 1$ 的情况讨论一下所有数都在同一层的情况，发现转移到下面一层有贡献的只有最大值和最小值，中间的可以乱选。 但是只有两个数时需要特殊考虑。 总而言之是丁真分讨题，讨论仔细一点就好了。 ### [联合省选 2022 D2T3](https://loj.ac/p/3705) 对于每个子树，考虑对上面的贡献，显然是上面下来一条链，还有这个子树给外面的贡献，设到状态里，可以得到一个三维 dp，转移直接大力讨论那条边先选即可。 暂时只会这样的 $O(n^3)$，有 $44$ 分，考场上可能最多也就写到这里了。 这样的状态只需要记录下面一条链到那个点，这样就可以把空间变成 $O(n^2)$ 了，可以过多一点。 最后的不想想了，太精神污染了。 ### [ABC295Ex](https://atcoder.jp/contests/abc295/tasks/abc295_h) 忍不住新开了一个题。 一列一列 dp，记录上面到下面前缀还有那些列活着，记录到状态里。 然后轮廓线 dp，要么是上面有，要么是左边一个前缀。 $O(nm2^m)$，滚动数组一下空间是 $O(2^m)$。 卡常小技巧：有多维数组，把小的放到前面会变快（显然）。 然后 vector 每次重新定义 < 枚举每一个赋值 < memset。 ### [CF1798F](https://codeforces.com/contest/1798/problem/F) 不会做题了。 用 [uoj771](https://uoj.ac/contest/79/problem/771) 的结论，任意 $2n-1$ 个数总能凑出 $n$。 那么把 $s_i$ 从小到大排序，然后前面的都可以暴力 dp 凑出，最后剩下的差多少就补多少即可。 ### [loj 6406](https://loj.ac/p/6406) 直接考虑第 $i$ 个人增加了 $a_i$ 的概率，这个是 $$ \frac{\binom{n}{a_1,a_2,...,a_n}a_1!a_2!...a_n!}{\frac{(n+d-1)!}{(n-1)!}} $$ 注意到这是个定值，所以所有方案概率都一样，算出总方案和总概率即可。 一个人一个人 dp 比较困难，考虑一行一行 dp，设 $f_{i,j}$ 表示用了 $i$ 个，还有 $j$ 个人继续的方案数。 概率期望题能不能给个模数啊。 ### [nadafes2022_day2_e](https://atcoder.jp/contests/nadafes2022_day2/tasks/nadafes2022_day2_e) 两维问题，直接考虑去独立。 $$ \min(|x_i-x_j|,|y_i-y_j|)=|x_i-x_j|+|y_i-y_j|-\max(|x_i-x_j|,|y_i-y_j|) $$ 然后后面那个转坐标就两维独立了，独立后就是简单的计数问题。 ### [abc221G](https://atcoder.jp/contests/abc221/tasks/abc221_g) 依然考虑两维独立，会发现现在已经独立了，要让他们合并做比较好，那么原来的左边是一个十字，现在转成一个 X，这样两维不影响，分别做即可。 bitset 一下。 ### [AGC056B](https://atcoder.jp/contests/agc056/tasks/agc056_b) 好难，网上的题解写的都比较问号。 本质是一个映射，但是网上题解所说的字典序最小对应没看懂有啥用。 就是考虑这个东西如果确定了一个区间最大值，那么就把区间分成两半，唯一的问题在于可能会有重复，所以选出的这个最大值是有要求的。 我们对于一个 $x$ 序列这样构造：每次在所有被区间包含的，所有可以放的里面，选最小的那个位置去放。 既然被区间包含，那么必然需要一个区间来限定这是最左边方案，也就是说需要一个区间包含这个点和他左边的最大值，而右边可以乱填。 然后区间 dp 即可，记录 $f_{i,j,k}$ 表示区间 $[i,j]$ 中，最大值位置为 $j$ 的方案，前缀和优化即可。 ### [CF1732D2](https://www.luogu.com.cn/problem/CF1732D2) 神秘复杂度题。 首先考虑没有删除，那么直接开 map 记录每个点有没有被删，然后暴力跳即可，如果多次询问同一个 $k$，那么就从上一次停下的地方继续走，复杂度应该是单 $\log$。 然后带删除，一直在想线段树分治，但是没啥用啊。 考虑如果把 $k$ 经过的点上去放一个 $k$，如果删去一个点就记录一下，然后询问 $k$ 的时候先看看前面有没有被删去的点，否则继续前进。 复杂度不知道。 ### [联合省选 2021 D1T2](https://loj.ac/p/3500) 直接构造比较困难，考虑先搞出一个不符合 $[0,10^6]$ 的方案，然后来调整。 调整，会发现一行把第 $i$ 个元素加上 $(-1)^i$ 后，依然满足条件。 因此设第 $i$ 行操作 $a_i$ 次，第 $j$ 列操作 $b_j$ 次，就可以列出不等式，然后改一下就可以差分约束了。 ### [联合省选 2021 D1T3](https://loj.ac/p/3501) 从小到大删点，可以发现如果 $(u,v)$ 中途需要经过 $x$ 满足 $x<v$，那么 $x$ 一定在前面就被删掉了，因此相当于 $u \to v,v\to u$ 上经过的点都要求 $\ge v$。 简单的想法是直接 Floyd，每次加一个最小的点，复杂度 $O(n^3)$。 然后考虑边数比较小，枚举 $v$，相当于只保留 $[v,n]$ 的点，然后最短路，可以 dij 做到 $O(nm\log m)$。 考虑动态加边然后维护可行性，这个也比较简单，只有当前边会产生贡献的时候再去跑 bfs 即可，总复杂度 $O(nm)$。 ### [[ZJOI2012]灾难 ](https://www.luogu.com.cn/problem/P2597) 复习一下支配树，这个是 Dag 部分。 先建一个超级源点，连向所有入度为 $0$ 的点，这样支配变成了 $1$ 到 $v$ 的路径必须经过 $u$。 首先支配关系形成一棵树，若干个支配对会形成一条链，因此一定没有环。 考虑 dag 上咋做，那就拓扑排序，只需要找到支配一个点的深度最小的那个点即可，那么建出前面的支配树，然后加一个点就相当于对于所有它的入度点求个 lca，然后挂在它下面。 加点求 lca 可以倍增。 ### [联合省选 2021 D2T3](https://loj.ac/p/3504) 支配形成树，先建出来。 然后考虑加一条边，那么显然是一个点 $u$ 的被支配集变小了。 也就是说可以通过其他路径走过来，不经过 $u$ 到根的路径上的所有点。 加入的边如果是 $(x,y)$，那么必然要经过这条边，也就是 $1$ 到 $x$ 路径上的点都要经过。 然后从 $y$ 出发，去一个点 $z$，看 $z$ 的被支配集会不会变。 容易发现如果 $y$ 到 $z$ 上的点没有经过 $1..x$ 路径以及他们的儿子的点，就合法，因此 dfs 一下就没了。 复杂度 $O(nq+n^2)$，跑的很快。 ### [联合省选 2021 D2T2](https://loj.ac/p/3503) 简单题，考虑直接状压，记录上面一个在哪里，选 $b_i$，这样是 $O(2^nm^2n^2)$ 的，过不去。 考虑由于 $b_i$ 单调不降，因此考虑横着放即可，然后就不用记录上面一个了，复杂度少一个 $m$。 ### [ABC212G](https://atcoder.jp/contests/abc212/tasks/abc212_g) 用原根，把乘法变成加法。 $$ x=r^a,y=y^b $$ $$ an\equiv b\pmod {p-1} $$ 对于一个 $a$，合法的 $b$ 有 $\frac{p-1}{\gcd(p-1,a)}$ 个，然后欧拉反演一下車没了。 ### [CF1706D2](https://codeforces.com/contest/1706/problem/D2) 先整除分块，然后考虑对于一个 $\min$ 去算最小的 $\max$。 这个东西对于分出来的每一个区间可以看成是一个差分，暴力存下来，空间会爆。 事实上这个东西就是一个区间修改，然后就线性了。 ### [CF1706E](https://codeforces.com/contest/1706/problem/E) 若干个点形成的连通块，可以先知道他们的 lca，然后相当于每个点到 lca 的路径取个并，这样可以直接线段树了。 但是不需要，因为这些点的连通块还可以看成相邻两个点路径的并，然后就没了。 用重构树想会简单一些。 ### [loj3310](https://loj.ac/p/3310) 遍历所有边，先想到欧拉路。 把 $s,i$ 连一条边，那么就是欧拉回路，然后形成若干连通块。 先相邻的奇点匹配掉，然后剩下的要求联通，最小生成树即可。 ### [联合省选 2021 D2T1](https://loj.ac/p/3502) 考虑路径可以看成是 $x$ 到 lca，lca 到 $y$ 两条。 $x$ 到 lca 上，只需要每个点记录它上面点权是它加一的点的位置，然后只需要找到第一个 $1$，就可以倍增跳了。 右边那个不太一样，因为不知道终点是啥，所以需要二分一波，二分出个 $u$，那么要算 $y$ 上面第一个 $u$，这个不太好搞。 直接离线一波，然后维护每个点到根路径上的每个值在哪里即可。 ### [P6577](https://www.luogu.com.cn/problem/P6577) 学习了一下 KM。 对偶之后，相当于顶标加起来大于边。 当 $vx+vy=edge$ 的时候，这条边为相等边，只要找到一个相等边构成的完美匹配即可。 不断扩展，每次加入一个点，然后左边整体减，右边整体加来调整。 复杂度 $O(n^3)$。 ### [P4980](https://www.luogu.com.cn/problem/P4980) 复习一下群。 $$ Ans=\frac{1}{|G|}\sum_{g\in G}X^g $$ $$ = \frac{1}{n}\sum_{i=1}^n n^{\gcd(i,n)} $$ $$ = \frac{1}{n}\sum_{d|n} n^d \sum_{i=1}^n [\gcd(i,n)=d] $$ 别急着上莫反，右边那个东西是欧拉函数。 $$ = \frac{1}{n}\sum_{d|n} n^d \varphi(\frac{n}{d}) $$