2017-Sp78-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，不久有人过J，sub读了J丢给cjb，cjb上机'''J1y8'''。cjb读了G就判断是个网络流，先行敲了dinic板子。渐渐有人过了A，sub和yzc经过了谨慎地讨论，yzc上机写A，wa了两发，打印检查。cjb和sub判断E是个cls的old题，cjb上机很快敲完，也wa了，调了精度wa在了后面的点，很难受。sub和yzc终于找到了A的问题，yzc上机终于'''A3y70'''。cjb在接下来的时间里修改了无数次的E，wa在各种各样的地方，其中cjb也和yzc讲解了树套树优化网络流的方法，yzc抽空上机写完了，sub独力开C，多次上机都告失败。最后cjb改了匪夷所思的地方后终于'''E12y145'''。yzc上机很快写完了G，提交获得tle。cjb表示可能要用二维st表代替树套树，给yzc讲解完后yzc上机'''G2y183'''。sub终于得到了C的做法，之后'''C1y203'''。之后三个人试图讨论D，没有得到很优美的做法，sub表示B是个三维凸包+最小圆覆盖的板子题，cjb上机开始敲，敲了20多min还让yzc查了很久bug，最后20min sub rush B没有成功，赛后20min通过了B，敲板子的时候sub给yzc理论了D，但是做法比较不清真，思路不清晰，没能达成输出。
== 总结 ==
=== chenjb ===
时隔多年，又一次吃了NAIPC的屎，其实还是套路上的欠缺，我们今天严格执行了“宁可差题数也不能差进度”这个策略，虽然5题还是有点差强人意，但是目前看来还是Acceptable的，很多队伍都是在临近final前做这套题，自然状态也不可同日而语，我们要在去MIPT前抓紧时间提高，步子迈大些也无所谓，把最后的磨合和调整留给MIPT CAMP。
=== oipotato ===
比起屎，可能还是烧烤比较好吃。
=== subconscious  ===
楼上说的对。
== 题解 ==
 * A：把括号序列处理成，左边都是右括号，右边都是左括号的形式，记为A个左括号，B个右括号。将B和A-B塞入数组，对于A-B>=0，按照A升序排序，否则按照A降序排序，dp即可，类似背包。
 * B：跑出三维凸包，枚举面，以面为圆柱底，所有点投影到该平面上，变成最小圆覆盖。
 * C：f[i][j]代表区间[i,j]生成树方案，g[i][j]代表从i到j已经有一条边的生成方案，如果i和j互质，方案数强制为0，f[i][j]=f[i][k]*g[k][j](i<=k<=j-1)，g[i][j]=Σf[i][k]*f[k][j](i<=k<=j-1)，答案为f[1][n]。
 * D：考虑类似最长上升子序列二分的做法，对于一棵子树，维护一个序列表示每个答案对应的最小权值，由于子树互相之间独立，可以直接合并所有子树的序列，将父亲节点在序列中二分，并替换掉大于本身的第一个值即可。具体实现时使用启发式合并，并用set维护此序列，一个巧妙的操作是离散化的时候对于相同权值的点，按照节点编号给予不同的离散化值，这样既保证了题目要求，又使所有节点权值不同，保证了set的正常工作。
 * E：二分一个mid值给特殊的边后跑MST，整数就可以了，注意排序的时候相同代价的边要把特殊的边放在后头，正确性待思考。
 * F
 * G：用二维st表优化最大流建边，每个买家只需要连出4条边对应自己的矩形(具体类比四分树)
 * H：可证必存在一点出边颜色完全相同。可不断找出剩下的图中的那个点，得到一序列Ai，称Ai颜色为出边颜色。之后枚举子图中最后出现的点。可维护一个数组代表贡献为x子图的方案树数。
 * I
 * J：统计两种字母个数，相同输出1，否则输出0。
 * K
== 补题 ==

流水账

开场各自看题，不久有人过J，sub读了J丢给cjb，cjb上机J1y8。cjb读了G就判断是个网络流，先行敲了dinic板子。渐渐有人过了A，sub和yzc经过了谨慎地讨论，yzc上机写A，wa了两发，打印检查。cjb和sub判断E是个cls的old题，cjb上机很快敲完，也wa了，调了精度wa在了后面的点，很难受。sub和yzc终于找到了A的问题，yzc上机终于A3y70。cjb在接下来的时间里修改了无数次的E，wa在各种各样的地方，其中cjb也和yzc讲解了树套树优化网络流的方法，yzc抽空上机写完了，sub独力开C，多次上机都告失败。最后cjb改了匪夷所思的地方后终于E12y145。yzc上机很快写完了G，提交获得tle。cjb表示可能要用二维st表代替树套树，给yzc讲解完后yzc上机G2y183。sub终于得到了C的做法，之后C1y203。之后三个人试图讨论D，没有得到很优美的做法，sub表示B是个三维凸包+最小圆覆盖的板子题，cjb上机开始敲，敲了20多min还让yzc查了很久bug，最后20min sub rush B没有成功，赛后20min通过了B，敲板子的时候sub给yzc理论了D，但是做法比较不清真，思路不清晰，没能达成输出。

总结

chenjb

时隔多年，又一次吃了NAIPC的屎，其实还是套路上的欠缺，我们今天严格执行了“宁可差题数也不能差进度”这个策略，虽然5题还是有点差强人意，但是目前看来还是Acceptable的，很多队伍都是在临近final前做这套题，自然状态也不可同日而语，我们要在去MIPT前抓紧时间提高，步子迈大些也无所谓，把最后的磨合和调整留给MIPT CAMP。

oipotato

比起屎，可能还是烧烤比较好吃。

subconscious

楼上说的对。

题解

  • A：把括号序列处理成，左边都是右括号，右边都是左括号的形式，记为A个左括号，B个右括号。将B和A-B塞入数组，对于A-B>=0，按照A升序排序，否则按照A降序排序，dp即可，类似背包。
  • B：跑出三维凸包，枚举面，以面为圆柱底，所有点投影到该平面上，变成最小圆覆盖。
  • C：f[i][j]代表区间[i,j]生成树方案，g[i][j]代表从i到j已经有一条边的生成方案，如果i和j互质，方案数强制为0，f[i][j]=f[i][k]*g[k][j](i<=k<=j-1)，g[i][j]=Σf[i][k]*f[k][j](i<=k<=j-1)，答案为f[1][n]。
  • D：考虑类似最长上升子序列二分的做法，对于一棵子树，维护一个序列表示每个答案对应的最小权值，由于子树互相之间独立，可以直接合并所有子树的序列，将父亲节点在序列中二分，并替换掉大于本身的第一个值即可。具体实现时使用启发式合并，并用set维护此序列，一个巧妙的操作是离散化的时候对于相同权值的点，按照节点编号给予不同的离散化值，这样既保证了题目要求，又使所有节点权值不同，保证了set的正常工作。
  • E：二分一个mid值给特殊的边后跑MST，整数就可以了，注意排序的时候相同代价的边要把特殊的边放在后头，正确性待思考。
  • F
  • G：用二维st表优化最大流建边，每个买家只需要连出4条边对应自己的矩形(具体类比四分树)
  • H：可证必存在一点出边颜色完全相同。可不断找出剩下的图中的那个点，得到一序列Ai，称Ai颜色为出边颜色。之后枚举子图中最后出现的点。可维护一个数组代表贡献为x子图的方案树数。
  • I
  • J：统计两种字母个数，相同输出1，否则输出0。
  • K

补题

附加文件