2017-C08-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(day8board.png)]]
== 流水账 ==
开场sub从A开始看，yzc改从D开始看，cjb从J开始看. 过了一会儿，三人都没有发现签到题，此时看board，'''Cls'''已经光速过了G，赶忙去看G，小小讨论了一会儿后就想到做法，yzc上机'''G1y16'''. 此时看board，毛子过了D，sub表示不大会做，但三人脑洞了一下就提出了贪心的思路，yzc继续上机'''D1y43'''. sub和cjb讨论出了几何题J的做法，sub上机打了很久，但是始终过不了cjb手出的数据.期间cjb和yzc讨论了剩下的题，尝试开坑，考虑H的时候，想到了思路，在sub调试无果的时候yzc换下sub开始写H, 2小时的时候wa了一发，打印调试后找到了错误，'''H2y134'''. cjb和sub得到了感觉很靠谱的C的做法，cjb上机写C，sub继续思考J，. cjb很快写完之后，编译过后过不了样例，马上换上sub继续写J，sub换了做法，终于通过了手出的数据，最后'''J1y180'''. cjb上机继续调C，过了样例，三个半小时的时候wa了第一发. yzc和sub开出了E,yzc上机写E，不到二十分钟写完之后过样例，提交喜获MLE. 三人一阵乱搞，继续MLE，三脸懵逼. cjb继续完善C，套了个树链剖分，感觉非常科学，四小时初交了还是wa，cjb直接爆粗.....yzc继续“冷静”地研究E，终于发现了非常牛逼的错误，在又拿了两发MLE后终于得到了一发TLE，后来致力于调常数，依然TLE,最后又调了一次常数，过了, '''E8y267'''. 看了下榜，发现无人开C，cjb心情复杂，三人开始千方百计构造数据卡cjb的C，无果，甚至assert了数据范围，还是构造不出能卡cjb的数据，只好欢声笑语打出GG，封榜后感觉一队过了A，瞬间爆炸. 比赛最后5分钟甚至不能提交，最后重回老二，cjb成为建队以来第一个在整场比赛中没有输出的人QAQ.....另外祝贺'''sub'''成功报道，正式成为我校学生.
== 总结 ==
=== chenjb ===
可以说是非常难受了，今天没有输出....这个C是咋回事儿啊怎么大家都卡不掉我程序啊QAQ 怎么就wa 3了呀....菜菜啊.....确实今天可能是我们队整体配合最少的一天，感觉有些罚时大家还是不太冷静，平时要多练习，三人先把自己的题刷完呗~
=== oipotato ===
今天感觉整体配合比较少，除了和sub一起讨论出E的做法，其他感觉都是一个人提出的算法就差不多是正解了。感觉最近打代码不是很稳，今天的E更是打出了建队以来最高罚时，而且最后看看还都是毫无意义的提交，比赛的时候还是要冷静，平时还是要多练。
=== subconscious  ===
今天前期配合不足，又出现了不断交流题意的情况，中期卡题，计算几何卡了好久，后期乏力，主要是C题感觉是可做题所以刚到了结尾却没有刚出来，还是需要多加考虑再去开题.
== 题解 ==
 * A:
    * 题意：n只猪玩老虎机，这个老虎机的输赢序列是周期性的，所有猪排队轮流玩老虎机，赢了赚一块，输了亏一块。每只猪有一个初始钱数，如果有只猪把钱输完了，就带着所有猪一起走了。现在猪老板想知道这些猪走的时候会带走多少钱。可是由于猪老板有数不尽的钱，所以如果这些猪一直没把钱输光的话，他们就会一直玩下去，此时你应该输出-1.
    * 题解：倍增出从周期中某位置开始，做2^i^轮的钱的变化，然后算出每只猪最早什么时候没钱，取最小的即可。
 * B:
    * 题意：染色，颜色1-k，每种颜色不少于2次，相邻不同色。题目还会给出一种满足颜色属于1-k的和一种满足不少于2次的。
    * 题解：选择第一种方案中颜色唯一的点，选取第二种方案中与其同色的点，染为同色。复杂度O(n)。
== 补题 ==
 * ~~A~~ by yzc
 * ~~B~~ by yzc
 * C
 * F
 * I

流水账

开场sub从A开始看，yzc改从D开始看，cjb从J开始看. 过了一会儿，三人都没有发现签到题，此时看board，Cls已经光速过了G，赶忙去看G，小小讨论了一会儿后就想到做法，yzc上机G1y16. 此时看board，毛子过了D，sub表示不大会做，但三人脑洞了一下就提出了贪心的思路，yzc继续上机D1y43. sub和cjb讨论出了几何题J的做法，sub上机打了很久，但是始终过不了cjb手出的数据.期间cjb和yzc讨论了剩下的题，尝试开坑，考虑H的时候，想到了思路，在sub调试无果的时候yzc换下sub开始写H, 2小时的时候wa了一发，打印调试后找到了错误，H2y134. cjb和sub得到了感觉很靠谱的C的做法，cjb上机写C，sub继续思考J，. cjb很快写完之后，编译过后过不了样例，马上换上sub继续写J，sub换了做法，终于通过了手出的数据，最后J1y180. cjb上机继续调C，过了样例，三个半小时的时候wa了第一发. yzc和sub开出了E,yzc上机写E，不到二十分钟写完之后过样例，提交喜获MLE. 三人一阵乱搞，继续MLE，三脸懵逼. cjb继续完善C，套了个树链剖分，感觉非常科学，四小时初交了还是wa，cjb直接爆粗.....yzc继续“冷静”地研究E，终于发现了非常牛逼的错误，在又拿了两发MLE后终于得到了一发TLE，后来致力于调常数，依然TLE,最后又调了一次常数，过了, E8y267. 看了下榜，发现无人开C，cjb心情复杂，三人开始千方百计构造数据卡cjb的C，无果，甚至assert了数据范围，还是构造不出能卡cjb的数据，只好欢声笑语打出GG，封榜后感觉一队过了A，瞬间爆炸. 比赛最后5分钟甚至不能提交，最后重回老二，cjb成为建队以来第一个在整场比赛中没有输出的人QAQ.....另外祝贺sub成功报道，正式成为我校学生.

总结

chenjb

可以说是非常难受了，今天没有输出....这个C是咋回事儿啊怎么大家都卡不掉我程序啊QAQ 怎么就wa 3了呀....菜菜啊.....确实今天可能是我们队整体配合最少的一天，感觉有些罚时大家还是不太冷静，平时要多练习，三人先把自己的题刷完呗~

oipotato

今天感觉整体配合比较少，除了和sub一起讨论出E的做法，其他感觉都是一个人提出的算法就差不多是正解了。感觉最近打代码不是很稳，今天的E更是打出了建队以来最高罚时，而且最后看看还都是毫无意义的提交，比赛的时候还是要冷静，平时还是要多练。

subconscious

今天前期配合不足，又出现了不断交流题意的情况，中期卡题，计算几何卡了好久，后期乏力，主要是C题感觉是可做题所以刚到了结尾却没有刚出来，还是需要多加考虑再去开题.

题解

• A:
  • 题意：n只猪玩老虎机，这个老虎机的输赢序列是周期性的，所有猪排队轮流玩老虎机，赢了赚一块，输了亏一块。每只猪有一个初始钱数，如果有只猪把钱输完了，就带着所有猪一起走了。现在猪老板想知道这些猪走的时候会带走多少钱。可是由于猪老板有数不尽的钱，所以如果这些猪一直没把钱输光的话，他们就会一直玩下去，此时你应该输出-1.
  • 题解：倍增出从周期中某位置开始，做2ⁱ轮的钱的变化，然后算出每只猪最早什么时候没钱，取最小的即可。
• B:
  • 题意：染色，颜色1-k，每种颜色不少于2次，相邻不同色。题目还会给出一种满足颜色属于1-k的和一种满足不少于2次的。
  • 题解：选择第一种方案中颜色唯一的点，选取第二种方案中与其同色的点，染为同色。复杂度O(n)。

补题

• A by yzc
• B by yzc
• C
• F
• I

附加文件

• day8board.png by chenjb