2017-Sp104-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，有人光速过B，yzc和cjb读了之后迅速上机写，'''B1y8'''。之后sub开E，推出式子后'''E1y28'''。cjb和yzc讨论C，cjb提出了一个结论，yzc基于这个结论得到了一个check的做法，获得wa。yzc下机检查，cjb上机敲miller-rabin，之后sub上机写H，tle两发后'''H3y73'''。cjb想到了D的思路，让yzc上机写D，wa了之后艹了几发fix了代码，'''D2y112'''。之后让sub上机重写C，'''C2y121'''。cjb上机写和sub讨论出的F，sub和yzc讨论G，中途cjb发现过不了样例，下机思考，yzc上机G获得wa，之后cjb在sub提示下想好了上机也wa，yzc修改代码还是wa，cjb修改精度wa在了更前面，之后cjb突然发现有个地方会爆int，修改后'''F3y183'''。在sub帮助下，yzc改好了G，对拍之后'''G3y192'''。之后三个人讨论A，想到了一个基于单调性的做法，yzc上机获得wa，之后和sub反复对拍仍wa，打算放弃，让sub上机写K，之后yzc想到了一个常数小的log做法，cjb想到了正确的线性做法，sub直接上机'''A3y297'''。最后sub rush K无果。
== 总结 ==
=== chenjb ===
World Finals 2018 Bless All !!!
=== oipotato ===
World Finals 2018 Bless All !!!
=== subconscious  ===
World Finals 2018 Bless All !!!
== 题解 ==
 * A：先建出最大流模型，转化为最小割思考，由最优性可得从小到大排序后，答案为A[1..x]+B[1..y]+(n-x)(m-y)的最小值，令该式子为f(x,y)，f(x,y)和f(x,y+1)作差可得到n-x>B[y]，之后从小到大枚举x，n-x也是单调的，就可以two-pointer了。

 * B：贪心。

 * C：状压dp即可，f[mask]在mask这些月份买了有效的物品下最优解，转移枚举物品即可

 * D：枚举多少个0多少个1在T后面，T中每一个1前面可以有任意数量的0，同理0前面有任意数量的1，组合数计算即可

 * E：对于一张竞赛图，强连通分量数量等于拆分成两个点集使得之间严格有序的数量，枚举子集O(n)统计即可。

 * F：二分答案，先把每个大于limit的段贪心分成小于等于limit，如果操作不足，则令大于limit中最小的段s，除开该段，将limit改为2*limit-s再做一次贪心(因为最长距离为x/2 + y/2，x和y为最长段和非严格次长段)

 * G：根据入度为0的点和一些入度为1的点分类讨论，注意处理一些corner case。

 * H：枚举质因子，可发现最多只有2sqrt(c)个质因子需要判定，求出之后用Miller Rabin大力往下跑下一个质数即可。

 * I：sub

 * J：yzc

 * K：求偏导得最优解形式，暴力枚举轴的顺寻，然后二分初始角度即可。注意卡常。
== 补题 ==

流水账

开场各自看题，有人光速过B，yzc和cjb读了之后迅速上机写，B1y8。之后sub开E，推出式子后E1y28。cjb和yzc讨论C，cjb提出了一个结论，yzc基于这个结论得到了一个check的做法，获得wa。yzc下机检查，cjb上机敲miller-rabin，之后sub上机写H，tle两发后H3y73。cjb想到了D的思路，让yzc上机写D，wa了之后艹了几发fix了代码，D2y112。之后让sub上机重写C，C2y121。cjb上机写和sub讨论出的F，sub和yzc讨论G，中途cjb发现过不了样例，下机思考，yzc上机G获得wa，之后cjb在sub提示下想好了上机也wa，yzc修改代码还是wa，cjb修改精度wa在了更前面，之后cjb突然发现有个地方会爆int，修改后F3y183。在sub帮助下，yzc改好了G，对拍之后G3y192。之后三个人讨论A，想到了一个基于单调性的做法，yzc上机获得wa，之后和sub反复对拍仍wa，打算放弃，让sub上机写K，之后yzc想到了一个常数小的log做法，cjb想到了正确的线性做法，sub直接上机A3y297。最后sub rush K无果。

总结

chenjb

World Finals 2018 Bless All !!!

oipotato

World Finals 2018 Bless All !!!

subconscious

World Finals 2018 Bless All !!!

题解

  • A：先建出最大流模型，转化为最小割思考，由最优性可得从小到大排序后，答案为A[1..x]+B[1..y]+(n-x)(m-y)的最小值，令该式子为f(x,y)，f(x,y)和f(x,y+1)作差可得到n-x>B[y]，之后从小到大枚举x，n-x也是单调的，就可以two-pointer了。
  • B：贪心。
  • C：状压dp即可，f[mask]在mask这些月份买了有效的物品下最优解，转移枚举物品即可
  • D：枚举多少个0多少个1在T后面，T中每一个1前面可以有任意数量的0，同理0前面有任意数量的1，组合数计算即可
  • E：对于一张竞赛图，强连通分量数量等于拆分成两个点集使得之间严格有序的数量，枚举子集O(n)统计即可。
  • F：二分答案，先把每个大于limit的段贪心分成小于等于limit，如果操作不足，则令大于limit中最小的段s，除开该段，将limit改为2*limit-s再做一次贪心(因为最长距离为x/2 + y/2，x和y为最长段和非严格次长段)
  • G：根据入度为0的点和一些入度为1的点分类讨论，注意处理一些corner case。
  • H：枚举质因子，可发现最多只有2sqrt(c)个质因子需要判定，求出之后用Miller Rabin大力往下跑下一个质数即可。
  • I：sub
  • J：yzc
  • K：求偏导得最优解形式，暴力枚举轴的顺寻，然后二分初始角度即可。注意卡常。

补题

附加文件