2017-Sp210-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb很快在yzc和sub的帮助下写D，wa了，yzc上机写C，wa了，之后sub发现问题，'''D2y36'''。cjb发现H是做过的构造题，'''H1y47'''，yzc发现问题'''C1y50'''。cjb丢了K给yzc，'''K2y93'''。sub一直试图手推E，cjb让他丢了自己上去写随机增量，'''E1y110'''。之后cjb和yzc开了J，会做之后cjb上机'''J1y150'''。sub和yzc开了G，yzc上机'''G2y169'''。cjb很早就和sub商量好了I，sub上机'''I1y187'''。之后sub和yzc开F，大力猜想结论之后上暴力dp，wa了之后assert帮助下yzc查了个错误，'''F2y255'''。cjb上机rush L，结果因为板子的支配树有个变量名字错了wa到了比赛结束，sub一直思考B无果。
== 总结 ==
=== chenjb ===
绝望，被板子坑了我的L。居然是namespace里板子内部变量名定义错了，然后又神秘地用了外部的同名数组这种问题。另外今天前期有点慢，签到磕磕绊绊。这个B怎么回事儿啊，为啥大家都会啊???
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：

 * B：sub的构造

 * C：答案显然不超过3，1只有可能全局翻转，2有包含和交叉两种情况分别讨论即可。

 * D：把单种货币和超过50的打包，问题变成dp不超过50的部分，然后用组合数计算有多少个包即可。

 * E：随机增量求三维费马点。

 * F：易猜想，存在任何子树中三色差不超过1的方案，直接暴力dp即可。

 * G：f[i][j]代表到i长度为j的最小斜率，动态单调队列优化转移。

 * H：经典构造，可以生成<=3的方案或检测是否存在<=2的方案：dfs遍历树，向下递归时填深度为偶数的部分，返回时填深度为奇数的部分。

 * I：左右做凸包处理出区间变成最小点覆盖区间，贪心即可。

 * J：kmp求出所有匹配区间，之后f[i]代表在取i点且前1-i已经合法的最小代价，显然i>j且f[i]<f[j]时j必然不可能有有效转移，所以双端队列维护即可。

 * K：显然可以根据取最小的k个和最大的k个确定合法区间，顺序枚举每一个数，用相同方法判断即可。

 * L：显然各SCC分开考虑，对于每个SCC，随便取1个点作为根，跑支配树，任何点的支配父亲不为根时，该父亲为合法点，反图同理再跑一次；注意此时根的答案不能确定，可以换一个根再做一次，也可以去掉该点再跑一次tarjan判定。

流水账

出门各自看题，cjb很快在yzc和sub的帮助下写D，wa了，yzc上机写C，wa了，之后sub发现问题，D2y36。cjb发现H是做过的构造题，H1y47，yzc发现问题C1y50。cjb丢了K给yzc，K2y93。sub一直试图手推E，cjb让他丢了自己上去写随机增量，E1y110。之后cjb和yzc开了J，会做之后cjb上机J1y150。sub和yzc开了G，yzc上机G2y169。cjb很早就和sub商量好了I，sub上机I1y187。之后sub和yzc开F，大力猜想结论之后上暴力dp，wa了之后assert帮助下yzc查了个错误，F2y255。cjb上机rush L，结果因为板子的支配树有个变量名字错了wa到了比赛结束，sub一直思考B无果。

总结

chenjb

绝望，被板子坑了我的L。居然是namespace里板子内部变量名定义错了，然后又神秘地用了外部的同名数组这种问题。另外今天前期有点慢，签到磕磕绊绊。这个B怎么回事儿啊，为啥大家都会啊???

oipotato

subconscious

题解

  • A：
  • B：sub的构造
  • C：答案显然不超过3，1只有可能全局翻转，2有包含和交叉两种情况分别讨论即可。
  • D：把单种货币和超过50的打包，问题变成dp不超过50的部分，然后用组合数计算有多少个包即可。
  • E：随机增量求三维费马点。
  • F：易猜想，存在任何子树中三色差不超过1的方案，直接暴力dp即可。
  • G：f[i][j]代表到i长度为j的最小斜率，动态单调队列优化转移。
  • H：经典构造，可以生成<=3的方案或检测是否存在<=2的方案：dfs遍历树，向下递归时填深度为偶数的部分，返回时填深度为奇数的部分。
  • I：左右做凸包处理出区间变成最小点覆盖区间，贪心即可。
  • J：kmp求出所有匹配区间，之后f[i]代表在取i点且前1-i已经合法的最小代价，显然i>j且f[i]
  • K：显然可以根据取最小的k个和最大的k个确定合法区间，顺序枚举每一个数，用相同方法判断即可。
  • L：显然各SCC分开考虑，对于每个SCC，随便取1个点作为根，跑支配树，任何点的支配父亲不为根时，该父亲为合法点，反图同理再跑一次；注意此时根的答案不能确定，可以换一个根再做一次，也可以去掉该点再跑一次tarjan判定。
附加文件