2017-C16-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(day17.png)]]

== 流水账 ==
开场yzc从A开始看，cjb从E开始看，shb从L开始看. 很快shb就表示L是个简单的sg函数题，和tsr之前出的几乎一模一样，但是因为怀疑还有更简单的签到题，所以并没有马上去写，大家继续看题。没找到别的题，所以cjb让shb上去写L，'''L1y22'''. 发现board上很多队伍过D，三人开始讨论D，cjb给出了正确的贪心思路，大家脑补了个分割最长链的东西让cjb去写，yzc和shb研究K. cjb写完wa了两发，发现自己打成重儿子剖分了，又改又wa，然后很无奈地换yzc重写，然后yzc写完后'''D4y111'''. 期间shb想好了A的点分治，上机写A，cjb想出了F，和yzc确认了几个细节，在shb下机调试的时候写F，shb wa了2发后通过了A，'''A3y185'''. cjb不久后调出了F，提交之后通过，'''F1y218'''. yzc想出了G，和shb确认了做法后，想让cjb写预处理，cjb表示自己太傻，艰难写起了代码，然后就被yzc赶下了机子，yzc一人重新开G，shb和cjb想别的题，shb和cjb很快口胡通过了I，表示写不完，又回去搞K，最后挣扎到最后搞了个沿切线走的方法，yzc终于写完G，一发入魂，'''G1y290'''. shb赶忙上去写K，并没有成功，最后5题结束了比赛.
== 总结 ==
=== chenjb ===
感觉今天脑回路还行？引领了一波D和F？然后明明做法自己想出来的，tm手贱贡献了D的三发罚时还羞耻地让yzc手写才过QAQ菜得抠脚...还好F没有智障，稳稳当当地过了...这段时间感觉手速还行，但是代码准确度迷之下降了，要提高代码准确度，刷一波CF吧！另外感觉今天最开始的时候我应该指挥堡堡立马去写L，不应该犹豫多一会儿，因为如果有真正简单的签到题是可以通过board看出来的，这也算是一个小小的指挥失误吧.
=== oipotato ===

=== shb  ===
== 题解 ==
 * B
  * 题意：两只猪玩游戏，桌上有N张卡片，每张卡片上有一个数字，猪1在[a,b]中选择一个数字t，猪2在桌上选择恰好K张卡片将数字求和，记为u。猪1希望abs(t-u)越大越好，猪2相反。两只猪都很聪明，求猪1会选择哪个数字t（如果多个选择结果一样，选择最小的），猪2又对应的会选择哪几张卡片。N，K<=600，a，b<=1.8E5。
  * 题解：很直观的一个想法就是枚举t，然后DP出最接近的。由于这个dp可以预处理，于是可以先用bitset优化背包来处理出恰好选K个能达到的和。由于空间的限制，需要采用滚动数组，也就不能得到方案。于是我们每做magic次dp就记录一次当前答案，则只需N/magic*2^magic^的时间就可以把方案枚举出来。显然magic在空间允许的前提下越小越好，当magic<=14时就可以通过此题。此外，K可以取到<=300，因为大于300可以用N-K来dp不选的状态。一个常数优化是，dp到第i件物品时，第二维可以只枚举到i而不是一直枚举到K。

 * [https://wiki.icpc-camp.org/twsf/Petrozavodsk%20Summer-2015.%20JAG%20Spring%202015 TheWaySoFar]
== 补题 ==
 * ~~B~~ by yzc
 * C
 * E
 * H
 * I
 * J
 * ~~K~~ by sub

流水账

开场yzc从A开始看，cjb从E开始看，shb从L开始看. 很快shb就表示L是个简单的sg函数题，和tsr之前出的几乎一模一样，但是因为怀疑还有更简单的签到题，所以并没有马上去写，大家继续看题。没找到别的题，所以cjb让shb上去写L，L1y22. 发现board上很多队伍过D，三人开始讨论D，cjb给出了正确的贪心思路，大家脑补了个分割最长链的东西让cjb去写，yzc和shb研究K. cjb写完wa了两发，发现自己打成重儿子剖分了，又改又wa，然后很无奈地换yzc重写，然后yzc写完后D4y111. 期间shb想好了A的点分治，上机写A，cjb想出了F，和yzc确认了几个细节，在shb下机调试的时候写F，shb wa了2发后通过了A，A3y185. cjb不久后调出了F，提交之后通过，F1y218. yzc想出了G，和shb确认了做法后，想让cjb写预处理，cjb表示自己太傻，艰难写起了代码，然后就被yzc赶下了机子，yzc一人重新开G，shb和cjb想别的题，shb和cjb很快口胡通过了I，表示写不完，又回去搞K，最后挣扎到最后搞了个沿切线走的方法，yzc终于写完G，一发入魂，G1y290. shb赶忙上去写K，并没有成功，最后5题结束了比赛.

总结

chenjb

感觉今天脑回路还行？引领了一波D和F？然后明明做法自己想出来的，tm手贱贡献了D的三发罚时还羞耻地让yzc手写才过QAQ菜得抠脚...还好F没有智障，稳稳当当地过了...这段时间感觉手速还行，但是代码准确度迷之下降了，要提高代码准确度，刷一波CF吧！另外感觉今天最开始的时候我应该指挥堡堡立马去写L，不应该犹豫多一会儿，因为如果有真正简单的签到题是可以通过board看出来的，这也算是一个小小的指挥失误吧.

oipotato

shb

题解

• B
  • 题意：两只猪玩游戏，桌上有N张卡片，每张卡片上有一个数字，猪1在[a,b]中选择一个数字t，猪2在桌上选择恰好K张卡片将数字求和，记为u。猪1希望abs(t-u)越大越好，猪2相反。两只猪都很聪明，求猪1会选择哪个数字t（如果多个选择结果一样，选择最小的），猪2又对应的会选择哪几张卡片。N，K<=600，a，b<=1.8E5。
  • 题解：很直观的一个想法就是枚举t，然后DP出最接近的。由于这个dp可以预处理，于是可以先用bitset优化背包来处理出恰好选K个能达到的和。由于空间的限制，需要采用滚动数组，也就不能得到方案。于是我们每做magic次dp就记录一次当前答案，则只需N/magic*2^magic的时间就可以把方案枚举出来。显然magic在空间允许的前提下越小越好，当magic<=14时就可以通过此题。此外，K可以取到<=300，因为大于300可以用N-K来dp不选的状态。一个常数优化是，dp到第i件物品时，第二维可以只枚举到i而不是一直枚举到K。
• TheWaySoFar

补题

• B by yzc
• C
• E
• H
• I
• J
• K by sub

附加文件

• day17.png by chenjb