2019-team3-0031
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2019-team3 返回]
[[Image(1.png,700px)]]
== 概述 ==
七月集训第三场
== 总结 ==
=== HbFS- ===
比赛完了刚开始觉得俩队友都在演戏，后来发现自己是演戏演的最真实的。感觉整场比赛除了扯犊子没干啥事儿，最大的作用就是自告奋勇上去帮lsy查代码，虽然啥也没看出来但是废物利用：自闭了个最菜的，解放了个最强的。
感觉这两场比赛打比赛之前心情都挺糟糕的，所以比赛的时候老是感觉使不上劲。当了两场比赛的工具人，一直打工一直爽。
比赛中期有一点点失控，特别想把A题查出来以至于中期一度忘记了时间，以为才过了一个半个小时没想到只剩一个多小时了，当时感觉有点懵。自己有一点掉进了A题里面去，被这道题所困住了，以至于虽然还有很多题目未读，很多题目可以做也没有去做。最重要的是感觉队伍失去了指挥，节奏有一点点乱，队伍一度非常迷茫非常自闭。
虽然感觉队伍在这场比赛经历了挺大的困难，最后题数和排名还算看得下去，但感觉有些地方处理的的确不是很好。
A题，调试到一半突然想起来应该让cyw也看一下这个代码，于是把题意和做法跟cyw说了，最后也是他上机一通乱写订正了这个题。事实证明越多人看错误真的越容易被发现出来，有问题多求助队友总是没错的。竞赛里有些签到题也是这样，很可能一个人一下子想不到，这也是很正常的事情，多和几个人说一说题意很可能就算不是擅长这类型题目的队友也能把这个题做出来。
比赛中期明显感觉到情绪波折很大，当时自己也有一点点小绝望。担心负面情绪在队伍里面蔓延，但浩然的牛逼也没有吹起来，一直到比赛最后感觉写M题的时候也是很心急很着急的。还是希望大家比赛的时候能够静下心来，集中在题目和代码上， 榜的作用是指导开题和写题，排名在比赛进行中是次要的。毕竟ACM比赛是在五个小时结束后才计算每支队伍的排名，前期的领先或者落后可能都和最终结果相差甚远。
G觉是一个自己心里想的很清楚，一开始没有转述说清楚，然后cyw写的时候也有点着急的题目。因为一直在专心于A题，所以很晚才注意到cyw的G题已经非常自闭了。于是赶紧让他去搞其他的题目，自己改了改他的代码就过了。
还是希望明天的比赛好起来，大家别演戏了，一起打真赛。
=== LIN452 ===
今天的A题我要背锅了。开场一小时A就被开出来了，我103分钟时写完交了第一发，RE43，遂下机查错。
我和dhr一起看代码，看了很久都没发现可能会RE的地方，之后造大数据跑，本地爆栈，改了一个手写栈上去，还是RE43，这时候也没有开出新题，就感觉整个队伍心态有点崩。
中途我把cyw改良的D题写了交上去（犯了两个沙雕错误,多了两发罚时），过了D之后，dhr就拉cyw一起看A题，并让他上机玩一玩A题，面向OJ调试了几发之后发现了RE是n=1的情况，改了之后就过了。
今天队伍在A题上花了太多时间了，静态查错反复看代码，上机调试，造数据、手写栈，将近花了2小时。
如果一开始写的时候意识到了n=1的问题，会给接下来的题目留更多的时间，尤其在这一场的可做题很多的情况下。
以后遇到线段树RE，考虑l>r的可能性；遇到树链剖分处理边的信息，要考虑n=1的情况。以及E题的倒过来模拟法的思路好巧妙啊QAQ
面向OJ调试感觉好有效啊
=== Pepcy_Ch ===
上来交错题 + 忘记分母1 造成两法罚时，吹响了爆炸的号角。
签了 H、I、F 后想 G，dhr 给出了一种状态的设计方式，我试着写了写式子后去写了，在经历了初值设错的问题后，发现我的转移不能提前赊一盏灯。因为觉得自己能改过来，就一直倔强地改着 G，浪费了一些时间才让给 dhr 去改。
之后给下机的 lsy 讲 dhr 曾给出的 D 的错误的贪心的做法，发现问题在于出去的点的 L 的值，提出更新一遍再贪心，于是 lsy 过了 D。
期间我看了 lsy A 的代码，感觉正确无比，想了一下 n=1 会不会'''在修改时'''出问题，但发现没有问题。尝试去面向 OJ 调试，试错两次失败后测了一下 n=1 的数据，令我意外地 RE 了（因为我之前觉得没有问题，也觉得 n=1 不像是会被忽略的 corner case），改了之后过了。（其实一开的 A 应该就只有这一出错，10^5^ 级别的 dfs 在我印象中是不会爆栈的，但处于对 dhr gdb 的相信，还是中途去写了手写栈，这一下也浪费了不少时间的样子）
最后去想 M（因为发现自己想不出 B 和 E），回想起一个叫啥啥啥二分的技巧（赛后查找发现叫 wqs 二分，因为它能解决去年南京时一道过了一片但我们不会的 B 所以印象很深）。觉得这个 M 的性质和我印象中啥啥啥二分的要求不太一样，以及自己从没有写过这个啥啥啥二分，抱着怀疑的态度写了一下，发现过了样例，提交 WA 23。dhr 提出应该二分实数，但 WA 7（TLE 是在确定二分次数）。回过头来改整数二分的上下界，WA 35、37，但再过不了更多的点了。
整个比赛从出门两个罚时开始就比较急，再加上中途疯狂卡题，感觉自己这场比赛打得心很是不静。
这个 E 题，三人纷纷画出来 dfs 树和一些反祖边，尝试从环上找到性质。我曾提出过串联交点是割点的性质，但事实上这个性质也是不够强且不够可做的。感觉 E 没有接近过正解。但是今天的其他签到题还是比较快的，留出了更多的时间（用来自闭）。
赛后一直在自闭 M，补掉 M 题后又半个小时终于理解了这个二分：一是'''最后要补上的是题目要求的 K 倍二分值而不是 DP 跑出来的边数倍二分值'''；二是'''应该在 DP 时规定取更多的边（或更少），因为一个二分值对应的数目可以是一个区间，只有正确使用边界值比较才能 AC。去考虑没有取等的一侧会更容易想清楚和写对'''；三是 '''wqs 二分是不需要实数二分的'''；四是'''无解应当提前判'''。感觉提升了自己对二分的认识。
题外话：cjb 讲 M 时提到有一个叫 Aliens 的题用到了这个技巧，记得 UOJ 群里曾有人问 300iq 什么是 "aliens-trick"，后来得出的结论是 aliens-trick = wqs二分。
=== 补题 ===[/wiki/2019-team3 返回]
概述
七月集训第三场
总结
HbFS-
比赛完了刚开始觉得俩队友都在演戏，后来发现自己是演戏演的最真实的。感觉整场比赛除了扯犊子没干啥事儿，最大的作用就是自告奋勇上去帮lsy查代码，虽然啥也没看出来但是废物利用：自闭了个最菜的，解放了个最强的。
感觉这两场比赛打比赛之前心情都挺糟糕的，所以比赛的时候老是感觉使不上劲。当了两场比赛的工具人，一直打工一直爽。
比赛中期有一点点失控，特别想把A题查出来以至于中期一度忘记了时间，以为才过了一个半个小时没想到只剩一个多小时了，当时感觉有点懵。自己有一点掉进了A题里面去，被这道题所困住了，以至于虽然还有很多题目未读，很多题目可以做也没有去做。最重要的是感觉队伍失去了指挥，节奏有一点点乱，队伍一度非常迷茫非常自闭。
虽然感觉队伍在这场比赛经历了挺大的困难，最后题数和排名还算看得下去，但感觉有些地方处理的的确不是很好。
A题，调试到一半突然想起来应该让cyw也看一下这个代码，于是把题意和做法跟cyw说了，最后也是他上机一通乱写订正了这个题。事实证明越多人看错误真的越容易被发现出来，有问题多求助队友总是没错的。竞赛里有些签到题也是这样，很可能一个人一下子想不到，这也是很正常的事情，多和几个人说一说题意很可能就算不是擅长这类型题目的队友也能把这个题做出来。
比赛中期明显感觉到情绪波折很大，当时自己也有一点点小绝望。担心负面情绪在队伍里面蔓延，但浩然的牛逼也没有吹起来，一直到比赛最后感觉写M题的时候也是很心急很着急的。还是希望大家比赛的时候能够静下心来，集中在题目和代码上， 榜的作用是指导开题和写题，排名在比赛进行中是次要的。毕竟ACM比赛是在五个小时结束后才计算每支队伍的排名，前期的领先或者落后可能都和最终结果相差甚远。
G觉是一个自己心里想的很清楚，一开始没有转述说清楚，然后cyw写的时候也有点着急的题目。因为一直在专心于A题，所以很晚才注意到cyw的G题已经非常自闭了。于是赶紧让他去搞其他的题目，自己改了改他的代码就过了。
还是希望明天的比赛好起来，大家别演戏了，一起打真赛。
LIN452
今天的A题我要背锅了。开场一小时A就被开出来了，我103分钟时写完交了第一发，RE43，遂下机查错。
我和dhr一起看代码，看了很久都没发现可能会RE的地方，之后造大数据跑，本地爆栈，改了一个手写栈上去，还是RE43，这时候也没有开出新题，就感觉整个队伍心态有点崩。
中途我把cyw改良的D题写了交上去（犯了两个沙雕错误,多了两发罚时），过了D之后，dhr就拉cyw一起看A题，并让他上机玩一玩A题，面向OJ调试了几发之后发现了RE是n=1的情况，改了之后就过了。
今天队伍在A题上花了太多时间了，静态查错反复看代码，上机调试，造数据、手写栈，将近花了2小时。
如果一开始写的时候意识到了n=1的问题，会给接下来的题目留更多的时间，尤其在这一场的可做题很多的情况下。
以后遇到线段树RE，考虑l>r的可能性；遇到树链剖分处理边的信息，要考虑n=1的情况。以及E题的倒过来模拟法的思路好巧妙啊QAQ
面向OJ调试感觉好有效啊
Pepcy_Ch
上来交错题 + 忘记分母1 造成两法罚时，吹响了爆炸的号角。
签了 H、I、F 后想 G，dhr 给出了一种状态的设计方式，我试着写了写式子后去写了，在经历了初值设错的问题后，发现我的转移不能提前赊一盏灯。因为觉得自己能改过来，就一直倔强地改着 G，浪费了一些时间才让给 dhr 去改。
之后给下机的 lsy 讲 dhr 曾给出的 D 的错误的贪心的做法，发现问题在于出去的点的 L 的值，提出更新一遍再贪心，于是 lsy 过了 D。
期间我看了 lsy A 的代码，感觉正确无比，想了一下 n=1 会不会在修改时出问题，但发现没有问题。尝试去面向 OJ 调试，试错两次失败后测了一下 n=1 的数据，令我意外地 RE 了（因为我之前觉得没有问题，也觉得 n=1 不像是会被忽略的 corner case），改了之后过了。（其实一开的 A 应该就只有这一出错，105 级别的 dfs 在我印象中是不会爆栈的，但处于对 dhr gdb 的相信，还是中途去写了手写栈，这一下也浪费了不少时间的样子）
最后去想 M（因为发现自己想不出 B 和 E），回想起一个叫啥啥啥二分的技巧（赛后查找发现叫 wqs 二分，因为它能解决去年南京时一道过了一片但我们不会的 B 所以印象很深）。觉得这个 M 的性质和我印象中啥啥啥二分的要求不太一样，以及自己从没有写过这个啥啥啥二分，抱着怀疑的态度写了一下，发现过了样例，提交 WA 23。dhr 提出应该二分实数，但 WA 7（TLE 是在确定二分次数）。回过头来改整数二分的上下界，WA 35、37，但再过不了更多的点了。
整个比赛从出门两个罚时开始就比较急，再加上中途疯狂卡题，感觉自己这场比赛打得心很是不静。
这个 E 题，三人纷纷画出来 dfs 树和一些反祖边，尝试从环上找到性质。我曾提出过串联交点是割点的性质，但事实上这个性质也是不够强且不够可做的。感觉 E 没有接近过正解。但是今天的其他签到题还是比较快的，留出了更多的时间（用来自闭）。
赛后一直在自闭 M，补掉 M 题后又半个小时终于理解了这个二分：一是最后要补上的是题目要求的 K 倍二分值而不是 DP 跑出来的边数倍二分值；二是应该在 DP 时规定取更多的边（或更少），因为一个二分值对应的数目可以是一个区间，只有正确使用边界值比较才能 AC。去考虑没有取等的一侧会更容易想清楚和写对；三是 wqs 二分是不需要实数二分的；四是无解应当提前判。感觉提升了自己对二分的认识。
题外话：cjb 讲 M 时提到有一个叫 Aliens 的题用到了这个技巧，记得 UOJ 群里曾有人问 300iq 什么是 "aliens-trick"，后来得出的结论是 aliens-trick = wqs二分。
补题
附加文件
- 1.png by Pepcy_Ch