WC 历年真题分析

cyh_toby · 2022-01-19 18:05:10 · 个人记录

2021

括号路径

由于题目保证斜对称性，所以如果 x 可以走到 y，那么 y 一定可以走到 x。于是构成一种强联通性。

考虑长度为 2 的合法路径 x\rightarrow y，必然是有 (z,x,w),(z,y,w)。把这样的 (x,y) 缩成一个点，显然不会破坏其他合法解。所以不停地缩点即可，可以对边启发式合并。

表达式求值

数组每一位互不相干，所以考虑拆成 n 个单个的数来做。

首先建出表达式树。最直接的 DP 是设 f(x,i) 表示 x 节点的子树，得到结果为 i 的方案数。转移可以前缀和优化。注意到第二维离散化之后其实是 O(m) 的，因此总复杂度是 O(nm|S|)。

证明：

2. 虽然 f_{n-1},f_n 在模意义下不一定互质，但由于非模意义下 \gcd(f_{n-1}, f_n)=1，可以反证出对于模意义下的 f_{n-1},f_n，有 \gcd(f_{n-1},f_n,m')=1，所以 \forall d|f_{n-1},d|m',d>1，d\not|f_n，故 f|b'。

因此同时除以 \gcd(f_{n-1},m')=\gcd(b',m')，问题变成：

现在就存在逆元了，可以除过去了。

所以我们的预处理是：对于 m 的所有约数 m '，在模 m' 意义下遍历一个循环节内的斐波那契数。对于相邻两项 f_{n-1},f_n，令 d=\gcd(f_{n-1},m')，把 n 用于更新 (m',d,\frac{f_n}{\frac{f_{n-1}}{d}}\bmod {\frac{m'}{d}}) 这个状态的答案。这一部分复杂度是 O(\sum_{d|m})\approx O(m\log\log m)（m=10^5 时大约为 4\times10^5）。

查询的时候首先同时除以 \gcd(a,b,m)，得到 a',b',m'，记 d=\gcd(b',m')，那么查询状态 (m',d,-\frac{a'}{\frac{b'}{d}}\bmod \frac{m'}{d})。

用 map 实现的话常数有点大，我不开 O2 会被卡。（当然在 LOJ 的话不开 O2 也是稳过的。）

2020

有根树

参考 cmd 题解：https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p6729-wc2020-you-gen-shu

注意到一个性质，就是 w 随深度递减而递增。最低的部分分一看就是每次二分答案然后在树上贪心，即把 w_i \le mid 的 i （且不是根）全部排出在外，剩下的点就是一个包含根的连通块，检查一下点数是否 \le lim 即可。

然后我们发现这样找到的最优解一定可以满足 \min_{i\in C}\{w_i\}\ge |C|\ge \max_{i\not\in C}\{w_i\}，并且此时 ans=|C|。

考虑不满足的时候如何调整。

1. 若 \min_{i\in C}\{w_i\}<\max_{i\not\in C}\{w_i\}，把 C 中最小的和不在 C 中最大的交换，|C| 不变，而 \max 不变大，不会变劣。

2. 若 \min_{i\in C}\{w_i\}<|C|，由上一条可知当前答案瓶颈在于 |C|，于是把 C 中最小的踢出去，答案不会变劣。

3. 若 \max_{i\not\in C}\{w_i\}>|C|，则答案瓶颈在于 \max，那么把不在 C 中的最大的加入 C 中，答案不会变劣。

所以思路就是，不断调整使得满足上式，并且让 ans=|C| 尽量小。

• 加入操作。

  会把到根的一条链上全部点的 w+1，由于从下至上 w 递增，所以至多有一个位置 +1 后会导致 \max_{i\not\in C}\{w_i\}>\min_{i\in C}\{w_i\}，那么只需要进行一次调整 1 和调整 3。

• 删除操作。

  会把到根的一条链上全部点的 w-1。

  • 在 C 内。这时 C 要 -1，可能需要调用调整 3。但 \min_{i\in C}\{w_i\} 显然是不会减小的，因此不需要调整 1,2。

  • 在 C 外，那么需要调整 1,3，不需要调整 2。

综上，每次只需要 O(1) 次调整。

实现方面，用树剖 + 线段树，线段树每个节点维护两个值 mn,mx，分别表示 \min_{i\in C}\{w_i\} 和 \max_{i\not\in C}\{w_i\}，特殊地，当不存在时分别 +\inf,-\inf。加入一个点的时候先默认不在 C 中（为了 ans=|C| 尽量小），之后调整。并且调整 1 其实可以由调整 2,3 得到，因为 2,3 调整完后有 mn\ge |C|\ge mx。

时间复杂度 O(m\log^2n)，看得出出题人专门卡这个复杂度，但其实可以通过。

2019

远古计算机

提交答案题

Sub1

node 1
read 0 a
write a 0

Sub2

预处理出前 \log 左右项斐波那契数，然后把 jmp val 当作 switch 用。

Sub3

显然存在最优方案是单线路传输。

所以找到最短路即可。

Sub4

乱搞点。

第一感觉是搞出最短路图，然后沿着最短路图运输，先到的先转运。可能 random_shuffle 一下。

实际上只有不打乱并且前向星存图，才能恰好找到最优解。（偷懒用 vector 存图就吃大亏了）。

Sub5

不能乱搞了。

首先枚举 1-10 出发顺序的排列。

然后设 book(x,i) 表示 x 点在 i 时刻是否已占用。最短路转移时只能转移到 book(x,i),book(x,i+1) 都为 0 的时刻。

会发现最优解轮数是 21。

所以只要当前排列的结果是 21 了，就输出方案并结束。

提交答案题求最优解，往往会用到多次枚举或者随机化。

2018

通道

求点对使得在三棵树上的路径长度和最大的这个最大值。

对第一课树边分治（顺便一提，边分治重构后的树点数为 4n）。当前分治子问题中的点被分为两部分 L,R。在第二棵树上对当前子问题涉及到的点建虚树，然后从根 dfs，假设当前在 p，我们考虑计算虚树上以 p 为 LCA 的点对的贡献。假设他们是 x,y，并且 x,y 分别属于 L,R，那么贡献即为

其中 d_1 表示在第一棵树上到当前分治中心的距离，d_2 表示在第二棵树上的深度，dist_3 表示在第三棵树上的距离。