联考好题集锦

考试题

2022-0221 yyl

考虑带权重心的条件，其子树和一定要大于等于 $\lfloor {sum\over 2} \rfloor$ ，这是因为要考虑其父亲的那棵树。

然后要求深度最小的重心，也就是严格大于$\lfloor {sum\over 2} \rfloor$

考虑把树拍平到 dfn 上，则 dfn 序列上的带权中点一定在重心的子树内。

于是直接倍增即可。

2022-0221 dfs

十分有意思的做法完全忘记了…

考虑 $n$ 个点至多 $n\over 2$ 个匹配，且每个点度数不超过 $1$ ，考虑在所有 $2i,2i+1$ 之间连上一条边，这样每个点度数就不超过 $2$ 了，形成了若干环和链。

考虑我们已知信息中 $2i,2i+1$ 是一定连在一起的，于是把他们看成一个点，$dp$ 统计连成的环和链的个数。

$dp$ 大概是，两个状压，然后因为要保证不算重，所以要钦定此时链 / 环内最大的元素，合并答案就做个枚举子集就好了。

因为合并了点，所以复杂度是 $\mathrm O(2^{n\over2})$ 乘上一些东西的。

2022-0222 game

每个人希望自己走的比另一个人多走几步

预处理从每个点出发，能比别人多走几步

预处理十分玄妙，也可以看做一个 dp

foR (u, n, 1) for (auto v : to[u]) 
    if (col[u] == col[v]) ckmax(res[u], res[v] + 1);
    else ckmax(res[u], (!res[v]) ? 1 : 0);

背包合并即可

2022-0222 perm

nb 题

先转换一步限制，任意区间内，不能存在 $(a,b),(a,c)$ 而不存在 $(b,c)$ 。

你看这个二元组的排列，十分不好看，于是你看做一条条边。

限制就相当于是任意区间内的边拿出来具有传递性。

任意区间内限制不好满足，但发现区间 $[l,r]$ 满足传递性其实只要保证 $[1,r],[l,n]$ 满足就好，也就是只要保证每个前缀满足，每个后缀满足就好。

也就是对于一个前缀建图，它的补图也满足具有传递性就好。

一个 DAG ，本身与补图都具有传递性，这样的图是不多的，只有 $n!$ 个，原因是你可以把每个排列与一张这样的图做一个双射关系，大概是你拿出一个排列来，对于每个逆序对连边，因为两两偏序关系唯一，发现这样的图就是满足本身与补图都具有传递性的，

然后你就可以对于每个排列 dp 了，使用康拓展开给排列编号，从逆序对小的转移到逆序对大的，每次转移新加一条边，也就是找到一个 $p_i<p_{i+1}$ 将其交换，根据逆序对的性质我们知道这恰好变化 $1$ 。

复杂度 $\mathrm O(n!n)$ 。

2022-0224 藏弓待用

。。。套路题不想讲

记下来是因为这是我搬过的一道题，但赛时转换错了一个 “经典模型” 自闭了一场。。。最后 10min 才冲出来

分块优化 ddp

2022-0224 山泽麟迹

先考虑一个柿子：

$$E(u)=P\times E(las) +(1-P){1\over |s|}\sum E(v) +1$$

暴力高消可以获得？分

由于这是棵树，在树上有明显的序，考虑 $u$ 时，$v$ 已经算出，把 $E(u)$ 看做 $y=kE(fa)+b$ 的形式，原柿化为：

$$E(u)=P\times E(fa) +(1-P){1\over|s|}\sum (kE(u)+b)$$

手玩一下即可。

2022-0224 降众天华

随便选个点，每个点到他得到若干向量

把向量看成高斯整数 gcd 后，发现可以构造一个方阵是的两边的基底是 $gcd,igcd$ ，于是每组向量除 gcd 得到最大最小值，得到长宽

2022-0225 给国与地震

发现一个显然正确的贪心，每次找一条满足条件的字典序最小的合法边加入

发现这样会 T，发现一条边若还差 $s$ 合法，而两边增加量 $< {s\over 2}$ 他不会合法，于是给每条边设一个阈值 $s\over 2$ ，搞个 $set$ 记录每个联通块出边，每次启发式合并时找到增加量达到阈值的边进行 check ，若不满足则更新阈值

2022-0228 排列

厉害题！

首先期望是个假期望，乘个 $n!$

这个 $k$ 次方不好处理，于是考虑它的组合意义，相当于是，对于所有的谷，我们在其中选择 $k$ 个的方案数，可以重复选。

注意这里我们把对于每个排列贡献求和转换为了对于谷选 k 个排列方案数的求和，于是接下来的讨论我们不需要考虑没被选择的谷对于原柿子的贡献，这里笔者产生过误区

我们把被选中的谷拿出来组成一个集合，由于可以重复选，这个集合的大小是小于等于 $k$ 的，我们可以 dfs 这个集合的大小，除去这个集合的用个组合数可以简单解决，dfs 时，我们每次要 dfs 一个连续谷段的大小，它的贡献是给 $2q+1$ 个数字填入 $2q+1$ 的序列中且满足谷性质方案数，因为 $k\le 5$ ，简单爆搜可得一个表

2q+1:Ans
3:2
5:16
7:272
9:7936
11:353792

2022-03-01 寄

dp 技术不够高超所以寄了

设 $f_{i,j}$ 表示 $i$ 节点子树内 $j$ 个节点未匹配都汇聚到 $i$ 的最小代价，设 $g_{i,j}$ 表示 $i$ 节点内所有节点都已匹配，从外部来的点都会在 $j$ 这个中转站被解决的最小代价，$f$ 的转移就是 naive 的背包，$g$ 的转移则考虑新加入一棵子树时，在原子树枚举一些点在新子树内被解决，在新子树枚举一些点在原子树被解决…

注意最后要用 $g$ 来转移 f_

每对点会在其 lca 被枚举到，正确性可以保证，复杂度 $\mathrm O(n^2)$

2022-03-01 摆

由于没什么线代基础所以摆了

考虑这个矩阵 $a$

$$a=\begin{cases}1\ \ {i=j}\\0 \ \ i<j ∧ i|j\\C \ \ otherwise\end{cases}$$

考虑拆成两个矩阵 $b,c$

$$b=\begin{cases}1-C\ \ i=j\\-C\ \ i<j∧i|j\\0\ \ otherwise\end{cases}$$

$$c=C$$

$b$ 就是一个上三角矩阵了

然后：

$$det(a)=det(b+c)=\sum_{p} (-1)^{|p|} \prod(b_{i,p_i}+c_{i,p_i})$$

发现 $\prod(b_{i,p_i}+c_{i,p_i})$ 这个其实拆成每个 $i$ 行选择一个 b\or v 乘在一起，其实可以理解为一些矩阵的行列式，考虑把枚举排列转换为枚举矩阵，然后原式变为：

$$\sum_{A} det(A)$$

$A$ 矩阵的每一行要么是 $b$ 中的一行，要么是 $c$ 中的一行，发现若两行全是 $c$ 的一行，$det(A)=0$ ，于是：

$$Ans=(1-c)^n+\sum_{i=1}^n (1-c)^{n-1} F_{i,i}$$

枚举哪行变成了 $C$ ，则对此行高斯消元后得到的 $F_{i,i}$ 乘上其余就是答案。

考虑如何计算 $F_{i,i}$ ，这里我只会感性理解，大概是算 $F_i$ 一行，利用 $j<i,j|i$ 的 $F_j$ 递推，可得递推式：

$$F_i={-C \over(1-C)} F_j +[C,C,....C]$$

设 $f_i = F_{i,i}$ ，然后 $f_i=\sum_{j\not=i,j|i} {C\over 1-C}f_j+C$

现在我们希望求 $f_i$ 的前缀和 $s_i$ 使用杜教筛构造一个 $g(g_1=1,g_n={C\over{C-1}})$ ，于是：

$$g(1)S(n)=\sum_{i=1}^n (f*g)(i)-\sum_{i=2}^ng(i)S(\lfloor{n\over i}\rfloor)$$

这个 $g$ 构造得很好，于是：

$$S(n)=nC-\sum_{i=2}^ng(i)S(\lfloor{n\over i}\rfloor)$$

后面需要一个整除分块，我们还要快速预处理出一些 $S$

$$f_i=\sum_{j\not=i,j|i} {C\over 1-C}f_j+C$$

观察这个柿子，发现 $f_i$ 只与本质不同质因子出现次数集合有关 ，比方说 $6=2^13^1,9797=97^1101^1$ 他们的 $f$ 值是一样的。

于是我们为每个数字找到一个最小的 $id$ ，这个线性筛时可以递推解决

然后对于更大的 $S$ ，我们使用记忆化搜索递归解决。

2022-03-01 润

打表找规律发现奇怪的结论然后大力 ds

2022-03-03 A

题意容易转换为选出最少的集合使得内部 $gcd = 1$ ，发现答案最多为 $7$ ，枚举一个集合大小 $k$ 考虑容斥，设 $f_i$ 表示选了 $k$ 个元素，其中 $i$ 为所有数字因数的方案数，显然等于 $\binom{cnt}{k}$ 其中 $cnt$ 为 $i$ 的倍数在集合中的数字。

设 $g_i$ 表示 $i$ 为 gcd 方案数，有容斥: $g_i=f_i-\sum_{i|j} g_j$ 。

$cnt,g_i$ 的处理都可以使用 dirclet 后缀和。

2022-03-04 打麻将

对于一个 $len$ ，将所有满足子树直径 $\ge len$ ，而所有儿子的子树直径小于 $len$ 的点丢进队列，显然两两之间不会有祖先关系，每次选出一个最深的点，加入答案，删除这个点的子树，再倍增跳到第一个满足条件的位置加入队列。

这样贪心是显然对的，而删除一个点的子树，维护子树内的直径，可以使用线段树 + O1lca

2022-03-04 线性代数

诈骗题

不要想到什么矩阵的无穷次幂是否收敛

矩阵看做邻接矩阵，无环就行