2017-Sp164-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，三个人很快开出了E和G，'''G2y31'''，'''E2y44'''，之后cjb大力猜了B的结论，'''B1y77'''，sub上机写J，'''J1y87'''，之后三人开F和I，sub上机写F，cjb上机写树hash之后yzc上机写I，wa了之后和cjb一起查错，最后发现hash要long long，'''I3y262'''，sub  '''F3y269'''，6题罚时893。
== 总结 ==
=== chenjb ===
zimpha太牛逼了.jpg，树hash要注意值域范围，感觉第7个题还至少需要多给一个小时，估计是H题。前面表现还行，不过看起来就是牌7铁6的感觉，居然踩了Red Queen，罚时好就是了不起啊....
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：

 * B：是二分图则答案为1，否则为0。

 * C：

 * D：

 * E：平面图网络流，转成对偶图后跑最短路。

 * F：n^2^ f[i][j]代表目前左边的矩形到第i个，左边到第j个，利用前缀最大值优化到O(1)转移即可。

 * G：a[i],b[i]交替放，相邻一个数至少取一个，直接dp。

 * H：

 * I：把根节点儿子都拿出来，然后枚举B树size，则子树大小大于size的都必须在A树里，树HASH判断。

 * J：先构造曼哈顿环，然后每一次将i和i+p连边，可以使得每个点的度数加2，如果k%2==1，每个点再与它对面点连边，注意n是奇数时会多连一条。

流水账

出门各自看题，三个人很快开出了E和G，G2y31，E2y44，之后cjb大力猜了B的结论，B1y77，sub上机写J，J1y87，之后三人开F和I，sub上机写F，cjb上机写树hash之后yzc上机写I，wa了之后和cjb一起查错，最后发现hash要long long，I3y262，sub F3y269，6题罚时893。

总结

chenjb

zimpha太牛逼了.jpg，树hash要注意值域范围，感觉第7个题还至少需要多给一个小时，估计是H题。前面表现还行，不过看起来就是牌7铁6的感觉，居然踩了Red Queen，罚时好就是了不起啊....

oipotato

subconscious

题解

• A：
• B：是二分图则答案为1，否则为0。
• C：
• D：
• E：平面图网络流，转成对偶图后跑最短路。
• F：n² f[i][j]代表目前左边的矩形到第i个，左边到第j个，利用前缀最大值优化到O(1)转移即可。
• G：a[i],b[i]交替放，相邻一个数至少取一个，直接dp。
• H：
• I：把根节点儿子都拿出来，然后枚举B树size，则子树大小大于size的都必须在A树里，树HASH判断。
• J：先构造曼哈顿环，然后每一次将i和i+p连边，可以使得每个点的度数加2，如果k%2==1，每个点再与它对面点连边，注意n是奇数时会多连一条。

附加文件

• 1.png by chenjb