2017-Sp174-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门sub读了J告诉yzc，yzc上机搞了一下，'''J1y24'''。cjb上机写E，疯狂wa，之后不想调了改成贪心，'''E1y80'''。sub和yzc搞了C，wa了之后不知道咋办，cjb上机写F，最后终于发现有corner case，'''C2y132'''。cjb继续写F，'''F1y143'''。yzc写G，wa了之后发现算法问题，cjb想了稳妥做法，复杂度有点不对，上机'''G2y212'''。之后三个人一起讨论H，最后得到做法yzc上机'''H4y251'''。cjb和sub决定大力上I，'''I2y285'''。
== 总结 ==
=== chenjb ===
感觉NAIPC有点像wf，算法没那么有脑子，但是要能上敢上。。。多练NAIPC，幸福你我他。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：

 * B：

 * C：枚举之后贪心暴力，注意一行或一列的情况。

 * D：sub

 * E：二分答案，贪心，每次尽可能取长的一段来判定。

 * F：先把所有人的下界填完，显然这个时候我们可以不让此时最高的人再添加任何沙子，则二分差值，然后网络流判定每个人是否能满流maxh-limit-h[i]的流即可。

 * G：长度必须是n的因子，且枚举的串字母数和总串各字母数必须对应成倍数，判定此点后，可以用f[i][j]表示[i,j]区间是否能由原串扩展，则用f[i][j-k*len]&f[j-k*len+1][j]去转移，或者f[i][j-1]为true且第j个字母为对应字母，判定复杂度感觉是4.5次方的，然后跑得很快，thewaysofar说是3.5的。

 * H：每个点保留别人对他的最大和次大贡献，所有人沿着最大贡献走，如果是链则直接加入答案，否则枚举哪一个人取次大值更新答案，预处理的时候把正收益的点都吃到只剩1个。

 * I：算出终点，往回推30000步就结束。

 * J：按位枚举。

 * [https://www.cnblogs.com/clrs97/p/8025819.html Claris]
 * [https://wiki.icpc.camp/twsf/XV%20Open%20Cup%20named%20after%20E.V.%20Pankratiev.%20GP%20of%20America TheWaySoFar]

流水账

出门sub读了J告诉yzc，yzc上机搞了一下，J1y24。cjb上机写E，疯狂wa，之后不想调了改成贪心，E1y80。sub和yzc搞了C，wa了之后不知道咋办，cjb上机写F，最后终于发现有corner case，C2y132。cjb继续写F，F1y143。yzc写G，wa了之后发现算法问题，cjb想了稳妥做法，复杂度有点不对，上机G2y212。之后三个人一起讨论H，最后得到做法yzc上机H4y251。cjb和sub决定大力上I，I2y285。

总结

chenjb

感觉NAIPC有点像wf，算法没那么有脑子，但是要能上敢上。。。多练NAIPC，幸福你我他。

oipotato

subconscious

题解

• A：
• B：
• C：枚举之后贪心暴力，注意一行或一列的情况。
• D：sub
• E：二分答案，贪心，每次尽可能取长的一段来判定。
• F：先把所有人的下界填完，显然这个时候我们可以不让此时最高的人再添加任何沙子，则二分差值，然后网络流判定每个人是否能满流maxh-limit-h[i]的流即可。
• G：长度必须是n的因子，且枚举的串字母数和总串各字母数必须对应成倍数，判定此点后，可以用f[i][j]表示[i,j]区间是否能由原串扩展，则用f[i][j-k*len]&f[j-k*len+1][j]去转移，或者f[i][j-1]为true且第j个字母为对应字母，判定复杂度感觉是4.5次方的，然后跑得很快，thewaysofar说是3.5的。
• H：每个点保留别人对他的最大和次大贡献，所有人沿着最大贡献走，如果是链则直接加入答案，否则枚举哪一个人取次大值更新答案，预处理的时候把正收益的点都吃到只剩1个。
• I：算出终点，往回推30000步就结束。
• J：按位枚举。
• Claris
• TheWaySoFar

附加文件

• 1.png by chenjb