2017-Sp161-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，yzc上机'''A1y6'''，cjb上机'''I1y17'''，sub上机'''K1y26'''，yzc上机'''B1y32'''，cjb丢了C给yzc '''C1y47'''，sub上机'''L1y62'''，三人讨论E，sub上机'''E2y86'''，cjb上机'''G2y168'''，sub上机写J，'''J1y211'''，cjb和yzc开了H，'''H3y240'''，cjb上机写F预处理，sub上机'''F2y270'''，之后sub和yzc wa了两发D，现场榜rk1。
== 总结 ==
=== chenjb ===
还行，想AK。感觉大家集体训练打得不太行啊？G这种把图当树然后抠环维护的题可能越来越常见了？要多写写。
=== oipotato ===
=== subconscious  ===
快乐
== 题解 ==
 * A：完全背包。

 * B：暴力求解。

 * C：2^19^枚举，19*19检查。

 * D：反过来考虑变成经典暴力剪枝题，讨论一下发现特殊解符合ai>=2^(i-2)^，暴力预处理存下来即可。

 * E：分两类，一种是所有人变成lcm，另一种是当场上存在a类人的倍数，将a类人变成那个倍数，两种取min。

 * F：建出不等式图后缩点，状压dp算出有多少种不同的拓扑序即可。

 * G：跑出dfs树，所有非树边暴力将两点路径染色，有边被重复染色则代表有两个简单环有交，抠出来，取度数>=3的两个点暴搜出三条路径即可。

 * H：先把每棵树跑出最大匹配，且尽可能不去匹配根节点，然后把根节点被匹配的树连到1号点，剩余则按照非匹配点个数从大到小贪心连进主树即可。

 * I：答案是图形的周长减去套住的矩形的周长。

 * J：分块处理凸包，在凸包上二分即可。

 * K：构造一个x*y=n使2x-1<=h,2y-1<=w。

 * L：n本身，sqrt(n)两种特判，其他在1e6内暴力循环即可。

流水账

出门各自看题，yzc上机A1y6，cjb上机I1y17，sub上机K1y26，yzc上机B1y32，cjb丢了C给yzc C1y47，sub上机L1y62，三人讨论E，sub上机E2y86，cjb上机G2y168，sub上机写J，J1y211，cjb和yzc开了H，H3y240，cjb上机写F预处理，sub上机F2y270，之后sub和yzc wa了两发D，现场榜rk1。

总结

chenjb

还行，想AK。感觉大家集体训练打得不太行啊？G这种把图当树然后抠环维护的题可能越来越常见了？要多写写。

oipotato

subconscious

快乐

题解

A：完全背包。
B：暴力求解。
C：2¹⁹枚举，19*19检查。
D：反过来考虑变成经典暴力剪枝题，讨论一下发现特殊解符合ai>=2^(i-2)，暴力预处理存下来即可。
E：分两类，一种是所有人变成lcm，另一种是当场上存在a类人的倍数，将a类人变成那个倍数，两种取min。
F：建出不等式图后缩点，状压dp算出有多少种不同的拓扑序即可。
G：跑出dfs树，所有非树边暴力将两点路径染色，有边被重复染色则代表有两个简单环有交，抠出来，取度数>=3的两个点暴搜出三条路径即可。
H：先把每棵树跑出最大匹配，且尽可能不去匹配根节点，然后把根节点被匹配的树连到1号点，剩余则按照非匹配点个数从大到小贪心连进主树即可。
I：答案是图形的周长减去套住的矩形的周长。
J：分块处理凸包，在凸包上二分即可。
K：构造一个x*y=n使2x-1<=h,2y-1<=w。
L：n本身，sqrt(n)两种特判，其他在1e6内暴力循环即可。

附加文件

1.png by chenjb