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$ 个节点的树，求

$$\sum _{i=1}^n\sum _{j=i+1}^n[a_i\oplus a_j=a_{\mathrm{lca}(i,j)}](i\oplus j)$$

($2\le n\le {10}^5$，$1\le a_i\le {10}^6$)

题解

$a_i\oplus a_j=a_{\mathrm{lca}(i,j)}$ 的限制使用启发式合并来完成：先统计轻儿子内部答案（清空），再统计重儿子内部答案（不清空），再依次遍历轻儿子统计两两子树间的贡献。

$i\oplus j$ 直接统计的话不好计算，可以发现每一位是独立的，因此将每一位拿出来单独计算。总时间复杂度 $O(n{\log }^{2}n)$。

G

upsolved by

题意

题解

H

solved by Bazoka13 JJLeo

题意

给定一个 $m$ 位锁和一个初始十进制数字 $n$，两人轮流改动一个数字，不能改到和之前相同的数字，问先手是否必胜。($1\le m\le 5$，$0\le n<{10}^m$)

题解

根据每位之和的奇偶可以构成一张二分图，该题即为二分图博弈：从二分图的一个起点开始，两人轮流交替到一个相邻的之前双方都未经过的点，无法行动的人输。

先手必胜的条件是起点在所有的最大匹配中都被选中了，即删掉起点最大匹配会减少 1，可以通过先删掉起点的流量跑一次 dinic，再添加起点流量看第二次 dinic 有没有增广出新的流量。

证明如下：考虑先手必败的情况，如果存在一个最大匹配使得起点是未匹配点，那么先手第一步必然走到一个匹配点，否则这两个点就可以匹配，与最大匹配矛盾。那么后手只需走到该点对应的匹配点，而先手只能继续走到一个匹配点，否则会形成一条增广路，与最大匹配矛盾。后手只需重复上述过程即可，最终先手必然会回到最初的那一侧并无点可走。

I

upsolved by

题意

题解

J

solved by 2sozx JJLeo

题意

给定 $k$ 个圆，问有多少种方案可以在此基础上添加圆使其满足下列条件：（最初的圆满足）

• 所有圆心都在 $x$ 轴上。
• 所有圆的横坐标都在 $[0,n]$ 的范围。
• 所有圆的半径不超过 $5$。
• 任何两个圆至多有 $1$ 个交点。

最终答案对 ${10}^9+7$ 取模。($2\le n\le {10}^3$，$0\le k\le 5n$)

题解

因为圆半径很小，可以设 $f_i$ 为新添加的圆的半径的最大值为 $i$ 时的方案数，枚举新添加的圆的半径，这个圆内部放置的方案数使用 dfs 爆搜即可。前缀和优化进行转移即可。

K

upsolved by JJLeo

题意

初始有 $n$ 个可重集，每个集合内只有 $a_i$ 一个元素，有 $m$ 个如下操作：

• 新增一个可重集，里面只有一个元素。
• 将一个元素的值改变。
• 合并两个可重集。

每次操作后问有多少个点对满足它们在同一个可重集且 $\gcd (a_i,a_j)=a_i\oplus a_j$。($1\le n\le {10}^5$，$1\le m\le 2\times {10}^5$，$1\le a_i\le 2\times {10}^5$)

题解

枚举 $a_i\oplus a_j$，统计有多少个 $a_i$ 和 $a_j$ 满足 $\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$ 小的加，否则会出现问题。

记录

总结