2019-team0x03-0003

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Standings.png, 500px)]][[Image(Submissions.png, 500px)]]
== 概述 ==
七月集训第三场
== 流水账 ==
出门各自看题。开场lcd开出了A先上机写着。sds上机签H，由于网络问题花了一些时间，第一发提交有些晚，'''H2y39'''。sds继续签L，获得RE后lmh上机写I，获得wa后sds很快调过了L，'''L2y62'''。之后sds叉掉了lmh的I做法自己写了一个，'''I2y86'''。lcd断断续续写完了A的代码，'''A1y108'''。之后lmh上机写F并获得了wa，sds敏锐地指出了lmh的读题错误，'''F2y133'''。lcd上机写D，'''D1y156'''。sds和lcd讨论出了G的dp做法，在MLE一发后迅速过了G，'''G2y193'''。期间lmh开出了E和J并上机写E，获得wa后lcd上机写M，同样wa了，两人轮流对着打印的代码焦头烂额，期间sds听了J的做法。lmh信誓旦旦地认为能在封榜后过掉这三题，而sds觉得能过一题就不错了（一人一大口奶）。将近270min时sds给出了J的具体实现，然鹅lcd和lmh一直在wa，sds看了进度后决定先合力过掉这两题，结果全队对着wa声一片陷入自闭。
== 总结 ==
=== SidneySun ===
=== lichangdongtw ===

上来我看了A，发现树剖可以直接做，我就冲上去写了，中间队友看榜好像切了3道签到题，我在1个小时左右的时候写完，样例第二组询问没过，调试加修改一共花了大概20min多一点，发现线段树部分的查询 和修改有点萎，改了后过了样例就一发过了，拿了A的一血

中间队友写题的时候我看了B,C不太会，想了D,G和M的解法，我把G的做法给了sds，lmh写完下机后我上去写D，写完一发过拿下D的一血

队友上机的时候推了M的dp，看了看J不太会，其他题看起来不太可开也没看

M是个wqs二分，我写之前并没有把握能过，因为这种题我之前做都WA的痛苦不堪，事实上赛场上我也WA的痛苦不堪

 * M的问题主要有几点
   * 二分的上下界模糊，并没有意识到要定为边权最大值*n
   * 负数的四舍五入和正数不太一样
   * 凸函数中的共线情况可能并没有处理好，这个也涉及到二分的写法问题

 * 关于M学到的
   * 首先边权都是整数，所以函数都是整点，相邻点斜率必为整数，可以只二分整数
   * 然后二分的姿势应该是当>=K时，l=mid+1，最后的答案用l-1再跑一次dp，就算dp出来取得边数>K，也可以f+(l-1)*K，算出来是对的，这种就是共线的情况（注意dp过程中相同的f值取最多的边数）
=== ntwbvdbl_oe ===
 * sblmh太菜了，在简单题上他会得出一堆错误解法坑队友。
 * sblmh还是喜欢模拟和构造题，如果他的英语不出锅他还是比较可靠的。
 * sblmh能开出一些神奇的题目，但他的思维漏洞可能很多，他需要将做法讲给队友，再让队友去考虑实现细节。
 * sblmh的代码实现有很大问题，他需要多敲代码并锻炼他的逻辑严密性。
 * 菜 lmh 菜

== 题解 ==
 * A:
 * B:
 * C:
 * D:
 * E: 去掉重边并将度数为2的点缩为一条边，不断重复，直至只剩两个点和一条边即为合法
 * F: 左边建n/2，右边建n/2+1，丢进map里面
 * G:
 * H:
 * I: 暴力计算sg函数
 * J: 枚举每个高度，找到其左右扩展的边界，对于每个面积，就可以O(n)计算出小于或等于它的矩形数量。首先二分找到排序为LR的两个面积，再用类似方法统计答案
 * K:
 * L:
 * M:

[wiki:2019-team0x03 Back]

概述

七月集训第三场

流水账

出门各自看题。开场lcd开出了A先上机写着。sds上机签H，由于网络问题花了一些时间，第一发提交有些晚，H2y39。sds继续签L，获得RE后lmh上机写I，获得wa后sds很快调过了L，L2y62。之后sds叉掉了lmh的I做法自己写了一个，I2y86。lcd断断续续写完了A的代码，A1y108。之后lmh上机写F并获得了wa，sds敏锐地指出了lmh的读题错误，F2y133。lcd上机写D，D1y156。sds和lcd讨论出了G的dp做法，在MLE一发后迅速过了G，G2y193。期间lmh开出了E和J并上机写E，获得wa后lcd上机写M，同样wa了，两人轮流对着打印的代码焦头烂额，期间sds听了J的做法。lmh信誓旦旦地认为能在封榜后过掉这三题，而sds觉得能过一题就不错了（一人一大口奶）。将近270min时sds给出了J的具体实现，然鹅lcd和lmh一直在wa，sds看了进度后决定先合力过掉这两题，结果全队对着wa声一片陷入自闭。

总结

SidneySun

lichangdongtw

上来我看了A，发现树剖可以直接做，我就冲上去写了，中间队友看榜好像切了3道签到题，我在1个小时左右的时候写完，样例第二组询问没过，调试加修改一共花了大概20min多一点，发现线段树部分的查询 和修改有点萎，改了后过了样例就一发过了，拿了A的一血

中间队友写题的时候我看了B,C不太会，想了D,G和M的解法，我把G的做法给了sds，lmh写完下机后我上去写D，写完一发过拿下D的一血

队友上机的时候推了M的dp，看了看J不太会，其他题看起来不太可开也没看

M是个wqs二分，我写之前并没有把握能过，因为这种题我之前做都WA的痛苦不堪，事实上赛场上我也WA的痛苦不堪

• M的问题主要有几点
  • 二分的上下界模糊，并没有意识到要定为边权最大值*n
  • 负数的四舍五入和正数不太一样
  • 凸函数中的共线情况可能并没有处理好，这个也涉及到二分的写法问题
• 关于M学到的
  • 首先边权都是整数，所以函数都是整点，相邻点斜率必为整数，可以只二分整数
  • 然后二分的姿势应该是当>=K时，l=mid+1，最后的答案用l-1再跑一次dp，就算dp出来取得边数>K，也可以f+(l-1)*K，算出来是对的，这种就是共线的情况（注意dp过程中相同的f值取最多的边数）

ntwbvdbl_oe

• sblmh太菜了，在简单题上他会得出一堆错误解法坑队友。
• sblmh还是喜欢模拟和构造题，如果他的英语不出锅他还是比较可靠的。
• sblmh能开出一些神奇的题目，但他的思维漏洞可能很多，他需要将做法讲给队友，再让队友去考虑实现细节。
• sblmh的代码实现有很大问题，他需要多敲代码并锻炼他的逻辑严密性。
• 菜 lmh 菜

题解

• A:
• B:
• C:
• D:
• E: 去掉重边并将度数为2的点缩为一条边，不断重复，直至只剩两个点和一条边即为合法
• F: 左边建n/2，右边建n/2+1，丢进map里面
• G:
• H:
• I: 暴力计算sg函数
• J: 枚举每个高度，找到其左右扩展的边界，对于每个面积，就可以O(n)计算出小于或等于它的矩形数量。首先二分找到排序为LR的两个面积，再用类似方法统计答案
• K:
• L:
• M:

Back

附加文件

• Standings.png by ntwbvdbl_oe
• Submissions.png by ntwbvdbl_oe