用户工具

站点工具


2020-2021:teams:farmer_john:2016_ccpc_合肥站

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:farmer_john:2016_ccpc_合肥站 [2020/10/07 22:38]
2sozx [A.]
2020-2021:teams:farmer_john:2016_ccpc_合肥站 [2020/10/13 22:34] (当前版本)
jjleo [总结]
行 4: 行 4:
 **solved by 2sozx** ​ **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$ 。<​del>​我是真敢写</​del>​
 =====B.===== =====B.=====
 **upsolved by** **upsolved by**
行 15: 行 16:
  
 =====C.===== =====C.=====
-**upsolved ​by **+**solved ​by 2sozx**
 ====题意==== ====题意====
 +给定一颗树,节点数为 $n,n\le 40000$ ,边权为 $0, 1$ ,两个人玩游戏,若一个点与父亲节点的边权为 $1$ 则这个节点可以被选择。每个人选择一个点,之后将这个点与根节点路径上的边权翻转,不能翻转则失败。$q$ 次操作,每次可以修改一条边边权或者询问以 $x$ 为根节点谁会赢。
 +
 +
 ====题解==== ====题解====
 +考虑与根节点相链接的点边权,显然游戏结束必要变为 $0$ ,分情况讨论。若开始为 $1$ ,操作完这个点的子树之后变为 $0$ 则显然进行了奇数次操作;若不变,显然子树进行了偶数次操作,再将这个 $1$ 变成 $0$ 则会进行奇数次操作。因此若边为 $1$ 则一定会进行奇数次操作,否则进行偶数次操作,因此将与根节点连接的边的边权异或起来,若为 $1$ 则先手胜,否则后手胜。边权修改用 $map$ 存一下即可。
 =====D.===== =====D.=====
 **upsolved by ** **upsolved by **
行 33: 行 38:
 ====题解==== ====题解====
 =====G.===== =====G.=====
-**upsolved ​by**+**solved ​by JJLeo**
 ====题意==== ====题意====
  
行 39: 行 44:
  
 =====H.===== =====H.=====
-**upsolved ​by **+**solved ​by JJLeo** 
 ====题意==== ====题意====
 +签到题。
 ====题解==== ====题解====
 +暴力即可。
 =====I.===== =====I.=====
-**upsolved ​by **+**solved ​by 2sozx JJLeo**
 ====题意==== ====题意====
  
行 51: 行 57:
  
 =====J.===== =====J.=====
-**upsolved ​by **+**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炸了一天,到写记录的时候还没好\\ 前情提要:cf炸了一天,到写记录的时候还没好\\
行 72: 行 79:
 till end:剩下两小时看了会牛客比赛,然后直接开溜\\ till end:剩下两小时看了会牛客比赛,然后直接开溜\\
 =====总结===== ​ =====总结===== ​
-MJX:记得减法一定要取模,多组数据一定要清零。+  * MJX:记得减法一定要取模,多组数据一定要清零。 
 +  * ZYF:要复习一手终于遇到的LCT
2020-2021/teams/farmer_john/2016_ccpc_合肥站.1602081482.txt.gz · 最后更改: 2020/10/07 22:38 由 2sozx