======2016 CCPC 合肥站====== [[https://vjudge.net/contest/399651|比赛链接]] =====A.===== **solved by 2sozx** ====题意==== 给定一个竞赛图，将其拆成两个子图 $P,Q$。 定义一个图有传递性为 $a\to b,b\to c$ 有 $a\to c$，问 $P,Q$ 是否具有传递性。$n\le 2016$ ====题解==== $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** ====题意==== ====题解==== =====J.===== **solved by 2sozx Bazoka13 JJLeo** ====题意==== [[http://acm.hdu.edu.cn/showproblem.php?pid=5970|中文题意]] ====题解==== 先看数据范围，$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。