2017-Sp123-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场cjb和sub光速秒了个B，cjb上了一会儿，sub和yzc讨论出了A，yzc上了'''A1y32'''。然后yzc和sub继续讨论G，上了一下'''G1y45'''。cjb和sub讨论了F，wa了之后发现naive了，'''F2y57'''。sub开始上机写K，猛wa 4发。cjb上机继续写B，'''B1y163'''，此前yzc和cjb开了E，yzc上机，连wa两发。终于发现了K的问题，sub上机修改后'''K5y181'''。之后yzc给sub讲了代码，'''E4y188'''。sub上机写D，cjb改java，'''D1y221'''。最后yzc开出了J，'''J1y258'''。
== 总结 ==
=== chenjb ===
海星，中期卡了题有点惨，还好一下子连过3个题追回了一点节奏。sub注意一些corner case。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：构造长度为r+r+1的环，从环上某个点出发连出一条长度为d-r的链，正确性显然。

 * B：枚举竖着的切割点，跑n次最小表示法，用哈希来比大小。

 * C：按到原点距离排序，可以发现每次新加入的点到某个在其圆内的好点的极角序之间一定没有其他点，用set维护极角序取前驱后继即可。

 * D：容斥，n个物品的方案数可以dp获得，每次强制把枚举的集合合并成一个元素即可，要BigInteger。

 * E：f[0/1][j][k]表示不影响连通性的边数量奇偶性为0/1时，大小为奇数的块有j个，大小为偶数的块有k个的胜负状态，dp即可。

 * F：扫一遍，每次遇到一个字母如果小于等于当前头的字母，就放到开头，反之放到结尾。

 * G：最能满足所有询问的显然是每个点取覆盖它的询问的答案中的最大值，确定完每个点的值之后重新检查一遍所有询问是否符合即可。

 * H：cjb

 * I：

 * J：f[i][0~4]表示前i位在转换之后0代表空串、1代表1个b，2代表1个i，3代表bi，4代表ib这样的情况是否存在，记录下从哪里转移即可生成方案。

 * K：每次尽可能把1铺在当前高度上，如果有奇数个踢掉1的个数最少的那一位，如果只有1个撤销之前的一对来填补，填出超过读入值的答案就输出impossible。

 * [https://wiki.icpc.camp/new-meta/Andrew%20Stankevich%20Contest%2032 NewMeta]

流水账

开场cjb和sub光速秒了个B，cjb上了一会儿，sub和yzc讨论出了A，yzc上了A1y32。然后yzc和sub继续讨论G，上了一下G1y45。cjb和sub讨论了F，wa了之后发现naive了，F2y57。sub开始上机写K，猛wa 4发。cjb上机继续写B，B1y163，此前yzc和cjb开了E，yzc上机，连wa两发。终于发现了K的问题，sub上机修改后K5y181。之后yzc给sub讲了代码，E4y188。sub上机写D，cjb改java，D1y221。最后yzc开出了J，J1y258。

总结

chenjb

海星，中期卡了题有点惨，还好一下子连过3个题追回了一点节奏。sub注意一些corner case。

oipotato

subconscious

题解

  • A：构造长度为r+r+1的环，从环上某个点出发连出一条长度为d-r的链，正确性显然。
  • B：枚举竖着的切割点，跑n次最小表示法，用哈希来比大小。
  • C：按到原点距离排序，可以发现每次新加入的点到某个在其圆内的好点的极角序之间一定没有其他点，用set维护极角序取前驱后继即可。
  • D：容斥，n个物品的方案数可以dp获得，每次强制把枚举的集合合并成一个元素即可，要BigInteger。
  • E：f[0/1][j][k]表示不影响连通性的边数量奇偶性为0/1时，大小为奇数的块有j个，大小为偶数的块有k个的胜负状态，dp即可。
  • F：扫一遍，每次遇到一个字母如果小于等于当前头的字母，就放到开头，反之放到结尾。
  • G：最能满足所有询问的显然是每个点取覆盖它的询问的答案中的最大值，确定完每个点的值之后重新检查一遍所有询问是否符合即可。
  • H：cjb
  • I：
  • J：f[i][0~4]表示前i位在转换之后0代表空串、1代表1个b，2代表1个i，3代表bi，4代表ib这样的情况是否存在，记录下从哪里转移即可生成方案。
  • K：每次尽可能把1铺在当前高度上，如果有奇数个踢掉1的个数最少的那一位，如果只有1个撤销之前的一对来填补，填出超过读入值的答案就输出impossible。
  • NewMeta
附加文件