2016 CCPC 合肥站¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 1/153 | 8 | 8 | 10 |
A¶
solved by 2sozx
题意¶
给定一个竞赛图，将其拆成两个子图 \(P,Q\)。 定义一个图有传递性为 \(a\to b,b\to c\) 有 \(a\to c\)，问 \(P,Q\) 是否具有传递性。
题解¶
\(bitset\) 直接搞，\(O(\frac{n^3}{w})\)。
写题解时突然发现这不是必然 \(Tle\) 了么，比赛时候复杂度算错了，少算个 \(n\) 。我是真敢写
B¶
upsolved by
题意¶
题解¶
C¶
solved by 2sozx
题意¶
给定一颗树，节点数为 \(n,n\le 40000\) ，边权为 \(0, 1\) ，两个人玩游戏，若一个点与父亲节点的边权为 \(1\) 则这个节点可以被选择。每个人选择一个点，之后将这个点与根节点路径上的边权翻转，不能翻转则失败。\(q\) 次操作，每次可以修改一条边边权或者询问以 \(x\) 为根节点谁会赢。
题解¶
考虑与根节点相链接的点边权，显然游戏结束必要变为 \(0\) ，分情况讨论。若开始为 \(1\) ，操作完这个点的子树之后变为 \(0\) 则显然进行了奇数次操作；若不变，显然子树进行了偶数次操作，再将这个 \(1\) 变成 \(0\) 则会进行奇数次操作。因此若边为 \(1\) 则一定会进行奇数次操作，否则进行偶数次操作，因此将与根节点连接的边的边权异或起来，若为 \(1\) 则先手胜，否则后手胜。边权修改用 \(map\) 存一下即可。
D¶
upsolved by
题意¶
题解¶
E¶
upsolved by
题意¶
题解¶
F¶
upsolved by
题意¶
题解¶
G¶
solved by JJLeo
题意¶
题解¶
H¶
solved by JJLeo
题意¶
签到题。
题解¶
暴力即可。
I¶
solved by 2sozx JJLeo
题意¶
给定 \(l, r\) 找到一个最大的值 \(ans\) 使得存在 \(l \le x \le y \le r\) 并且 \(ans = x | y\)
题解¶
- 对于 \(l, r\) 从高位开始相同的位置显然 \(x, y\) 一定是这个，即 \(ans\) 的这几位与 \(l, r\) 相同。
- 对于第一位 \(l, r\) 不同显然一个是 \(1\), 另一个是 \(0\)，因此我们很容易得到之后位的 \(x = \cdots 011111\cdots 1, y = \cdots 100000\cdots0\) 一定能取到，即 \(ans\) 后几位均可以取到1
J¶
solved by 2sozx Bazoka13 JJLeo
题意¶
题解¶
先看数据范围，\(m\) 很小，而且有 \(f(i + j, j) = f(i, j)\) ，由于 \(c\) 很小并且显然 \(\frac{ij + kj^2}{f(i,j)}\) 的余数或者下取整的差分有以长度为 \(c\) 的循环节，因此可以 \(O(m^2c)\) 预处理。询问可以 \(O(m^2)\) 得到。
记录¶
前情提要：cf炸了一天，到写记录的时候还没好
0min：分题,ZYF冲H
6min：ZYF AC,MJX 冲A
12min：MJX AC,CSK 冲E
19min：CSK WA,ZYF 冲I
22min：ZYF AC,CSK继续冲E
23min：CSK WA,看后发现出题人毒瘤，模数是 \(10^8 + 7\)
26min：CSK AC,冲D
42min：CSK AC D,ZYF 冲G
70min：ZYF MLE,MJX 冲C
76min：MJX AC,ZYF 冲G
83min：ZYF MLE * 2,MJX 冲J
153min：MJX WA,把int 全改 long long 后tle
165min：MJX AC, ZYF 分块冲G 卡过
till end：剩下两小时看了会牛客比赛，然后直接开溜
总结¶
- MJX：记得减法一定要取模，多组数据一定要清零。
- ZYF：要复习一手终于遇到的LCT。