2017-Sp225-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，yzc读了H丢给sub，然后跟榜读A，感觉复杂度有点过好，迟疑了一下'''A2y30'''。sub上机写B和H，'''B1y35'''，然后继续写H，wa了。cjb此前开了C丢给yzc，'''C2y90'''。sub继续写H，'''H3y108'''。cjb上机写G，'''G1y118'''。yzc深思熟虑后上机写F，'''F2y135'''。sub开了D，'''D2y141'''。cjb和yzc决定写J的搜索，然后疯狂tle。sub插空过了E，'''E1y218'''。之后cjb和yzc暴搜似乎有了一些进展，tle72。sub抽空写了I，'''I1y268'''。最后一起刚J，tle75还是过不了，AK大失败。
== 总结 ==
=== chenjb ===
fuck这个J，又tm暴搜失败了，nmd的lyk。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：根据要求得到上界和下界，按要求输出即可。

 * B：数位dp。

 * C：floyd后直接状压dp

 * D：答案是2^联通块^+是否存在一个大于1的联通块。

 * E：维护翻转后的凸多边形，每次判定角度区间，暴力即可。

 * F：如果是位移符号，后面一定是一个S，或者数码，根据这个来判定，直接模拟即可。

 * G：按p=1和p>1分成两类，sort后把p>1先连成一条链，考虑把p=1插在链上。f[i][j]表示前i段链，处理了前j个叶子节点的最优值，每次预处理出i和前j段连一起的代价，用prioirity_queue维护换出最优值即可，O(nmlogn)。

 * H：第一个圆从左下角到矩阵中心，第二个圆从右上角到矩阵中心，二分所在位置的比例即可。

 * I：可以用每一行从右往左匹配了多少个位置的状态，注意这个状态要保证单调递增，暴力每种状态有哪些转移，状态只有200多个，高斯消元即可。

 * J：暴搜+剪枝。

流水账

出门各自看题，yzc读了H丢给sub，然后跟榜读A，感觉复杂度有点过好，迟疑了一下A2y30。sub上机写B和H，B1y35，然后继续写H，wa了。cjb此前开了C丢给yzc，C2y90。sub继续写H，H3y108。cjb上机写G，G1y118。yzc深思熟虑后上机写F，F2y135。sub开了D，D2y141。cjb和yzc决定写J的搜索，然后疯狂tle。sub插空过了E，E1y218。之后cjb和yzc暴搜似乎有了一些进展，tle72。sub抽空写了I，I1y268。最后一起刚J，tle75还是过不了，AK大失败。

总结

chenjb

fuck这个J，又tm暴搜失败了，nmd的lyk。

oipotato

subconscious

题解

  • A：根据要求得到上界和下界，按要求输出即可。
  • B：数位dp。
  • C：floyd后直接状压dp
  • D：答案是2联通块+是否存在一个大于1的联通块。
  • E：维护翻转后的凸多边形，每次判定角度区间，暴力即可。
  • F：如果是位移符号，后面一定是一个S，或者数码，根据这个来判定，直接模拟即可。
  • G：按p=1和p>1分成两类，sort后把p>1先连成一条链，考虑把p=1插在链上。f[i][j]表示前i段链，处理了前j个叶子节点的最优值，每次预处理出i和前j段连一起的代价，用prioirity_queue维护换出最优值即可，O(nmlogn)。
  • H：第一个圆从左下角到矩阵中心，第二个圆从右上角到矩阵中心，二分所在位置的比例即可。
  • I：可以用每一行从右往左匹配了多少个位置的状态，注意这个状态要保证单调递增，暴力每种状态有哪些转移，状态只有200多个，高斯消元即可。
  • J：暴搜+剪枝。
附加文件