2020 CCPC 网络赛¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 113/3156 | 7 | 10 | 13 |
A¶
upsolved by 2sozx
题意¶
给定一个开始全白的二维平面，每次操作选择一个矩形将其涂黑，矩形下面紧贴 \(x\) 轴，问每次操作过后黑色区域的周长为多少。操作次数 \(n \le 2 \times 10^5\)
题解¶
由于矩形紧贴 \(x\) 轴，矩形上下两条边边长可以用线段覆盖来维护，现在考虑左右两条边的边长。易知操作是一个区间取 \(\max\) ，每次的和为 \(\sum_{i = 1}^{n - 1}|a_i - a_{i + 1}|\) ,维护区间 \(a_i,a_{i + 1}\) 其中一个是最小值的个数即可，区间 \(\max\) 用吉老师线段树维护即可。
B¶
solved by JJLeo 2sozx
题意¶
可以是 min_25 模板题
题解¶
可以是 min_25 模板题
C¶
solved by 2sozx
题意¶
签到题
题解¶
签到题
D¶
upsolved by
题意¶
题解¶
E¶
solved by 2sozx Bazoka13 JJLeo
题意¶
\(t\) 组询问，每组询问给出 \(n\) 个数，两个人进行游戏，每次每个人可以选择一个数 \(x\) ，若存在 \(x = p \times q\) 且 \(p \not = 1\) 可以将 \(x\) 分成 \(p\) 个 \(q\) ，无法对 \(1\) 进行操作， 问先手赢还是后手赢。\(t \le 10^4, x\le 10^9, n\le 10\)
题解¶
将每个数的质因数个数算出来 \(p^i\) 与 \(p^j\) \(i \not = j\) 且 \(p \not = 2\) 时算两个，之后用 \(Nim\) 游戏的方法算就行。别问为什么
F¶
solved by JJLeo
题意¶
爆搜
题解¶
爆搜
G¶
solved by Bazoka13
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
K¶
solved by 2sozx
题意¶
给定矩阵 \(A,K\)，定义矩阵 \(C\) 为 \(C_{x,y}=\sum_{i=1}^{min(n-x+1,3)}\sum_{j=1}^{min(n-y+1,3)}A_{x+i-1,y+j-1}K_{i,j}\) 定义 \(C^{m}(A,K)=C(C^{m-1}(A,K),K)\) 矩阵 \(K\) 中元素和为 \(1\) 求 \(\lim\limits_{m \to \infty} C\) ，矩阵 \(K\) 为 \(3\times 3\)
题解¶
从 \(C\) 的最后一位开始推很容易得出当且仅当 \(K(1,1) = 1\) 时 \(\lim\limits_{m \to \infty} C\) 非零，否则 \(C = A\)
L¶
upsolved by JJLeo
题意¶
问有多少有序整数组 \((x,y)\) 满足如下性质:
- \(x \in [0,A], y \in [0,B]\)。
- \(|x-y| \le C\)。
- \(x \oplus y \le D\)。
(\(0 \le A,B,C,D \le 10^9\))
题解¶
数位 dp，从高位进行到低位，第一个限制和第三个限制直接按位并记录是否贴上界即可。
第二个限制可以转化为 \(x-y+C \ge 0\) 和 \(y-x+C \ge 0\) 两个条件。不考虑进位退位情况，\(x,y,C\) 二进制每一位按 \(x-y+C\) 加减起来的取值范围是 \([-1,2]\)，可以记录状态进行转移:
- 如果上一位是 \(0\)，这一位是 \(1\) 或 \(2\)，那么下面随便填也可以保证 \(x-y+c \ge 0\)；这一位是 \(0\)，状态不变；这一位是 \(-1\)，则进入下面这个状态。
- 如果上一位是 \(-1\)，如果这一位是 \(-1\) 或 \(0\)，后面怎么填也不能使得 \(x-y+c \ge 0\)，从而不合法；如果这一位是 \(1\)，相当于上一位是 \(0\) 而这一位是 \(-1\)，状态不变；如果这一位是 \(2\)，相当于这一位和上一位都是 \(0\)，进入上面的状态。
- 最终递归边界（到最低位下一位时）为，上述第一个状态或随意填为 \(1\)，第二个状态为 \(0\)。
M¶
upsolved by JJLeo
题意¶
多项式问题，找规律后可以发现式子是形如 \(\prod_{i=1}^n \limits (b_ix+c_i)\) 的分治 NTT。
题解¶
时间复杂度 \(O(n \log ^2 n)\)。
记录¶
before:准备视奸全场结果后排没位置了。书接上文：CSK恰了意面，身体不适
0min:开始分题，ZYF冲1010
2min:ZYF AC，MJX冲1003
14min:MJX AC，CSK冲1007
16min:CSK AC，拿了暂时的 rank1，MJX看1011
41min:MJX PE二发后AC，ZYF冲1002
57min:ZYF AC，ZYF,CSK看1005，MJX看1012，自闭开始
240min:换题讨论，顺了起来，MJX 冲1005，ZYF冲1006
263min:MJX AC
264min:ZYF AC
after end:MJX ban掉ZYF1012正解，CSK ban掉ZYF正解，结论：要换题看