2017-Sp277-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
出门cjb G1y25，换根dp丢给yzc I2y62，sub上机J1y84，cjb和yzc开到最后一步F，sub说可以ntt，F2y144。之后cjb和yzc做E，sub做D，这个E构造好了偶数和k=1的部分，奇数怎么搞都不对，sub写完D，想了很久发现D fix不了，最后没了。
=== chenjb ===
E太伤了......也没有别的可以做的题....其实是不是应该早点把sub拉回来啊。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：

 * B：

 * C：

 * D：x+y为偶数的黑子显然会不断尝试往白所在对角线上走，在对角线上即为黑胜, 接下来考虑x+y为奇数的黑子。求数组U[i,j]代表白到达(i,j)后选择不断往上走，能够阻挡其的黑子集合，R代表不断向右的对应集合，U'=(U or 在[i,j]能和白碰撞的黑子)，R'同理。计算U,R: 1.U[i,j]=U'[i,j+1]，R[i,j]=R'[i+1,j] 2.若U或R为空，则该点白胜，U和R均变空; 3.若R仅有单个元素k,则U.erase(k),另一方向同理,注意此步同时计算. 证明:若仅存在一个防止单方向冲刺的黑子,则其无法防守另一个方向; 多个防守时不确定棋子; 无法防守某个方向即为白胜.棋子防守即为碰撞,因此从碰撞位置开始计算.

 * E：1的时候是欧拉通路，k为偶数的时候考虑当前点如果手里是个奇数就先不断跟儿子之间走来走去，把到儿子那条边染了，递归儿子，然后回来，注意到奇偶性没变。对于返祖边，直接暴力走来走去，注意奇偶性还是没变。当k为奇数，每一段k-1的构造，奇数段的最后一步返回，并且将这一步再走回去作为下一段的开始。

 * F：考虑hash，观察t在经过i次变换后的hash的式子，发现可以fft得到，预处理即可。

 * G：考虑二分求LIS的过程，建出偏序关系跑topsort

 * H：

 * I：换根dp，子树顺序是谁对别人贡献小谁排前面。

 * J：竖着看，三个全为0或1用1步解决，相同的或者完全相反的可以用2步合并成一个，最后剩下的互相之间能添加的边全部添加，可以发现不超过2e5。

流水账

出门cjb G1y25，换根dp丢给yzc I2y62，sub上机J1y84，cjb和yzc开到最后一步F，sub说可以ntt，F2y144。之后cjb和yzc做E，sub做D，这个E构造好了偶数和k=1的部分，奇数怎么搞都不对，sub写完D，想了很久发现D fix不了，最后没了。

chenjb

E太伤了......也没有别的可以做的题....其实是不是应该早点把sub拉回来啊。

oipotato

subconscious

题解

  • A：
  • B：
  • C：
  • D：x+y为偶数的黑子显然会不断尝试往白所在对角线上走，在对角线上即为黑胜, 接下来考虑x+y为奇数的黑子。求数组U[i,j]代表白到达(i,j)后选择不断往上走，能够阻挡其的黑子集合，R代表不断向右的对应集合，U'=(U or 在[i,j]能和白碰撞的黑子)，R'同理。计算U,R: 1.U[i,j]=U'[i,j+1]，R[i,j]=R'[i+1,j] 2.若U或R为空，则该点白胜，U和R均变空; 3.若R仅有单个元素k,则U.erase(k),另一方向同理,注意此步同时计算. 证明:若仅存在一个防止单方向冲刺的黑子,则其无法防守另一个方向; 多个防守时不确定棋子; 无法防守某个方向即为白胜.棋子防守即为碰撞,因此从碰撞位置开始计算.
  • E：1的时候是欧拉通路，k为偶数的时候考虑当前点如果手里是个奇数就先不断跟儿子之间走来走去，把到儿子那条边染了，递归儿子，然后回来，注意到奇偶性没变。对于返祖边，直接暴力走来走去，注意奇偶性还是没变。当k为奇数，每一段k-1的构造，奇数段的最后一步返回，并且将这一步再走回去作为下一段的开始。
  • F：考虑hash，观察t在经过i次变换后的hash的式子，发现可以fft得到，预处理即可。
  • G：考虑二分求LIS的过程，建出偏序关系跑topsort
  • H：
  • I：换根dp，子树顺序是谁对别人贡献小谁排前面。
  • J：竖着看，三个全为0或1用1步解决，相同的或者完全相反的可以用2步合并成一个，最后剩下的互相之间能添加的边全部添加，可以发现不超过2e5。
附加文件