2017-C05-team1

从 Trac 迁移的文章

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

原文章内容如下：

注：今日由于jsb学长参加竺院选拔考，比赛的前3.5h只有lsmll和shb两个人参赛。


[[Image(44.png)]] 

== lsmll ==
流水账：还是倒着看，K是计算几何，于是就跳过了。看了J，想了一个贪心做法，于是等shb写完签到题C之后去写了，结果获得WA，后来仔细一想感觉贪心是不太靠谱，于是暂时搁置J题。看榜(combined，下同)发现H题、F题过的人较多，我看了H题发现只要递归求每个数在Grey Code中的位置然后减一下就行，于是在shb过了E题后就去写了，刚开始算术左移的地方(1<<n,n<=60,应该写成1LL<<n)没转换long long结果WA了一发。后来shb和我讨论出了F的做法，他去上机写了并通过。然后再次看榜，I题过的人最多，其次是A和J。我们刚开始觉得I是斯坦纳树，但是后来shb发现由于只有两个关键点，所以枚举分叉点就行，于是他去写了，并通过。后来我们讨论A，发现最多只会改动2n个位置，于是可以DP。最关键的问题是转移的时候，给定两个长度为m的数a和b，以及改动次数x，求一个最小的c，使得c>=a且b与c的不同位数不能超过x，要求在O(m)内完成。我刚开始想了一种贪心，但是获得了WA，修改了数次再次提交还是WA。期间shb想出了J是网络流，并在我打印代码查错时上机写。之后他写完了然而也获得了WA。于是我们决定我给他看J题代码，他给我出A的数据测。我发现他的J题网络流抄模板时少了一行，然而他改了之后仍然获得WA，他也没有能造出使我A题程序挂掉的数据。此时大约3.5h多一点，jsb学长回来了，给我指出了一种比较科学的DP解决A题的那个转移时的子问题，我改了之后终于通过A题。然后shb的J题我再次从头到尾看代码，同时jsb学长完全重写，还没重写完时，我发现shb主程序中一个的错误，i写成了q[i]，于是修改后通过了J题。之后我们大概讨论出了B的做法，然而只有20min了并没有写完。

总结：以后写题前最好要考虑做法的正确性，避免出现我一开场J的占用了宝贵的机时写了错误的贪心，还造成一次罚时。其实我和JSB学长相对比较擅长网络流，都不需要模板就能默写出来。不过当时我已经A题写了一半了，所以只能让shb去写J。不过我没有早一点就看出来J是网络流，这点值得检讨。

== shb ==
流水帐：前期签到，因为今天少人的缘故所以看题想题比较慢，签到速度一般。不过开场不久sm学长觉得J是简单贪心，虽然不确定对不对还是上来写了很久，浪费了一些读题的时间，而且也没有通过。CEFHI都比较顺利，做完的时候是106min。因为只有两个人，我们讨论之后决定双开一波，sm学长来写A，我继续去想J。但是A有一些比较麻烦的边界情况（按我们的DP方程），转移的时候要通过一个子问题的贪心，所以调了很久。这段时间我觉得J是个网络流，想了个错误的建图就让学长纸上调试，我上去写了，结果写完segment fault，后来学长发现是我模板抄错。之后又发现建图有点小问题，改了以后还是一直WA，直到最后才发现是我建图的地方写错了一个字符。感觉我的锅非常之大。。还剩一个半小时的时候jsb回来了，用DP解决了子问题，跟sm学长一起过了A，然后感受了一波J的网络流感觉也是对的，于是决定他来重写一波，我和sm学长来看代码。结果他写到一般的时候sm学长发现了我写错的地方，改掉就过了。只剩20分钟，决定让我来写B，他们俩在旁边帮我看，不过因为时间问题还没有写完，十分遗憾。。

总结：
1、感觉前期还是不要开没把握的题，简单题最好还是跟一下榜，不然可能浪费时间还影响心态。

2、我可能需要提高一波debug。。连着两天都是小地方的错误改了很久，花费了很多时间。

3、互相看代码的时候一定要细致，如果只是随便看看基本上没什么作用。

4、事实上感觉今天双开的节奏还可以（虽然写的有点炸），之后人齐的时候应该还是保持一下双开到单开？


== JSB ==
流水账：
今天去竺考了，吃完饭才回机房，所以到的时候只有一个多小时了。和lsmll学长讨论了一发过了A,然后我就进入零贡献状态。堡学长花了些时间和我讲了J题的题意和它的代码，然而我就是一条debug咸鱼，根本看不出哪里有错。最后我们决定我先完全重写，学长们继续肉眼调试。快写完时lsmll发现一处神奇的错误，改了改就过了。在机位上的我感觉很尴尬>_<后来我们会了B，可惜20min没rush出。

总结：

1.还是要多提高姿势水平，多练习肉眼debug大法（以前高中我都是dev单步调试感觉好羞耻），因为这对自己和队友都有益。

2.还是要多提高姿势水平，多练习清楚的思路，并提高手速和正确性（咦我好想在说废话），这样才能为光速rush提供可能。

== 补题 ==
B[shb]
按题目描述，不存在size>5的强连通分量。因此缩点后，爆搜算出每个SCC内部两两之间的最长路，再将每个点拆成出点和入点，构成DAG后DP即可。

D[lsmll]

G[]

K[]

注：今日由于jsb学长参加竺院选拔考，比赛的前3.5h只有lsmll和shb两个人参赛。

lsmll

流水账：还是倒着看，K是计算几何，于是就跳过了。看了J，想了一个贪心做法，于是等shb写完签到题C之后去写了，结果获得WA，后来仔细一想感觉贪心是不太靠谱，于是暂时搁置J题。看榜(combined，下同)发现H题、F题过的人较多，我看了H题发现只要递归求每个数在Grey Code中的位置然后减一下就行，于是在shb过了E题后就去写了，刚开始算术左移的地方(1<=a且b与c的不同位数不能超过x，要求在O(m)内完成。我刚开始想了一种贪心，但是获得了WA，修改了数次再次提交还是WA。期间shb想出了J是网络流，并在我打印代码查错时上机写。之后他写完了然而也获得了WA。于是我们决定我给他看J题代码，他给我出A的数据测。我发现他的J题网络流抄模板时少了一行，然而他改了之后仍然获得WA，他也没有能造出使我A题程序挂掉的数据。此时大约3.5h多一点，jsb学长回来了，给我指出了一种比较科学的DP解决A题的那个转移时的子问题，我改了之后终于通过A题。然后shb的J题我再次从头到尾看代码，同时jsb学长完全重写，还没重写完时，我发现shb主程序中一个的错误，i写成了q[i]，于是修改后通过了J题。之后我们大概讨论出了B的做法，然而只有20min了并没有写完。

总结：以后写题前最好要考虑做法的正确性，避免出现我一开场J的占用了宝贵的机时写了错误的贪心，还造成一次罚时。其实我和JSB学长相对比较擅长网络流，都不需要模板就能默写出来。不过当时我已经A题写了一半了，所以只能让shb去写J。不过我没有早一点就看出来J是网络流，这点值得检讨。

shb

流水帐：前期签到，因为今天少人的缘故所以看题想题比较慢，签到速度一般。不过开场不久sm学长觉得J是简单贪心，虽然不确定对不对还是上来写了很久，浪费了一些读题的时间，而且也没有通过。CEFHI都比较顺利，做完的时候是106min。因为只有两个人，我们讨论之后决定双开一波，sm学长来写A，我继续去想J。但是A有一些比较麻烦的边界情况（按我们的DP方程），转移的时候要通过一个子问题的贪心，所以调了很久。这段时间我觉得J是个网络流，想了个错误的建图就让学长纸上调试，我上去写了，结果写完segment fault，后来学长发现是我模板抄错。之后又发现建图有点小问题，改了以后还是一直WA，直到最后才发现是我建图的地方写错了一个字符。感觉我的锅非常之大。。还剩一个半小时的时候jsb回来了，用DP解决了子问题，跟sm学长一起过了A，然后感受了一波J的网络流感觉也是对的，于是决定他来重写一波，我和sm学长来看代码。结果他写到一般的时候sm学长发现了我写错的地方，改掉就过了。只剩20分钟，决定让我来写B，他们俩在旁边帮我看，不过因为时间问题还没有写完，十分遗憾。。

总结：

1、感觉前期还是不要开没把握的题，简单题最好还是跟一下榜，不然可能浪费时间还影响心态。

2、我可能需要提高一波debug。。连着两天都是小地方的错误改了很久，花费了很多时间。

3、互相看代码的时候一定要细致，如果只是随便看看基本上没什么作用。

4、事实上感觉今天双开的节奏还可以（虽然写的有点炸），之后人齐的时候应该还是保持一下双开到单开？

JSB

流水账：

今天去竺考了，吃完饭才回机房，所以到的时候只有一个多小时了。和lsmll学长讨论了一发过了A,然后我就进入零贡献状态。堡学长花了些时间和我讲了J题的题意和它的代码，然而我就是一条debug咸鱼，根本看不出哪里有错。最后我们决定我先完全重写，学长们继续肉眼调试。快写完时lsmll发现一处神奇的错误，改了改就过了。在机位上的我感觉很尴尬>_<后来我们会了B，可惜20min没rush出。

总结：

1.还是要多提高姿势水平，多练习肉眼debug大法（以前高中我都是dev单步调试感觉好羞耻），因为这对自己和队友都有益。

2.还是要多提高姿势水平，多练习清楚的思路，并提高手速和正确性（咦我好想在说废话），这样才能为光速rush提供可能。

补题

B[shb]

按题目描述，不存在size>5的强连通分量。因此缩点后，爆搜算出每个SCC内部两两之间的最长路，再将每个点拆成出点和入点，构成DAG后DP即可。

D[lsmll]

G[]

K[]

附加文件