2017-Sp122-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
感觉十分垃圾，构造题C不会做，三人被打翻在地。
== 总结 ==
=== chenjb ===
不懂为什么D这个网络流能过。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：farmland原题，由于坐标系比较小，直接延长到1e5以外即可。更具体做法参见shi哥代码

 * B：按男生的w值从大到小排序后跑二分图匹配，匈牙利算法保证了最优性。

 * C：Watashi nb。维护[2 11...1 0 0101...01]的多个块相连接的形态，每次取第一个严格在pos之后的2的位置t，再取t之前第一个0的位置r;if(pos>=r)++c[pos],c[t]=0,++c[t+1];else if(c[pos]>0)--c[pos],++c[pos+1];else ++c[pos];

 * D：相当于dinic跑一次阻塞流，跑之前助推一次就能过了....把S的in置为inf，按id推一遍，然后把T的in置为inf，倒着求出每条边推了的流量。

 * E：可以证明答案就是最短路径长度，然后根据最短路径长度k染色即可，距离<=k的根据距离染成i，>k的染成k即可。

 * F：f[i][j]直接dp即可，注意记录方案。

 * G：用map维护并查集来维护define信息，用堆栈进行表达式求值。

 * H：bzoj王室联邦原题

 * I：随便找个轴展开，大力simpson即可。

 * [http://blog.watashi.ws/970/andrew-stankevich-3-solution/ Watashi]

流水账

感觉十分垃圾，构造题C不会做，三人被打翻在地。

总结

chenjb

不懂为什么D这个网络流能过。

oipotato

subconscious

题解

• A：farmland原题，由于坐标系比较小，直接延长到1e5以外即可。更具体做法参见shi哥代码
• B：按男生的w值从大到小排序后跑二分图匹配，匈牙利算法保证了最优性。
• C：Watashi nb。维护[2 11...1 0 0101...01]的多个块相连接的形态，每次取第一个严格在pos之后的2的位置t，再取t之前第一个0的位置r;if(pos>=r)++c[pos],c[t]=0,++c[t+1];else if(c[pos]>0)--c[pos],++c[pos+1];else ++c[pos];
• D：相当于dinic跑一次阻塞流，跑之前助推一次就能过了....把S的in置为inf，按id推一遍，然后把T的in置为inf，倒着求出每条边推了的流量。
• E：可以证明答案就是最短路径长度，然后根据最短路径长度k染色即可，距离<=k的根据距离染成i，>k的染成k即可。
• F：f[i][j]直接dp即可，注意记录方案。
• G：用map维护并查集来维护define信息，用堆栈进行表达式求值。
• H：bzoj王室联邦原题
• I：随便找个轴展开，大力simpson即可。
• Watashi