2016-E02-team2

从 Trac 迁移的文章

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

原文章内容如下：

||#||When||Who||Problem||Lang||Verdict||Time||Memory||
||19514285||2016-07-30 17:05:59||TaZoF||F - Best of a bad lot||GNU C||Wrong answer on test 3||0 ms||2800 KB||
||19514163||2016-07-30 17:00:34||TaZoF||F - Best of a bad lot||GNU C||Wrong answer on test 3||0 ms||2800 KB||
||19513932||2016-07-30 16:51:46||TaZoF||F - Best of a bad lot||GNU C++11||Wrong answer on test 3||15 ms||200 KB||
||19513386||2016-07-30 16:27:17||TaZoF||F - Best of a bad lot||GNU C++11||Wrong answer on test 3||0 ms||200 KB||
||19512431||2016-07-30 15:44:52||TaZoF||J - Scarily interesting!||GNU C++11||Accepted||31 ms||0 KB||
||19512021||2016-07-30 15:27:50||TaZoF||C - Zhenya moves from parents||GNU C||Accepted||171 ms||33600 KB||
||19511126||2016-07-30 14:46:27||TaZoF||J - Scarily interesting!||GNU C++11||Wrong answer on test 8||15 ms||0 KB||
||19510909||2016-07-30 14:37:27||TaZoF||J - Scarily interesting!||GNU C++11||Wrong answer on test 17||15 ms||0 KB||
||19510585||2016-07-30 14:19:44||TaZoF||J - Scarily interesting!||GNU C++11||Wrong answer on test 16||15 ms||0 KB||
||19510552||2016-07-30 14:18:11||TaZoF||J - Scarily interesting!||GNU C++11||Runtime error on test 10||15 ms||0 KB||
||19510403||2016-07-30 14:10:28||TaZoF||H - Pair: normal and paranormal||GNU C||Accepted||30 ms||100 KB||
||19510341||2016-07-30 14:06:54||TaZoF||J - Scarily interesting!||GNU C++11||Wrong answer on test 16||15 ms||0 KB||
||19509325||2016-07-30 13:08:39||TaZoF||D - Zhenya moves from the dormitory||GNU C||Accepted||15 ms||0 KB||
||19509216||2016-07-30 13:02:22||TaZoF||D - Zhenya moves from the dormitory||GNU C||Wrong answer on test 5||15 ms||0 KB||
||19509123||2016-07-30 12:55:35||TaZoF||I - Traffic Jam in Flower Town||GNU C++11||Accepted||31 ms||0 KB||
||19508940||2016-07-30 12:41:14||TaZoF||G - The Debut Album||GNU C++11||Accepted||124 ms||800 KB||
||19508856||2016-07-30 12:36:18||TaZoF||L - Donald is a postman||GNU C++11||Accepted||15 ms||0 KB||
||19508554||2016-07-30 12:12:47||TaZoF||A - About Grisha N.||GNU C||Accepted||15 ms||0 KB||

比赛链接: http://www.codeforces.com/gym/100507

== 流水账 ==

=== TsReaper ===
练习开始的时候vjudge不知道为什么上不去了，只能在gym里再开一场一样的...

和之前一样，我读ABCD，Starve学长EFGH，hzf学长IJKL。A题仍然是签到题，'''A1y2'''。B题是一道题意非常奇怪的题目，暂时跳过。C题貌似是什么数据结构或者分治，一下子想不到思路。Starve学长发现G题是简单题，不过一开始我们把题目中的in a row理解错了，浪费了一点时间~~感觉真是对不起大英老师~~。此时hzf学长发现了L是简单题，确认了一下题意之后'''L1y26'''，不久Starve学长也做好了G，'''G1y31'''。

在学长们写题的过程中我也看到了简单题D题，不过有一些细节没有考虑好。正好hzf学长要写I，就让学长先上机了，'''I1y45'''。稍微考虑了一下D题的写法之后我也开始写D，但是因为弄错了一个题意WA了一次，'''D2y58'''，~~感觉这场练习有着浓浓的阅读理解气氛~~。

练习前期还算顺利，刷了一下ranklist我们决定考虑J。一开始我们想用二分答案+多物品背包的方式，但是输出方案非常麻烦。Starve学长想了某种贪心，虽然觉得比较奇怪，但是机器空着也不好，就让学长先试一下（感觉变成了上一场的节奏...），可惜并没有答对。Starve学长写J的时候我和hzf学长考虑H。一开始我们猜想是区间dp，不过是O(n^3^)的，之后又考虑了一个O(n^2^)的消除法。好在~~正在debug的~~Starve学长发现了这道题和括号序列的某种联系，hzf学长也指出了做法，我就上机写H。~~因为CF太卡用手机交题~~，'''H1y120'''。

之后Starve学长继续调J，我和hzf学长也根据ranklist决定想一想C。我对C题不太有思路，好在hzf学长发现了重要结论：答案就是某个前缀和。经过一番思考我们发现C题其实只需要维护最小前缀和即可，~~因为怕线段树写错~~我就把写题的锅甩给了hzf学长，自己思考B题。hzf学长写C期间Starve学长上机修改了若干代码，都没有通过J...C题写好以后似乎并不能通过样例，我觉得可能不应该让hzf学长接锅，还是自己写了线段树，'''C1y197'''。简单抉择之后我们决定先把J想好，再去看奇怪的B题。很快Starve学长想到了更为科学的贪心，'''J6y214'''。

看了一下ranklist发现有队伍通过了F题，鉴于B题题意太奇怪，我们决定尝试F题。因为n <= 400，我们猜想会不会是网络流。仔细读题后发现题目中给的图是二分图，为我们的猜想增添了~~迷之~~自信。我们想通过二分图的最大独立点集得到诚实的人，这样剩下的人就是说谎的了，感觉非常科学。Starve学长就上机写二分图匹配，结果在第三个点就WA了...看看时间还有大概40分钟，我决定重写一下F，~~结果样例都没有过~~。我们发现了输出方案中存在的问题，又猜想会不会是黑白染色，然而不管怎么改都在第三个点WA了，最后都没有调出来，难过地结束了练习...~~赛后发现F题又弄错了一个题意~~

=== hzf  ===
我还是从后往前读题，IJKL，可能受了上一场的影响，我竟然把K当成最后一题了，先读了K，而且竟然还觉得可做..~~赛后发现没人A这题~~幸好及时跳出了坑看了L，大水题，'''L1y26'''，然后学长们说I题过了好多人，我就跳过了J直接去看I，也很水，'''I1y45'''，然后想了一会儿J，tsr学长说的多重背包二进制拆分的做法我到现在还是不会，惨，而且编程复杂度也过高...而J的贪心也一直没过，从这以后我们就卡了好久题...

tar学长拉我一起看C和H，H starve学长发现是个括号序列，tsr很快就写出来了，然后我和tsr学长讨论了一下C题的性质...然后就转化成了线段树...喔然后我~~不自量力地~~上去写线段树，tsr学长和starve学长讨论J的问题在哪里，...过了好久我还是写不出来，tsr学长看不下去了替了我写了5min就写出来啦...强！~~感觉自己迟早只能嗑瓜子~~starve学长很快yy出了一个更加合理的贪心，过了J。

最后大家一起开始想F。先从网络流开始想，然后发现它是个二分图...于是就开始套各种模版...本来想用最大独立集的...结果赛后证明这是错的...因为这题要求独立集的补集里也不能有边阿！所以这题实际上就是二分图染色阿...~~不听tsr学长的教导我果然又错了~~

=== 3z ===
已经没什么好说的了。。

== 总结 ==

=== TsReaper ===

 * 再也不要读错题啦！！！
 * 感觉hzf学长的思维很好，想到了很多题的关键结论，是不是更适合思维...？写代码的锅可能还是要自己接，不过自己写代码不够持久，还是多写吧...
 * 我们三个的基本功还是太差了，其实这一场想要做10题应该不是难事，J和F分别卡住非常不应该。
 * 还是心态吧...虽然是竞争性很强的项目，但是做好自己就可以了，不要想着超过谁。感觉自己对待ACM的态度和一开始预想的偏差有点大...

=== hzf ===

 * 要不然提高自己的码力，要不然只能可耻地甩锅啦
 * 可能要更熟悉各种np问题的意义还有它们在二分图下的特殊解法？这样就不会套错啦...

=== 3z ===
 * 果然我的英语太差，F题没过都是我的锅，B题也完全没有读懂
 * 感觉我的策略有问题吧，即使电脑空闲也不能随便就写一个看起来正确率不超过一成的贪心
 * 基本功太差，遇见一些模板题还是不能立刻就想出解法
 * 姿势还是不过多啊。。

== 题解 ==
ADGIL是简单题，略过...

=== J ===
其实是一个很明显的贪心。。一开始没想到
我们发现如果i位置能让观众留下，那么对于所有i之前的位置多可以让观众留下，而且和顺序没有关系。
于是我们反着想，如果第一组的惊吓和大于第二组的惊吓和，我们想让观众留的时间尽量长的话，最后一场放第一组的最大值，第二组的最小值。这样会让倒数第二场的两组惊吓和的差缩小，这是我们想看到的。
于是算法很明显了，惊吓和大的那一组升序输出，另一组降序输出就好了。。

== 补题 ==

=== TsReaper ===

B, E, ~~F~~, K
=== 3z ===

K
#WhenWhoProblemLangVerdictTimeMemory
195142852016-07-30 17:05:59TaZoFF - Best of a bad lotGNU CWrong answer on test 30 ms2800 KB
195141632016-07-30 17:00:34TaZoFF - Best of a bad lotGNU CWrong answer on test 30 ms2800 KB
195139322016-07-30 16:51:46TaZoFF - Best of a bad lotGNU C++11Wrong answer on test 315 ms200 KB
195133862016-07-30 16:27:17TaZoFF - Best of a bad lotGNU C++11Wrong answer on test 30 ms200 KB
195124312016-07-30 15:44:52TaZoFJ - Scarily interesting!GNU C++11Accepted31 ms0 KB
195120212016-07-30 15:27:50TaZoFC - Zhenya moves from parentsGNU CAccepted171 ms33600 KB
195111262016-07-30 14:46:27TaZoFJ - Scarily interesting!GNU C++11Wrong answer on test 815 ms0 KB
195109092016-07-30 14:37:27TaZoFJ - Scarily interesting!GNU C++11Wrong answer on test 1715 ms0 KB
195105852016-07-30 14:19:44TaZoFJ - Scarily interesting!GNU C++11Wrong answer on test 1615 ms0 KB
195105522016-07-30 14:18:11TaZoFJ - Scarily interesting!GNU C++11Runtime error on test 1015 ms0 KB
195104032016-07-30 14:10:28TaZoFH - Pair: normal and paranormalGNU CAccepted30 ms100 KB
195103412016-07-30 14:06:54TaZoFJ - Scarily interesting!GNU C++11Wrong answer on test 1615 ms0 KB
195093252016-07-30 13:08:39TaZoFD - Zhenya moves from the dormitoryGNU CAccepted15 ms0 KB
195092162016-07-30 13:02:22TaZoFD - Zhenya moves from the dormitoryGNU CWrong answer on test 515 ms0 KB
195091232016-07-30 12:55:35TaZoFI - Traffic Jam in Flower TownGNU C++11Accepted31 ms0 KB
195089402016-07-30 12:41:14TaZoFG - The Debut AlbumGNU C++11Accepted124 ms800 KB
195088562016-07-30 12:36:18TaZoFL - Donald is a postmanGNU C++11Accepted15 ms0 KB
195085542016-07-30 12:12:47TaZoFA - About Grisha N.GNU CAccepted15 ms0 KB

比赛链接: http://www.codeforces.com/gym/100507

流水账

TsReaper

练习开始的时候vjudge不知道为什么上不去了，只能在gym里再开一场一样的...

和之前一样，我读ABCD，Starve学长EFGH，hzf学长IJKL。A题仍然是签到题，A1y2。B题是一道题意非常奇怪的题目，暂时跳过。C题貌似是什么数据结构或者分治，一下子想不到思路。Starve学长发现G题是简单题，不过一开始我们把题目中的in a row理解错了，浪费了一点时间感觉真是对不起大英老师。此时hzf学长发现了L是简单题，确认了一下题意之后L1y26，不久Starve学长也做好了G，G1y31。

在学长们写题的过程中我也看到了简单题D题，不过有一些细节没有考虑好。正好hzf学长要写I，就让学长先上机了，I1y45。稍微考虑了一下D题的写法之后我也开始写D，但是因为弄错了一个题意WA了一次，D2y58，感觉这场练习有着浓浓的阅读理解气氛。

练习前期还算顺利，刷了一下ranklist我们决定考虑J。一开始我们想用二分答案+多物品背包的方式，但是输出方案非常麻烦。Starve学长想了某种贪心，虽然觉得比较奇怪，但是机器空着也不好，就让学长先试一下（感觉变成了上一场的节奏...），可惜并没有答对。Starve学长写J的时候我和hzf学长考虑H。一开始我们猜想是区间dp，不过是O(n3)的，之后又考虑了一个O(n2)的消除法。好在正在debug的Starve学长发现了这道题和括号序列的某种联系，hzf学长也指出了做法，我就上机写H。因为CF太卡用手机交题，H1y120。

之后Starve学长继续调J，我和hzf学长也根据ranklist决定想一想C。我对C题不太有思路，好在hzf学长发现了重要结论：答案就是某个前缀和。经过一番思考我们发现C题其实只需要维护最小前缀和即可，因为怕线段树写错我就把写题的锅甩给了hzf学长，自己思考B题。hzf学长写C期间Starve学长上机修改了若干代码，都没有通过J...C题写好以后似乎并不能通过样例，我觉得可能不应该让hzf学长接锅，还是自己写了线段树，C1y197。简单抉择之后我们决定先把J想好，再去看奇怪的B题。很快Starve学长想到了更为科学的贪心，J6y214。

看了一下ranklist发现有队伍通过了F题，鉴于B题题意太奇怪，我们决定尝试F题。因为n <= 400，我们猜想会不会是网络流。仔细读题后发现题目中给的图是二分图，为我们的猜想增添了迷之自信。我们想通过二分图的最大独立点集得到诚实的人，这样剩下的人就是说谎的了，感觉非常科学。Starve学长就上机写二分图匹配，结果在第三个点就WA了...看看时间还有大概40分钟，我决定重写一下F，结果样例都没有过。我们发现了输出方案中存在的问题，又猜想会不会是黑白染色，然而不管怎么改都在第三个点WA了，最后都没有调出来，难过地结束了练习...赛后发现F题又弄错了一个题意

hzf

我还是从后往前读题，IJKL，可能受了上一场的影响，我竟然把K当成最后一题了，先读了K，而且竟然还觉得可做..赛后发现没人A这题幸好及时跳出了坑看了L，大水题，L1y26，然后学长们说I题过了好多人，我就跳过了J直接去看I，也很水，I1y45，然后想了一会儿J，tsr学长说的多重背包二进制拆分的做法我到现在还是不会，惨，而且编程复杂度也过高...而J的贪心也一直没过，从这以后我们就卡了好久题...

tar学长拉我一起看C和H，H starve学长发现是个括号序列，tsr很快就写出来了，然后我和tsr学长讨论了一下C题的性质...然后就转化成了线段树...喔然后我不自量力地上去写线段树，tsr学长和starve学长讨论J的问题在哪里，...过了好久我还是写不出来，tsr学长看不下去了替了我写了5min就写出来啦...强！感觉自己迟早只能嗑瓜子starve学长很快yy出了一个更加合理的贪心，过了J。

最后大家一起开始想F。先从网络流开始想，然后发现它是个二分图...于是就开始套各种模版...本来想用最大独立集的...结果赛后证明这是错的...因为这题要求独立集的补集里也不能有边阿！所以这题实际上就是二分图染色阿...不听tsr学长的教导我果然又错了

3z

已经没什么好说的了。。

总结

TsReaper

  • 再也不要读错题啦！！！
  • 感觉hzf学长的思维很好，想到了很多题的关键结论，是不是更适合思维...？写代码的锅可能还是要自己接，不过自己写代码不够持久，还是多写吧...
  • 我们三个的基本功还是太差了，其实这一场想要做10题应该不是难事，J和F分别卡住非常不应该。
  • 还是心态吧...虽然是竞争性很强的项目，但是做好自己就可以了，不要想着超过谁。感觉自己对待ACM的态度和一开始预想的偏差有点大...

hzf

  • 要不然提高自己的码力，要不然只能可耻地甩锅啦
  • 可能要更熟悉各种np问题的意义还有它们在二分图下的特殊解法？这样就不会套错啦...

3z

  • 果然我的英语太差，F题没过都是我的锅，B题也完全没有读懂
  • 感觉我的策略有问题吧，即使电脑空闲也不能随便就写一个看起来正确率不超过一成的贪心
  • 基本功太差，遇见一些模板题还是不能立刻就想出解法
  • 姿势还是不过多啊。。

题解

ADGIL是简单题，略过...

J

其实是一个很明显的贪心。。一开始没想到

我们发现如果i位置能让观众留下，那么对于所有i之前的位置多可以让观众留下，而且和顺序没有关系。

于是我们反着想，如果第一组的惊吓和大于第二组的惊吓和，我们想让观众留的时间尽量长的话，最后一场放第一组的最大值，第二组的最小值。这样会让倒数第二场的两组惊吓和的差缩小，这是我们想看到的。

于是算法很明显了，惊吓和大的那一组升序输出，另一组降序输出就好了。。

补题

TsReaper

B, E, F, K

3z

K