2020 CCPC 长春站¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 17/? | 6 | 8/9 | 12 |
A¶
solved by 2sozx
题意¶
签到
题解¶
签到
B¶
upsolved by
题意¶
题解¶
C¶
upsolved by
题意¶
题解¶
D¶
solved by JJLeo
题意¶
签到
题解¶
签到
E¶
upsolved by
题意¶
题解¶
F¶
solved by JJLeo
题意¶
给一颗 \(n\) 个节点的树，求
(\(2 \leq n \leq 10^5\)，\(1 \leq a_i \leq 10^6\))
题解¶
\(a_i \oplus a_j = a_{\operatorname{lca}(i, j)}\) 的限制使用启发式合并来完成：先统计轻儿子内部答案（清空），再统计重儿子内部答案（不清空），再依次遍历轻儿子统计两两子树间的贡献。
\(i \oplus j\) 直接统计的话不好计算，可以发现每一位是独立的，因此将每一位拿出来单独计算。总时间复杂度 \(O(n \log^2 n)\)。
G¶
upsolved by
题意¶
题解¶
H¶
solved by Bazoka13 JJLeo
题意¶
给定一个 \(m\) 位锁和一个初始十进制数字 \(n\)，两人轮流改动一个数字，不能改到和之前相同的数字，问先手是否必胜。(\(1 \leq m \leq 5\)，\(0 \leq n < 10^m\))
题解¶
根据每位之和的奇偶可以构成一张二分图，该题即为二分图博弈：从二分图的一个起点开始，两人轮流交替到一个相邻的之前双方都未经过的点，无法行动的人输。
先手必胜的条件是起点在所有的最大匹配中都被选中了，即删掉起点最大匹配会减少 1，可以通过先删掉起点的流量跑一次 dinic，再添加起点流量看第二次 dinic 有没有增广出新的流量。
证明如下：考虑先手必败的情况，如果存在一个最大匹配使得起点是未匹配点，那么先手第一步必然走到一个匹配点，否则这两个点就可以匹配，与最大匹配矛盾。那么后手只需走到该点对应的匹配点，而先手只能继续走到一个匹配点，否则会形成一条增广路，与最大匹配矛盾。后手只需重复上述过程即可，最终先手必然会回到最初的那一侧并无点可走。
I¶
upsolved by
题意¶
题解¶
J¶
solved by 2sozx JJLeo
题意¶
给定 \(k\) 个圆，问有多少种方案可以在此基础上添加圆使其满足下列条件：（最初的圆满足）
- 所有圆心都在 \(x\) 轴上。
- 所有圆的横坐标都在 \([0,n]\) 的范围。
- 所有圆的半径不超过 \(5\)。
- 任何两个圆至多有 \(1\) 个交点。
最终答案对 \(10^9+7\) 取模。(\(2 \leq n \leq 10^3\)，\(0 \leq k \leq 5n\))
题解¶
因为圆半径很小，可以设 \(f_i\) 为新添加的圆的半径的最大值为 \(i\) 时的方案数，枚举新添加的圆的半径，这个圆内部放置的方案数使用 dfs 爆搜即可。前缀和优化进行转移即可。
K¶
upsolved by JJLeo
题意¶
初始有 \(n\) 个可重集，每个集合内只有 \(a_i\) 一个元素，有 \(m\) 个如下操作：
- 新增一个可重集，里面只有一个元素。
- 将一个元素的值改变。
- 合并两个可重集。
每次操作后问有多少个点对满足它们在同一个可重集且 \(\operatorname{gcd}(a_i,a_j)=a_i\oplus a_j\)。(\(1 \leq n \leq 10^5\)，\(1 \leq m \leq 2 \times 10^5\)，\(1 \leq a_i \leq 2 \times 10^5\))
题解¶
枚举 \(a_i\oplus a_j\)，统计有多少个 \(a_i\) 和 \(a_j\) 满足 \(\operatorname{gcd}(a_i,a_j)=a_i\oplus a_j\)，这部分的复杂度为 \(O(n \log ^2 n)\)。
可以发现满足这个条件的数对并不是很多，可以处理出每个数和哪些数是成对的，然后再使用 unordered_map 存取数字，使用启发式合并，每次修改暴力增加或减少满足条件的点对数目，时间复杂度约为 \(O(n \log ^2 n)\)。
L¶
upsolved by 2sozx
题意¶
寻找长度为 \(n\) 的序列 \(a\) 使得：
- \(a_i > 0\)
- \(\sum_{i=1}^n a_i = s\)
- \(a_i - a_{i+1} = k\) 或 \(a_{i+1} - a_i = 1\)
\(n,k \le 10^5, s \le 10 ^ {18}\)
题解¶
在 \(mod(k + 1)\) 意义下即为每次增加1的序列，首先枚举 \(a_1\) 看是否存在 \(a_1\) 使得 \(\sum_{i=1}^n a_i = s (mod (k + 1))\) ，如果不存在输出 \(-1\) 否则一定存在。
因此我们考虑从 \(mod\) 意义下的序列 \(a\) 在不同位置加 \(k + 1\)，显然需要从原 \(a_i\) 小的加，否则会出现问题。