2017-Sp171-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门看题，有个人过了L，sub和yzc开心做L，然后wa了，yzc上机'''J1y31'''，之后L变成了MLE，然后cjb上机试图水H，'''H3y43'''，之后L疯狂炸裂，甚至MLE 23。发现大家纷纷过了B，cjb读了上机'''B1y62'''，sub推好了C的式子给yzc，'''C1y64'''，之后yzc上机I又mle了，cjb上机写F，yzc陷入自闭，'''F1y109'''，之后sub帮yzc fix了I，yzc上机'''I2y125'''，之后cjb了解了下L的情况，建议用unordered_set，然后过了更多的点，缘分了一下阈值就'''L7y135'''，之后sub上机写A，'''A1y155'''。之后cjb上机开始写E，然后PE 2，assert了一下确信了自己的构造有问题，陷入自闭。sub和yzc开始搞G，'''G3y226'''，之后cjb上机fix E，'''E3y243'''。之后sub开始搞K，玄学卡常'''K6y293'''。
== 总结 ==
=== chenjb ===
今天还行，写了四个题，sub最后一发入魂真的爽，不过今天罚时非常糟糕.jpg 另外就是unordered_set内存比set少，甚至还能缘分地更快。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：存在原根，从原根统计出来之后最后是一个exgcd。

 * B：最大权闭合子图裸题。

 * C：推式子，答案为1/R^2^((Σri)^2^-Σri^2^)

 * D：

 * E：有结论：任何一个最大度数不大于k的子图都能被成功染色，所以先找到边数最大的满足条件的子图，之后考虑按点度数从大到小对相关边进行染色，直接基于残余网络进行匹配，然后将已染色的点度数--，重复k次。

 * F：所有数字同时乘以r的逆元之后，贪心从大到小如果能凑就放进背包，因为满足Σs[1..i-1]<s[i]，所以必定是这样构造。

 * G：预处理终点开始一步一步走，走2^16^次步的结果，然后枚举从起点以2^16^为步长，走0..2^16^步，维护答案即可。

 * H：实际上有结论每个点只需要向四个象限最近的点连边，然后kruskal即可。然而数据水，prim暴力可过。

 * I：f[i][j]表示前i个数字最后一段区间是i..j的答案，然后一开始将所有区间，按照区间和排序，按照这个顺序往后做，维护f[i]的最值，并且维护从哪个区间转移到当前区间，最后从n回推即可。

 * J：模拟。

 * K：在使用一次飞机之后，就把那条边的出度从飞机图上删去，可以证明均摊之后是三元环数量，卡一卡常就过了。

 * L：k个点能完全保住的连通块显然大小是有限的，巧妙地取此大小(本队取了n*k/2)，从起点终点各广搜一次即可，甚至可能要用unordered_set。

流水账

出门看题，有个人过了L，sub和yzc开心做L，然后wa了，yzc上机J1y31，之后L变成了MLE，然后cjb上机试图水H，H3y43，之后L疯狂炸裂，甚至MLE 23。发现大家纷纷过了B，cjb读了上机B1y62，sub推好了C的式子给yzc，C1y64，之后yzc上机I又mle了，cjb上机写F，yzc陷入自闭，F1y109，之后sub帮yzc fix了I，yzc上机I2y125，之后cjb了解了下L的情况，建议用unordered_set，然后过了更多的点，缘分了一下阈值就L7y135，之后sub上机写A，A1y155。之后cjb上机开始写E，然后PE 2，assert了一下确信了自己的构造有问题，陷入自闭。sub和yzc开始搞G，G3y226，之后cjb上机fix E，E3y243。之后sub开始搞K，玄学卡常K6y293。

总结

chenjb

今天还行，写了四个题，sub最后一发入魂真的爽，不过今天罚时非常糟糕.jpg 另外就是unordered_set内存比set少，甚至还能缘分地更快。

oipotato

subconscious

题解

  • A：存在原根，从原根统计出来之后最后是一个exgcd。
  • B：最大权闭合子图裸题。
  • C：推式子，答案为1/R2((Σri)2-Σri2)
  • D：
  • E：有结论：任何一个最大度数不大于k的子图都能被成功染色，所以先找到边数最大的满足条件的子图，之后考虑按点度数从大到小对相关边进行染色，直接基于残余网络进行匹配，然后将已染色的点度数--，重复k次。
  • F：所有数字同时乘以r的逆元之后，贪心从大到小如果能凑就放进背包，因为满足Σs[1..i-1]
  • G：预处理终点开始一步一步走，走216次步的结果，然后枚举从起点以216为步长，走0..216步，维护答案即可。
  • H：实际上有结论每个点只需要向四个象限最近的点连边，然后kruskal即可。然而数据水，prim暴力可过。
  • I：f[i][j]表示前i个数字最后一段区间是i..j的答案，然后一开始将所有区间，按照区间和排序，按照这个顺序往后做，维护f[i]的最值，并且维护从哪个区间转移到当前区间，最后从n回推即可。
  • J：模拟。
  • K：在使用一次飞机之后，就把那条边的出度从飞机图上删去，可以证明均摊之后是三元环数量，卡一卡常就过了。
  • L：k个点能完全保住的连通块显然大小是有限的，巧妙地取此大小(本队取了n*k/2)，从起点终点各广搜一次即可，甚至可能要用unordered_set。
附加文件