2017-Sp134-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门看题，感觉楠楠，大家都很会做A的样子，yzc试图上机搞个规律，失败了，之后强搞，cjb上机写java，感觉代码十分不清真，'''A1y62'''。此前sub和cjb搞了搞D，丢了个D给yzc，yzc上机大力分类讨论，'''D2y85'''。sub上机搞C，wa了之后cjb怀疑是popcount没ll，之后对拍了找到错误，'''C2y116'''。此前cjb和yzc讨论了G，上机'''G1y131'''，cjb上机写B，'''B1y173'''。sub和yzc讨论了I，'''I1y188'''。后面尝试做F，GG。
== 总结 ==
=== chenjb ===
今天题目梯度有点大，签完到后剩下4个题既是难题，还是我们队不太擅长的计数，呜呜呜。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：显然从小到大贪心取是对的，然后每次二分当前层的上下区间即可，需要大整数。

 * B：答案不会超过20，每段a会变成2*a+1，最后一段变成2*a，直接用数字存每一段a的个数，用kmp判一下就好。

 * C：大力位运算，用洞-球就可以得到哪些位置是有球的，popcount即可。

 * D：分类讨论，随便构造即可。

 * E：按照附件所写计算即可。

 * F：容斥，dp[i][j]表示至少有i个大小超过j的鞍点的方案数，最后组合数计算即可。注意本题的容斥方案。

 * G：考虑每个位置对答案的贡献，由于or的性质，每个位置只需要知道左右两边每一个二进制位第一次出现的位置即可，这样两边各只有至多16个关键点，暴力枚举即可。最后求前缀最大值得到答案。

 * H：

 * I：把图建出来，对于每个连通块直接大力把每个区间依次放进去，然后检查即可。

 * J：如图，折半分开即可，注意内存。
 *  [[Image(ftiasch1.png,500px)]]  [[Image(ftiasch2.png,500px)]]

流水账

出门看题，感觉楠楠，大家都很会做A的样子，yzc试图上机搞个规律，失败了，之后强搞，cjb上机写java，感觉代码十分不清真，A1y62。此前sub和cjb搞了搞D，丢了个D给yzc，yzc上机大力分类讨论，D2y85。sub上机搞C，wa了之后cjb怀疑是popcount没ll，之后对拍了找到错误，C2y116。此前cjb和yzc讨论了G，上机G1y131，cjb上机写B，B1y173。sub和yzc讨论了I，I1y188。后面尝试做F，GG。

总结

chenjb

今天题目梯度有点大，签完到后剩下4个题既是难题，还是我们队不太擅长的计数，呜呜呜。

oipotato

subconscious

题解

  • A：显然从小到大贪心取是对的，然后每次二分当前层的上下区间即可，需要大整数。
  • B：答案不会超过20，每段a会变成2*a+1，最后一段变成2*a，直接用数字存每一段a的个数，用kmp判一下就好。
  • C：大力位运算，用洞-球就可以得到哪些位置是有球的，popcount即可。
  • D：分类讨论，随便构造即可。
  • E：按照附件所写计算即可。
  • F：容斥，dp[i][j]表示至少有i个大小超过j的鞍点的方案数，最后组合数计算即可。注意本题的容斥方案。
  • G：考虑每个位置对答案的贡献，由于or的性质，每个位置只需要知道左右两边每一个二进制位第一次出现的位置即可，这样两边各只有至多16个关键点，暴力枚举即可。最后求前缀最大值得到答案。
  • H：
  • I：把图建出来，对于每个连通块直接大力把每个区间依次放进去，然后检查即可。
  • J：如图，折半分开即可，注意内存。
附加文件