2019 省选泛做

wlzhouzhuan · 2021-01-11 11:03:57 · 个人记录

HNOI2019

Day1T1 鱼

拒绝计算几何，看似 O(n^3) 暴力枚举所有等腰三角形，实际上有论文证明复杂度是 O(n^{2.137}) 的，因此直接碾过去了。

时间复杂度 O(n^{2.137}) ，论文link

Day1T2 JOJO

介绍一种特别优美的做法，先记每一个节点为一个二元组 \mathbb{(a_i,b_i)} 。

根据历史版本关系建出一棵树，考虑 \text{dfs} 的时候动态维护 \text{kmp} ，满足前缀和后缀完全一致。

新加入一个儿子的时候，在树上暴力跳 kmp ，顺便维护新增的贡献即可。

优化也很简单，每次可以直接跳到该串的最小周期位置，若最小周期小于\frac{\text{串长}}{2} ，则直接切换过去，否则暴跳。可以发现每次串长会减少一半。具体实现见代码，真的好优美。

时间复杂度 O(nlogn) 。code

Day2T2 白兔之舞

记 f_{i,y} 表示走了 i 步到第 y 列位置的方案数，有 f_{i,j}=\sum\limits_{k}f_{i-1,k}\times w_{k,j} ，设 A 为 w 的生成矩阵，则有：

A=\begin{bmatrix}w_{0,0}\cdots w_{0,n-1} \\ \cdots \\ w_{n-1,0}\cdots w_{n-1,n-1}\end{bmatrix}

不难发现 F_i=F_{i-1}A=A^i 。

ans_r=\sum\limits_{i=0}^{L}[i\equiv r\pmod k]\binom{L}{i}f_{i,y}

单位根反演，

=\sum\limits_{i=0}^{L}\binom{L}{i}f_{i,y}\frac{1}{k}\sum\limits_{j=0}^{k-1}\omega_k^{(i-r)j}

=\sum\limits_{i=0}^{L}\binom{L}{i}A_{x,y}^i\frac{1}{k}\sum\limits_{j=0}^{k-1}\omega_k^{(i-r)j}

=\frac{1}{k}\sum\limits_{i=0}^{k-1}\omega_k^{-ir}\sum\limits_{j=0}^{L}\binom{L}{j}(A^j)_{x,y}\omega_k^{ij}

=\frac{1}{k}\sum\limits_{i=0}^{k-1}\omega_k^{-ir}(\omega_k^iA+I)_{x,y}^L

=\frac{1}{k}\sum\limits_{i=0}^{k-1}a_i\omega_k^{-ir}

套用 \text{Bluestein's Algorithm (CZT)} 算法的套路：xy=\binom{x+y}{2}-\binom{x}{2}-\binom{y}{2}

=\frac{1}{k}\sum\limits_{i=0}^{k-1}a_i\omega_k^{-\binom{i+r}{2}+\binom{i}{2}+\binom{r}{2}}

=\frac{\omega_k^{\binom{r}{2}}}{k}\sum\limits_{i=0}^{k-1}\omega_k^{\binom{i}{2}}a_i\omega_k^{-\binom{i+r}{2}}

令 f(i)=\omega_k^{\binom{i}{2}}a_i ，g(i)=\omega_k^{-\binom{i}{2}} ，则为 \sum f(i)g(i+r) ，做差卷积即可。

先暴力求原根，计算出 \omega_k^i ，复杂度 O(\sqrt{p}\log p) 。

求 a_i 用矩阵快速幂，复杂度 O(kn^3logL) ；

将 F 和 G 做卷积，用 MTT 处理，复杂度 O(k\log k) 。

总时间复杂度 O(\sqrt{p}\log p+kn^3logL+k\log k) 。

Day2T3 序列

现在还不会实现。。不太会可持久化。。。

先考虑 a 递增的情况，一定有 b_i=a_i ；a 递减的情况，一定有 b_i = \frac{\sum_{j=1}^{n} a_j}{n} 。

不难推广：用单调栈维护，每次加入一个段，则比较栈顶和它的大小关系，如果递减，那么就改成平均值。

带修的话，维护前缀和后缀的单调栈，这部分可用可持久化单调栈，修改的位置可能会将前缀的后面几段和后缀的前面几段合并，二分端点即可。

时间复杂度 O(n\log^2n) 。

GXOI/GZOI 2019

Day2T2 旅行者

随机化直接过，傻逼题。时间复杂度 O(Tmlogn) 。

Day2T3 通信

网络流裸题，用 \text{cdq} 分治优化建边即可。

点数 O(n) ，边数 O(nlogn) ，时间复杂度 O(flow) 。

十二省联考2019

春节十二响

先考虑链的情况：将 1 的两儿子分别维护一个堆，然后大的和大的合并，小的和小的合并。贪心正确性显然。

拓展到树上，则表现为两两依次合并，用 \text{priority\_queue} 维护即可，注意要启发式合并。

时间复杂度 O(nlog^2n) ，注意在 \text{C++} 里面 swap 数据结构是 O(size) 的，在 \text{C++11} 里面是 O(1) 的。

字符串问题

先考虑暴力。

对于支配关系即 A 字符串连向 B 字符串。

若 B 字符串是 A 字符串的前缀，则 B 连向 A ，但注意到这里的边是 O(N_A.N_B) 的，考虑主席树优化建边。

将所有 A 字符串按 sa 排序后，每个 B 显然对应一段区间有连边。可用 SA 跑出 \text{height} 数组，然后 B 连向 A 的条件转化为：

LCP(suf(B),suf(A))\ge SZ(B)
SZ(A)\ge SZ(B)

按照 SZ 从大到小一次处理，即可解决第二个条件。用主席树维护区间信息，然后树形结构连边即可。

不难发现优化后的边数为 O((N_A+N_B)logN) 。

如果出现环，显然答案是 \text{-1} ，否则是一张 DAG ，直接跑拓扑排序即可。

细节较多，常数稍有点大。

时间复杂度 O(Tnlogn) 。

皮配

~~语文理解题~~ 裸的 01 背包题，具体见博客

骗分过样例 (有点烦，先鸽着)

\text{data 1,2,3: 1\_998244353}

求 19^x \%\ mod ，指数对 \varphi(mod) 取模即可，时间复杂度 O(nlogn) 。

\text{data 4: 1?}

用 data4.ans 反向推测出模数是 1145141 即可。

\text{data 5: 1?+}

通过 data5.ans 发现模数肯定很大，可通过 (19^x-a)\equiv (19^y-b) (mod\ p) 解出来。

\text{data 6,7: 1wa\_998244353}

显然是乘法的时候忘开\text{long long}了，找出它的循环节即可。实践发现从 55245 项开始，每 45699 一循环。

JSOI2019

T1 精准预测

应用 2-SAT 思想，将生死关系转化成图：记 (x,t,0/1) 表示 x 这个人在 t 时刻是死/活， a->b 表示一条从 a 到 b 的有向边。

显然有连边 \text{(i,t,0)->(i,t+1,0),(i,t+1,1)->(i,t,1)} 。01 操作是简单的。

发现有很多冗余状态，事实上只需要记录 2(n+m) 个有用状态，其他状态并不需要。具体地，只需要保留 x[i] 的 t[i] 时刻，以及每个 i 的 T+1 时刻状态即可。

可以发现这张图是个 DAG ，从每个 \text{(i,t+1,1)} 出发看能到达多少个 \text{(*,t+1,0)} 状态，用 \text{bitset} 压位即可。注意如果出现 \text{(i,t+1,1)} 和 \text{(i,t+1,0)} 连通，则 i 必死。

本题还卡空间，可每 B 个点一块处理，将空间压下去。实测取 B=15000 较优。

时间复杂度 O(\frac{m^2}{\omega}) ，空间复杂度 O(\frac{mB}{8}) 。

T2 神经网络

由于任意两棵树之间都可以到达，那可以将每棵树拆分成若干不相交的链，将这些链按一定顺序拼接起来，即为哈密顿回路。

对于该哈密顿回路，有以下两个限制：

相邻的链不能属于同一棵树
第一条链是第一棵树 1 号节点所在的链，最后一条链不是第一棵树的链

首先，对于每棵树，用树形 dp 求解拆分成 j 个链的方案数。用 dp[u][i][0/1/2] 表示以 u 为根的子树，当前拆成 i 条链，且点 u 所在链的状态是已拼成链/新的链(单点)/长度>1且还可继续向上拼接的链的拆分方案数。转移细节极多（有 13 条转移式）。

定义 f[i] 表示拆分成 i 个链的方案数，则有 f[i] = dp[root][i][0]+dp[root][i-1][1]+2\times dp[root][i-1][2] 。

定义一个链的颜色表示它所在的树下标。如果仅仅是链排列，那么直接将 m 棵树的以链数为下标的 EGF 卷起来就是答案的 EGF ，但这题相邻的颜色不能一样，考虑容斥：钦定有 j 个相邻的位置颜色一样。则不难得到一棵树的 EGF:

F(x)=\sum\limits_{i=1}^{k}f[i]* i!*\sum\limits_{j=0}^{i-1}(-1)^j\binom{i-1}{j}\frac{x^{i-j}}{(i-j)!}

解释：有 f[i] 种拆分方式，这些链排列有 i! 种，容斥系数为 (-1)^j ，有 i-1 个相邻位置挑 j 个，得到 i-j 条极长链（极长链是指同色链的极长连通块）。

注意第一棵树比较特殊，它需要满足：

第一个点所在的链处于首

此时钦定这条链为首即可，它不参与内部链排列，也不参与外部的 EGF 卷积：

\sum\limits_{i=1}^{k}f[i]*(i-1)!*\sum\limits_{j=0}^{i-1}(-1)^j\binom{i-1}{j}\frac{x^{i-j-1}}{(i-j-1)!}

最后一条链颜色不能是 1

这是上面的式子多算的部分，考虑将其剔除：

\sum\limits_{i=1}^{k}f[i]*(i-1)!*\sum\limits_{j=0}^{i-2}(-1)^j\binom{i-1}{j}\frac{x^{i-j-2}}{(i-j-2)!}

注意这里 j 的上界是 i-2 ，因为 x^{-1} 无意义。

做有标号背包卷积即可，时间复杂度 O(k^2) 。

T3 节日庆典

详见 cz_xuyixuan 的博客，可证明有效的后缀个数是 O(logn) 量级的，故暴力维护即可，比较后缀大小关系可用 \text{exkmp} 实现预处理 O(n) 查询 O(1) 。

时间复杂度 O(nlogn) 。

BJOI2019

Day1T1 奥术神杖

二分答案，转化为判定问题。设二分值为 mid ，则 W'=lnW-mid ，将所有串丢进 AC 自动机内，用 dp[i][j] 表示字符串前 i 个字符当前在自动机的 j 号节点能得到的最大值。

时间复杂度 O(26nmslog\text{值域}) ，跑不满。

Day1T2 勘破神机

发现 $\sqrt{5},\sqrt{3}$ 在模 $998244353$ 意义下无二次剩余，因此需扩域至 $x+y\sqrt{5}$ 形式来处理。时间复杂度 $O(Tk^2logk)$ 。 ## Day1T3 送别用平衡树维护每个墙，例如横向的墙拆分为下面左右两端点，上面左右两端点，然后查询两点之间的 $dist$ 即为 $rank$ 之差。处理起来细节极多，且实现难度极大。。。目前不打算去实现，时间复杂度 $O(nlogn)$ 。 ## Day2T1 排兵布阵定义 $dp[i][j]$ 表示前 $i$ 个城堡用了 $j$ 个士兵的最大总分，做 $01$ 背包即可。时间复杂度 $O(nms)$ ，跑不满。 ## Day2T2 光线考虑求上下两玻璃的等效透光率和反射率，记为 $p_i,q_i,p_j,q_j$ ，易得 $p=p_ip_j\frac{1}{1-q_iq_j},q=q_1+\frac{p_1^2q_2}{1-q_1q_2}$ 。注意要从下往上递推，不然上下光线量不同会导致玻璃上下面的透光率和反射率是不同的。时间复杂度 $O(n)$ 。 ## Day2T3 删数对于一个长度为 $n$ 的序列，删的顺序是：$k1$ 个 $n$ ，$k2$ 个 $n-k1$ ，$k3$ 个 $n-k1-k2$ ... 结论就是：用桶记录 $cnt[i]$ 表示 $i$ 的个数，放数轴向左翻倒，即覆盖 $[i-cnt[i]+1,i]$ ，$1$~$n$ 中未被覆盖的点数即为答案。对于整体加一/减一，可以只挪动查询区间，即求 $[p_0,p_0+n-1]

中未被覆盖的点，每次使 p_0 加减一。

时间复杂度 O(nlogn) 。

HAOI2018

Da2T2 染色

记 lim=\min\{m,\frac nS\} 表示满足条件的颜色数上限。

用 g[i] 表示钦定 i 种颜色出现了 S 次的方案数，不难得出 g[i]=\binom{m}{i}\frac{n!}{(S!)^i(n-iS)!}(m-i)^{n-iS} 。

用 f[i] 表示恰好 i 种颜色出现了 S 次的方案数，由二项式反演得 f[i]=\sum\limits_{j=i}^{lim}(-1)^{j-i}\binom{j}{i}g[j] 。

f[i]=\frac{1}{i!}\sum_{j=i}^{lim}\frac{(-1)^{j-i}}{(j-i)!}g[j]j!

卷积一下，答案即为 \sum\limits_{i=0}^{lim}f[i]w[i] 。

时间复杂度 O(n+mlogm) 。