2017-C03-team7
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== zhhhplus ==
流水账：今天到机房之前把昨天的几何题补了，心情不错，然后就在所有题目里面寻找看着容易的题，在盯住了1005之后，我就坐在旁边不断画图了。其间和chy讨论了1004改版KMP的正确性，一起找了1003的一点错（数组没开够大），就继续画图去了。在1003爆了一次内存之后，改了数据类型，但是返回了奇怪的WA，大家讨论了一下，wyz提出用鸽笼把过大的数据去掉，稳妥地过掉了1003（'''C2y35'''）（在之后发现第二发其实是A了的，不清楚是为什么），随后chy开始着手敲1004，我在这期间找出了1005的规律，和wyz讨论了一下觉得跑得应该足够快，我表示还能更快，最后稳妥起见，决定写将询问排序后的方案，chy在WA了一发1004之后，改了点小错误，就A了（'''D2y109'''），这时换上了wyz来听我嘴炮写1005，IO写好了一个大概之后我来缓慢地把主要内容填进去，在一不小心搞混了浮点数和整数之后（好在样例没过），随便改了改，觉得靠谱，就交了上去，平稳地一发A了（'''E1y122'''）。其后我开始构造1001，两位队友则调试1007，很久之后，在找出了十余个bug之后，终于过了样例，我们就大胆地提交了1007，结果却WA了，觉得有可能是爆了int甚至long long，输入了一个极端数据，发现比样例要小，我就表示你们这不可能不错嘛，肯定爆了范围，两位队友和我讲，这题有取模，我心道：怪不得。然后就默默去看这题的题干了，并没有找到，对自己的视力表示怀疑，莫非几何题调瞎了，就问了一下两位队友。大家定睛一看，并没有取模！督促两人把代码改了，然后继续构造去了。在修改了两次之后1007终于过掉了（'''G2y275'''），此时离比赛结束只剩下一个小时，大家觉得只有构造题可能来得及，就开始一起想构造题1001，我跟队友讲了之前自己已经推出来的一些性质，希望能避免走弯路，wyz表示想出了一组数据，我则想到了一种数据生成，此时时间只剩半小时了。wyz尝试交了自己的数据，WA了之后我马上上去敲生成器，中间又让给wyz来尝试了另一组数据（认为之前是顺序错了），又WA了之后，我开始疯狂写生成器，喜获一次WA，发现少写了某些东西，随后再交，觉得自己顺序有问题，着手修改，该好之后只剩下5分钟多，马上提交，这时网站却崩了，一直到结尾都没有交上去。后来发现顺序还是有问题，并且点数设置也不够多，输得透彻。
总结：和前两天比较，今天我们队伍的表现并不是很理想，队员的交流非常少，我本人卡智力题的时间也太久，以及作为队长没有较好地掌握局势，应该多加观察，保证大家的进程都没有空着，发挥更高的效率，以及在队友调试的时候没有帮助稳住心态，导致浪费了大量的时间，以及在最后解1001的时候情绪有点激动了，没有仔细考虑清楚做法是否完善。顺便自己卡智力题的时候，受到外界影响太大了，看到对面二队过了就很急，脑子一片空白，这时也没主动参加到讨论和帮助调试中，浪费了时间。比赛结束之后，看到5队表现得很不错，向他们的某位队员讨教之后，知道快速而稳定地解决掉签到题会带来很大的优势，平稳的心态也是很重要的因素。个人觉得我们队伍应该恢复到前两天的配合，做到1+1+1>3，岂不美哉。
== hanyi0923 ==
总结：今天可以说是这三天中发挥最不好的一天，虽然刚开始三人分别开了三题（我：KMP(Z-algorithm)，其他：结论题、贪心），但是后来我提出了D题（回文）的想法并讨论后让wyz写，却一直在debug，当时想着应该很快就好，就帮忙debug没看题，结果花了2小时才过题，后面就没再过题了。今天的问题可能是两方面的，编程方面如果我或队友可以快速稳定写对D题，就不会卡题；另一方面也应该控制debug时间，留编程的人自己继续debug，另外两个人往下看题，今天很多题是连题意都是赛后才理解，很不应该，下次不能再犯。
== zju_wyz ==
总结：今天可以说锅主要在我身上。回文数那题的调试问题实在是太致命了。不但我由于各种细节问题代码越改越丑，还拉上 chy 搭上了两个小时。其实这段时间如果能静下来想想屡清楚所有细节在上手写的话不应该出现今天这种情况——改一点地方->试一下->没过样例->加 printf() 进 gdb 慢慢调 ->再改一点地方。这也间接导致了我们最后一刻没有过掉 1001。这也暴露出我代码能力不足的问题，逻辑一多就会原地爆炸，甚至拉上旁边 debug 的小伙伴一起爆炸，浪费了大量时间。
在 debug 过程中出现的问题主要有：前导零问题（费时最多，因为很久之后才意识到数字中间的子串是允许有前导零的），递归边界问题(两位数的时候写挂了)，各种特殊情况（比如输入本身是一个回文数的时候，或者最后一个回文数取到/取不到的时候），以及纠结转好进制之后要不要 reverse()等等乱七八糟的东西，最后整个代码就像戏台上了老将军，浑身插满了 bool flag; 最后甚至还因为想当然的 % 了 100000007 而 WA 了一发。。。
总结下来还是自己的代码能力不够，驾驭算法不难但细节很多的程序的时候会有些力不从心。
== 题解 ==
'''1001'''
题意：构造一个结点数不大于500的图，使一个最小点覆盖的贪心算法选的点是实际最小点覆盖数目的三倍及以上。
解：
首先将最小点覆盖集合称为点集A（大小记为n），其余点为点集B，然后能够看出一个简单的结论：B集点之间无连边（不然A集就没有完全覆盖）。
随后思考尽量让贪心算法选择B集点（这里直接让贪心算法全选择B集点了），那么要求依次选择的B集点的度数应大于A集最大度数。而B集点度数最大为n（连了所有A集点），所以要选A集点，A集点度数最大也是n。
（这里可以知道一个结论，两集合间连边最多为n*n条）
（并且我们又知道，A集点之间最好也不要连边，这会提高它们的优先级，所以其实就是个二分图）
我们最早假设所有A集点的度数都为n（最后加完如果有剩是不影响的），那么要选择B集点，该B集点度数必须大于等于mx（A集最大度数）（并且通过安排序号，只要能选B集点，就能让贪心算法选）（另外选择某个B集点显然是不影响其余的B集点的），所以将该点与mx个度数最大的A集点们连线（为了减少mx的大小以减少两个集合之间的连边），这样尝试下去，直到B集点都有被连线，A集点也没被连接超过n条边。
题目要求贪心选择的点至少为最小点覆盖的三倍，那么我们就设置B集点为3n大小，然后太小的n会失败，几次尝试之后，知道48个点是最少的本构造方案的点数。
某感想：比赛的最后（剩余半小时）想出了这个方案并且实现了一次，但是以为A集点最后也会被选到，所以设了个2n的B集点，并且序号安排也有点不对，喜获WA。
补题：1001(√) 1006(√)zhhhplus
流水账：今天到机房之前把昨天的几何题补了，心情不错，然后就在所有题目里面寻找看着容易的题，在盯住了1005之后，我就坐在旁边不断画图了。其间和chy讨论了1004改版KMP的正确性，一起找了1003的一点错（数组没开够大），就继续画图去了。在1003爆了一次内存之后，改了数据类型，但是返回了奇怪的WA，大家讨论了一下，wyz提出用鸽笼把过大的数据去掉，稳妥地过掉了1003（C2y35）（在之后发现第二发其实是A了的，不清楚是为什么），随后chy开始着手敲1004，我在这期间找出了1005的规律，和wyz讨论了一下觉得跑得应该足够快，我表示还能更快，最后稳妥起见，决定写将询问排序后的方案，chy在WA了一发1004之后，改了点小错误，就A了（D2y109），这时换上了wyz来听我嘴炮写1005，IO写好了一个大概之后我来缓慢地把主要内容填进去，在一不小心搞混了浮点数和整数之后（好在样例没过），随便改了改，觉得靠谱，就交了上去，平稳地一发A了（E1y122）。其后我开始构造1001，两位队友则调试1007，很久之后，在找出了十余个bug之后，终于过了样例，我们就大胆地提交了1007，结果却WA了，觉得有可能是爆了int甚至long long，输入了一个极端数据，发现比样例要小，我就表示你们这不可能不错嘛，肯定爆了范围，两位队友和我讲，这题有取模，我心道：怪不得。然后就默默去看这题的题干了，并没有找到，对自己的视力表示怀疑，莫非几何题调瞎了，就问了一下两位队友。大家定睛一看，并没有取模！督促两人把代码改了，然后继续构造去了。在修改了两次之后1007终于过掉了（G2y275），此时离比赛结束只剩下一个小时，大家觉得只有构造题可能来得及，就开始一起想构造题1001，我跟队友讲了之前自己已经推出来的一些性质，希望能避免走弯路，wyz表示想出了一组数据，我则想到了一种数据生成，此时时间只剩半小时了。wyz尝试交了自己的数据，WA了之后我马上上去敲生成器，中间又让给wyz来尝试了另一组数据（认为之前是顺序错了），又WA了之后，我开始疯狂写生成器，喜获一次WA，发现少写了某些东西，随后再交，觉得自己顺序有问题，着手修改，该好之后只剩下5分钟多，马上提交，这时网站却崩了，一直到结尾都没有交上去。后来发现顺序还是有问题，并且点数设置也不够多，输得透彻。
总结：和前两天比较，今天我们队伍的表现并不是很理想，队员的交流非常少，我本人卡智力题的时间也太久，以及作为队长没有较好地掌握局势，应该多加观察，保证大家的进程都没有空着，发挥更高的效率，以及在队友调试的时候没有帮助稳住心态，导致浪费了大量的时间，以及在最后解1001的时候情绪有点激动了，没有仔细考虑清楚做法是否完善。顺便自己卡智力题的时候，受到外界影响太大了，看到对面二队过了就很急，脑子一片空白，这时也没主动参加到讨论和帮助调试中，浪费了时间。比赛结束之后，看到5队表现得很不错，向他们的某位队员讨教之后，知道快速而稳定地解决掉签到题会带来很大的优势，平稳的心态也是很重要的因素。个人觉得我们队伍应该恢复到前两天的配合，做到1+1+1>3，岂不美哉。
hanyi0923
总结：今天可以说是这三天中发挥最不好的一天，虽然刚开始三人分别开了三题（我：KMP(Z-algorithm)，其他：结论题、贪心），但是后来我提出了D题（回文）的想法并讨论后让wyz写，却一直在debug，当时想着应该很快就好，就帮忙debug没看题，结果花了2小时才过题，后面就没再过题了。今天的问题可能是两方面的，编程方面如果我或队友可以快速稳定写对D题，就不会卡题；另一方面也应该控制debug时间，留编程的人自己继续debug，另外两个人往下看题，今天很多题是连题意都是赛后才理解，很不应该，下次不能再犯。
zju_wyz
总结：今天可以说锅主要在我身上。回文数那题的调试问题实在是太致命了。不但我由于各种细节问题代码越改越丑，还拉上 chy 搭上了两个小时。其实这段时间如果能静下来想想屡清楚所有细节在上手写的话不应该出现今天这种情况——改一点地方->试一下->没过样例->加 printf() 进 gdb 慢慢调 ->再改一点地方。这也间接导致了我们最后一刻没有过掉 1001。这也暴露出我代码能力不足的问题，逻辑一多就会原地爆炸，甚至拉上旁边 debug 的小伙伴一起爆炸，浪费了大量时间。
在 debug 过程中出现的问题主要有：前导零问题（费时最多，因为很久之后才意识到数字中间的子串是允许有前导零的），递归边界问题(两位数的时候写挂了)，各种特殊情况（比如输入本身是一个回文数的时候，或者最后一个回文数取到/取不到的时候），以及纠结转好进制之后要不要 reverse()等等乱七八糟的东西，最后整个代码就像戏台上了老将军，浑身插满了 bool flag; 最后甚至还因为想当然的 % 了 100000007 而 WA 了一发。。。
总结下来还是自己的代码能力不够，驾驭算法不难但细节很多的程序的时候会有些力不从心。
题解
1001
题意：构造一个结点数不大于500的图，使一个最小点覆盖的贪心算法选的点是实际最小点覆盖数目的三倍及以上。
解：
首先将最小点覆盖集合称为点集A（大小记为n），其余点为点集B，然后能够看出一个简单的结论：B集点之间无连边（不然A集就没有完全覆盖）。
随后思考尽量让贪心算法选择B集点（这里直接让贪心算法全选择B集点了），那么要求依次选择的B集点的度数应大于A集最大度数。而B集点度数最大为n（连了所有A集点），所以要选A集点，A集点度数最大也是n。
（这里可以知道一个结论，两集合间连边最多为n*n条）
（并且我们又知道，A集点之间最好也不要连边，这会提高它们的优先级，所以其实就是个二分图）
我们最早假设所有A集点的度数都为n（最后加完如果有剩是不影响的），那么要选择B集点，该B集点度数必须大于等于mx（A集最大度数）（并且通过安排序号，只要能选B集点，就能让贪心算法选）（另外选择某个B集点显然是不影响其余的B集点的），所以将该点与mx个度数最大的A集点们连线（为了减少mx的大小以减少两个集合之间的连边），这样尝试下去，直到B集点都有被连线，A集点也没被连接超过n条边。
题目要求贪心选择的点至少为最小点覆盖的三倍，那么我们就设置B集点为3n大小，然后太小的n会失败，几次尝试之后，知道48个点是最少的本构造方案的点数。
某感想：比赛的最后（剩余半小时）想出了这个方案并且实现了一次，但是以为A集点最后也会被选到，所以设了个2n的B集点，并且序号安排也有点不对，喜获WA。
补题：1001(√) 1006(√)