2022省选前集训

20220211省选组总结

T1

观察可知答案至多由两个圈组成，因为一旦方向上有身体就会开始“卷小”，此时无论怎么转都会面向身体的一部分。

由此，DP，分别求出一个圈的顺时针/逆时针答案，再枚举连接点将两个圈合并即可。

T2

没有什么营养的题目。。。
对于每个圆算剩余的周长，由于 $n$ 只有 $1000$ ，可以直接枚举其他圆，余弦定理求相交弧对应的极坐标区间。
将得到的若干个区间求并可得到答案。

T3

分两个part。
part1: meet in middle 求 $ \le lim$ 的点集个数。
part2: 矩阵树定理求每个大小的点集的方案数。

20220212省选组总结

T1

可通过从大到小枚举每一个数，根据其位置快速计算逆序对个数。
由此，容易写出答案的 GF：

\[\left[ x^k \right] \prod_{i=1}^n \frac{ 1-x^i }{ 1-x}=\left[ x^k \right] \left( \frac{1}{1-x}\right)^n \prod_{i=1}^n \left(1-x^i \right) \]

此时左边易用组合数计算， $x^i$ 的系数即为 $i+n-1 \choose n-1$ ，于是问题只剩下右边。
该问题类似背包，容易想到用 DP 做，然而物体太多、值域太大，显然不能直接完成。
注意到 $k \le 10^5$ ，要求的只是前 $k+1$ 的系数，如果我们将生效的 $x^i$ 才称之为物体的话，由于每个物体的价值不同，物体个数至多只有 $\sqrt k$ 个。
不妨设 $f_{i,j}$ 为放了 $i$ 个物体，此时的指数是 $j$ 的方案数（系数），为了每个物体的价值不同，转移采取每次将全部已放物体的价值 $+1$ 的方式，每次考虑是否放入 $1$ ，并且在此过程中可能会“创造”出一个 $n+1$ ，需要减去。具体地讲，转移式如下：

\[\large f_{i,j} = f_{i,j-i} + \left( -f_{i-1,j-i} \right) - \left(-f_{i-1,j-(n+1)}\right) \]

T2

有自环的情况可以多次刷新排列，先不考虑。
按反拓扑序处理出每个点到终点的期望最短距离 $F_u$ 。
考虑一个点从多个点 $v , (u,v)\in E$ 转移过来，点和边权可能会有任意组合，

20220216省选组总结

T1

看到 $k$ 次方一般几个思路：

先计算贡献为 $x^k$ 的有多少个，再统一算（这很蠢所以基本不会用到）。
为了方便统计，同时维护 $0$ ~ $k-1$ 次方，用二项式定理维护。
$x$ 个合法位置有 $x^k$ 贡献的，可以转化为 $x$ 个中选 $k$ 个的方案数（可重）。

这题就是第三种，于是可以将计算有 $x$ 个的方案数转化为有 $k$ 个的方案数。
这里有贡献的位置称之为“谷”（取名于其在平面上的形状）。一个“谷”除了该点外还包括两侧的“山坡”。
以下分为几步计算答案：

计算 $f_{i,j}$ ，这里 $f_{i,j}$ 表示 $i$ 个“谷”，总长度为 $j$ 的排列数。
计算 $g_i$ ，表示可重集合 $S$ 的大小为 $k$ ，元素种类为 $i$ 的 $S$ 个数。
统计答案。

2 是很好做的，直接容斥即可。
考虑 1 怎么做，可以发现若两个“谷”没有相交，它们在计算排列数时是独立的。
于是考虑 $k$ 个谷由多组连续的 “山脉” 拼在一起。
暴力可以跑出“山脉”长度为 3,5,7,9,11 时的方案数，
然后 DP ，转移为 $f_{i+k,j+2k+1} = f_{i,j} \cdot {j+2k+1 \choose j} \cdot w_k$ ，$w$ 就是上面说的“山脉”方案数。

T2

构造一幅图
上层是 $n+1$ ~ $n+k$ 号点，相邻点连权值为 $X$ 的双向边，
下层是 $1$ ~ $n$ 号点，连单向边 $(n+i,j) \quad 1 \le i \le k , 1 \le j \le n$ 。
选的边要求构成最小直径生成树。
也就是钦定 $1$ ~ $n$ 号点度数一定为 $1$ ，这样做保证了两个点 $i,j \quad (1 \le i,j \le n , i \not = j)$ 之间的距离就是原题中给的式子。
于是考虑该图如何求绝对中心 $S$ ，如果在两层之间的边 $(n+i,j)$ 上，则要求 $dis(n+i,j) \ge \text{S与其他点的最小距离最大值}$ ，后者可以直接 dij 求。
否则，直接按照最小直径生成树的方法做。

20220218 省选组总结

栋爷的题呢

T1

将 $a_i$ 取反，那么一个方案合法当且仅当每一个数都有一个位，是由它独自占据的。
那么这些位打上标记，表示被且只被覆盖一次。
设 $f_{i,S}$ 为到第 $i$ 个决策点，目前覆盖的状态为$S$ 的方案数，其中，$S$ 的一位为 0/1/2 分别表示没有被覆盖/被覆盖多次/标记位。
如果直接转移的话容易发现是会算重的，容斥一下，若是标记位的集合为 $S$ ，就给其赋上一个 $(-1)^{\lvert S+1 \rvert}$ 的系数。

T2

将每个询问区间写成点，有相交的就连一根流量为重叠部分$\sum a_i$ 的边。
给每个区间初始的牌堆大小，令其取区间 $\lbrack l_i , \min(r_i , l_{i+1}) \rbrack$ ，即每个牌堆优先分给右侧的区间，于是上面的连边就必须方向向左，表示可从右侧转移 $\sum a_i$ 张牌到左侧牌堆。
每次查询直接使用当前牌堆，空了就找右侧第一个有牌的，需要线段树维护边流量的最小值。

20220219省选组总结

T1 树形图求和

~~貌似跟之前一道省选题几乎一样？~~
首先想的是对每条边统计其所在的树形图个数，乘上边权后相加。
会用到矩阵树定理求树形图个数。
但这样是 $O(m n^3)$ 的，显然过不了。
题解做法是快速维护余子式？
根本没有想到这一边，想到了也不会维护（bushi
嗯。。。考虑将原本矩阵中的度数或者边数改成双元组，即将一条边的贡献变为 $wx + 1$ （$w$ 为边权）的形式。答案是矩阵行列式的 $x^1$ 项系数。
如何理解？
考虑如果只计算一条边时是如何求答案的。
若一个树形图中包括该边，才会被计算到答案里面，那么如果把该边的 1条变成 权值条 ，算出来的也就是该边的贡献。
$x^1$ 项保证了只有一条边的贡献是边权。

讲到这里应该都明白了吧？还是提多一嘴。
由于求 det 需要高斯消元，一般都会想直接将多项式当成原本的方程系数来消元，这就需要用到多项式求逆了（虽然只有两项简单的很？）
实际上完全不需要求逆（我根本没写多项式……），只用对常数项高斯消元即可。
但是这个高斯消元需要~~额外步骤，其实就是~~不仅仅求出下三角矩阵，我们只保留一条对角线，其他位置的常数项要求全部为 $0$ 。
为什么？
由于我们只会取一个一次项，此时若在对角线外取了数，则有至少两个数不在对角线上，这些数中至多只有一个能取一次项，于是必有常数项 $0$ 会被取到，也就没有贡献了。
这样真的好写很多。。。

T2 旅行

还没敲。。。
首先是二分答案，由于题设，旅行一定是按dfn序做的。
那么我们对每个点维护二元组 $(a,b)$ 的集合表示第一天 $a$ 最后一天 $b$。
对于所有 $(a,b), (a',b')$ ，若有 $a \le a' , b \le b'$ ，$(a',b')$ 显然不优，就没必要存在了。
合并儿子时使用启发式合并，根据某种方式排序后就可以前缀最小值+双指针了吧。
排序什么的可以用归并可以保证复杂度是 $O(n \log n \log Ans)$ 的，或者直接 sort 多个 $\log$ 貌似也能硬刚。

T3 字符串游戏

先倒着扫一遍判合法性并找出二元组 $(a_i,b_i)$ 表示 $a_i$ 要移动到 $b_i$ 的位置。
做完第一次操作后一定是由这些 $a_i$ 组成的字符串。
然后设 $v_i$ 表示做完第一次后 可以提供的位置数 ，需要保证能覆盖到对应最左侧的需求位并至少留下一个位置（防止灭种）。
那么每一次操作相当于将 $v_i$ 往前贡献一次，这样的贡献是会保留下来继续对前面造成影响的。
会不会有贡献多了的情况，比如到达了 $b_i$ 后继续将后面的贡献转移到后面？
不会，原因是当 $b_i$ 该过程完成了，前面得到的可行位置就是该过程前的所有位置了，前面的答案也不可能更大。

20220221省选组总结

T1

Burnside引理的基础应用
先考虑旋转，联系裴蜀定理知不动点个数和为：

\[\large \sum_{i=1}^{m-1} {\frac{n}{\gcd(m,i)} \choose \frac{m}{\gcd(m,i)}} \]

发现这只跟 $\gcd$ 有关，于是枚举 $\gcd$ 计算，若 $x \vert m$ ，则 $\gcd(m,i)=x$ 的 $i$ 有 $\varphi(\frac{m}{x})$ 个。可以通过预处理 $\varphi$ ，再 $O(\sqrt m)$ 枚举因数快速计算。

然后考虑翻转，根据 $m$ 的奇偶性分成三种情况，分别计算即可。
大胆写式子，列组合数可以合并。

20220222省选组总结

T1

不会暴力怎么打是我的问题QAQ
总归打了个水法20pts。
暴力是对于每个格有两种删法，确定了哪种后在它之前必要删除的格子和删法就都确定了，这时 $O(n^4)$ 的，35pts。
然而会了暴力怎么就不会满分呢？？？
每个点有两种删法，左或右，一个先删左的格子，它左边的格也一定是先删左的。
于是左右两种方向做，继承前一个格子删的点，复杂度就是 $O(n^3)$ 的了。

T2

对于一颗生成树，每个点的度数是 $d_i$ ，它的贡献就是

\[\prod_{i=1}^n d_i \prod _{i=1}^n w_i^{d_i} \]

所以我们对每个点分别考虑，又结合Prufer序列相关知识，
Prufer 序列与生成树一一对应，每个点的度数则为序列中出现次数+1，序列总长度为 $n-2$
设点 $i$ 的 EGF 为 $F_{i}(x)$ ，则

\[F_i (x)= \sum_{k \ge 0} \frac{w_i^k x^k (k+1)}{k!}=e^{w_ix}(w_ix+1) \]

那么答案就是

\[\begin{align*} Ans&= \left[ \frac{x^{n-2}}{(n-2)!} \right] \prod_{k=1}^n w_i \prod_{k=1}^n F_i(x)\\ &= \left[ \frac{x^{n-2}}{(n-2)!} \right] {\Large e}^{\sum_{k=1}^n w_i x} \prod_{k=1}^n w_i \prod_{k=1}^n (w_i x+1) \end{align*} \]

这里前两个可以预处理，最后一个背包做，最后暴力算答案。
复杂度 $O(n^2)$ 。

T3

子任务：可以对整个序列维护一个大根堆，每次加入一个数，弹出堆顶元素。

由此可以很自然地得出分块的做法。
对每个块维护同样的一个堆，并记录每次加入的数。
整块情况直接做即可，散块需要将前面的记录先结算，此时直接暴力复杂度会退化，注意到寿司和人实际上地位相当，每个数会被修改为经过它的数中最小值，对加入的数维护一个小根堆，从 $l$ 到 $r$ 枚举 $a_i$ ，将 $a_i$ 对比并对调。

其实题目就做完了。。。但是卡常挺悲哀的QwQ
注意不要直接对所有块维护小根堆，而是先用 vector 记录下来，在需要维护整块信息（修改散块前）时用构造函数将 vector 转成 priority_queue ，原因是 push() 比 push_back() 要慢得多。

20220225省选组总结

T1

奇技淫巧增加了！
在边权上做文章，要使 $m^2$ 的其中一个 $m$ 变成 $\log m$ 的话，就加点 $\frac 1 2$ 进去吧！
设一条边还需要的点权为 $w_i$ ，若其所连的两个连通块点权都不超过 $\frac {w_i} 2$ ，这条边就不可能有贡献。
那么对每条边设阈值，扔到连通块上，用堆维护。

T2

设两侧都要经过的点个数为 $A$ ，若 $A$ 是 $4$ 的倍数很容易做，直接每四个数一组拆开即可。
否则，若 $A=4k+2$ ，直接搞就是不行的了，那么如果有两个 $LR$ 中间夹着至少一个 $A$ ，可以利用这个 $A$ 将 $LR$ 发挥出 $A$ 的效果。

T3

听说只要把递增的条件忽略掉就可以了。。。

20220228省选组总结

T2

容易发现答案一定满足 $siz_{ans} > \frac{siz_1} 2$ ，那么把树按DFS序拍到序列上，此时的带权中心一定在答案的子树内，倍增往上跳。
修改操作需要树剖，带权中心需要在线段树上二分做到 $O(n \log n)$ ，最后的倍增向上也是 $O(n \log^2 n)$ 的复杂度。
这是使用线段树维护的情况。

然而我们知道线段树求区间和会有 $3$ ~ $4$ 的常数，况且复杂度已经是 $O(n \log^2 n)$ 的了，没必要为了 $O(n \log n)$ 求带权中心而使用线段树，不如使用树状数组，可以减小最后求答案的常数，牺牲求带权中心的复杂度。

T3

《论爆搜时间复杂度层面的各种优化》

这里详细写写题解做法吧。
里面说的复杂度 $O(2^{\frac n 2}n^2)$ 和 $O(3^{\frac n 2})$ 取决于最后的子集卷积写法，然而前者是一定会有的。

对于每个合法方案，每个点的度数都不超过 $1$ ，于是我们将 $(2i-1,2i) \quad ,1 \le 2i \le n$ 相连，这样做的目的是将边都连起来成为若干个连通块的形式，从而将多条边的贡献统一计算，来加速计算过程。
此时每个点的度数仍然是不超过 $2$ 的，于是一个合法的方案只能由链和环组成。
将每个链和环的贡献分开计算，可以 DP 分别求出点集 $S$ 构成一个链/环的方案数。
求环这里可能会卡住，用断环成链来避免算重，钦定一定断开最左侧点的一条连边（不删上面所说手动加的边），这样无论是环还是链，状态中都只需要记录点集 $S$ 和目前的终点 $x$ 即可。
复杂度是 $O(2^{\frac n 2}n^2)$ 的。

然后把二者合并起来（子集卷积？），同样，为了避免算重，我们钦定每一次新加入的点集 $S'$ 包含 $S$ 中最小点，
如此可以 $O(3^{\frac n 2})$ 直接卷。

总结

时间分配不合理，赛时用了大量时间写T2，快写完时才发现是假的，导致暴力没有时间写。
要有效分析复杂度，较低等级的复杂度可以牺牲为目前必要的最大复杂度，以换取最大复杂度的常数减小。
关于计数题，为了避免算重可以考虑钦定一些条件，要求该钦定会使最终算得的每个方案出现次数便于计算（如都出现相同次数）；
接3 ，T3 在优化时间时，利用图“稀疏”的特性将 $n$ 降为了 $\frac n 2$ ，实质上是将多条边的贡献同时计算了，这给我们的启示是可以将散的东西利用特性组合，由此一次计算多个贡献，达到加速的效果。

JZOJ 总结