2017-Sp125-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场发现A是多项式求逆，就让sub推式子，cjb敲了fft，之后sub上机'''A1y45'''。cjb和yzc开了C，yzc上机写C，中间cjb上机打了个E的表，之后'''C1y74'''，sub找好规律，'''E1y88'''。sub上机写J，cjb开F，让yzc敲了费用流，之后wa 2，yzc找到了错误，'''F2y151'''。sub上机写B，'''B1y164'''。之后三人吃饭，yzc试图开I，最后三人讨论之后sub上机写J，'''J2y269'''。
== 总结 ==
=== chenjb ===

=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：FFT多项式求逆。

 * B：做出顶面上凸壳和底面下凸壳，扫一遍即可。

 * C：S向Gops点连边，Girls向T连边，若a是b的子集，则a向b连inf边，根据边的流向和依赖关系，这样符合了题目要求逻辑条件，跑最大流即可。

 * D：扫描线得到圆圆之间的树形关系。随后扫一遍树，计算每个圆的贡献去掉最大的K个即可。

 * E：暴力打表找规律即可。

 * F：对棋盘进行黑白染色，然后S向黑点连下限为1，上限为inf，费用为0的边，白点向T连下限为1，上限为inf的边，每个黑点向相邻的白点连流量为1，费用为0/1(看原先是否存在)，注意边界的情况要特殊处理，让黑点直接向T连边，S向边界的S连边，然后跑'''已有边数'''次费用流增广。下界限制可以用费用为-inf的边来限制，同时也能起到判断是否合法的效果。

 * G：

 * H：cjb

 * I：yzc

 * J：每个起点大力dp跑出所有三进制操作序列对应得胜者，在此之上博弈dp即可。

 * [https://wiki.icpc.camp/wood-cube/Petrozavodsk%20Winter-2014%20Ukrainian Wood Cube]

 * [https://wiki.icpc.camp/new-meta/2017/04/24%20Petrozavodsk%20Winter-2014.%20Ukrainian%20Contest New Meta]

 * [https://wiki.icpc.camp/deep-dark-fantasy/20170328 Deep Dark Fantasy]

 * [wiki:2016-C25-team1 Siunaus]

流水账

开场发现A是多项式求逆，就让sub推式子，cjb敲了fft，之后sub上机A1y45。cjb和yzc开了C，yzc上机写C，中间cjb上机打了个E的表，之后C1y74，sub找好规律，E1y88。sub上机写J，cjb开F，让yzc敲了费用流，之后wa 2，yzc找到了错误，F2y151。sub上机写B，B1y164。之后三人吃饭，yzc试图开I，最后三人讨论之后sub上机写J，J2y269。

总结

chenjb

oipotato

subconscious

题解

  • A：FFT多项式求逆。
  • B：做出顶面上凸壳和底面下凸壳，扫一遍即可。
  • C：S向Gops点连边，Girls向T连边，若a是b的子集，则a向b连inf边，根据边的流向和依赖关系，这样符合了题目要求逻辑条件，跑最大流即可。
  • D：扫描线得到圆圆之间的树形关系。随后扫一遍树，计算每个圆的贡献去掉最大的K个即可。
  • E：暴力打表找规律即可。
  • F：对棋盘进行黑白染色，然后S向黑点连下限为1，上限为inf，费用为0的边，白点向T连下限为1，上限为inf的边，每个黑点向相邻的白点连流量为1，费用为0/1(看原先是否存在)，注意边界的情况要特殊处理，让黑点直接向T连边，S向边界的S连边，然后跑已有边数次费用流增广。下界限制可以用费用为-inf的边来限制，同时也能起到判断是否合法的效果。
  • G：
  • H：cjb
  • I：yzc
  • J：每个起点大力dp跑出所有三进制操作序列对应得胜者，在此之上博弈dp即可。
  • Wood Cube
  • New Meta
  • Deep Dark Fantasy
  • Siunaus
附加文件