2017-Sp226-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，跟榜发现G是2-sat裸题，yzc上机'''G1y37'''。然后sub和yzc讨论E，'''E2y59'''。cjb上机写B，B wa了两发。yzc先上机写F，'''F1y75'''。sub上机写C，'''C1y84'''。cjb让yzc去拍B，找到错误'''B3y96'''。sub表示自己很懂K，上机wa了。cjb和yzc对I给出了一个线段树优化费用流的做法，cjb上机去写。sub回来fix了一下K，'''K2y151'''。yzc上机写H，I写完后也wa了。yzc fix了一下，'''H1y180'''。cjb fix了一下还是wa，决定对拍。sub上机写D，tle了2发。cjb拍过了之后RE了，sub fix D，'''D3y213'''。之后发现I有坑爹的n=0，然而改过之后I tle了。sub和cjb重新讨论I题，给出了贪心，'''I2y277'''。A的题意非常难懂，过的人很少，但是都怀疑是个sb SAM。终于在完场10min读懂了，yzc怀疑要lct维护，但是cjb和sub建议先上一发暴力，但是来不及写完了，最后赛后10min过A。
== 总结 ==
=== chenjb ===
这个I可能太自信了啊...冷静一点就能想到正确的做法了啊....QAQ  A是个什么jb题意杀...不过这个暴力跳父亲能过也比较玄学
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：SAM裸题？其实可能需要上个LCT维护，然而裸跳父亲就过了，看了看dls和newmeta都是这样做的，怀疑是题目模型侧面保证了该做法能过。

 * B：两个串交错构成新的串，所求等价于新串的回文串，之后跑manacher后取合法答案即可。

 * C：枚举r和s的距离，根据r对s的贡献可以算出r前面那位是多少，可以不断往前推，直到非法。一共只有log个，取字典序最小。

 * D：二分答案，把三个人都贴在边缘上，计算两两之间相切时的圆心角，小于360度合法，需要卡下常数。

 * E：解二次方程可得单步最小时间，8!暴力即可。

 * F：从大到小如果一个人他需要杀的士兵都能够或者已经被杀，就不取。

 * G：2-sat裸题。

 * H：直接根据当前01能放进某个卡组就放，不然就新建。对于第二个答案，先得到最小卡组数量，然后每一次选择牌数最小的卡组加入，注意一开始要记录以0和1打头的卡组数量。

 * I：从大到小枚举是否能加入答案集合，判定时每次有空位弹出给最早结束的区间。

 * J：sub

 * K：旋转卡壳求出所有最长对角线，建图，图能二分染色就TAK否则NIE。

流水账

出门各自看题，跟榜发现G是2-sat裸题，yzc上机G1y37。然后sub和yzc讨论E，E2y59。cjb上机写B，B wa了两发。yzc先上机写F，F1y75。sub上机写C，C1y84。cjb让yzc去拍B，找到错误B3y96。sub表示自己很懂K，上机wa了。cjb和yzc对I给出了一个线段树优化费用流的做法，cjb上机去写。sub回来fix了一下K，K2y151。yzc上机写H，I写完后也wa了。yzc fix了一下，H1y180。cjb fix了一下还是wa，决定对拍。sub上机写D，tle了2发。cjb拍过了之后RE了，sub fix D，D3y213。之后发现I有坑爹的n=0，然而改过之后I tle了。sub和cjb重新讨论I题，给出了贪心，I2y277。A的题意非常难懂，过的人很少，但是都怀疑是个sb SAM。终于在完场10min读懂了，yzc怀疑要lct维护，但是cjb和sub建议先上一发暴力，但是来不及写完了，最后赛后10min过A。

总结

chenjb

这个I可能太自信了啊...冷静一点就能想到正确的做法了啊....QAQ A是个什么jb题意杀...不过这个暴力跳父亲能过也比较玄学

oipotato

subconscious

题解

  • A：SAM裸题？其实可能需要上个LCT维护，然而裸跳父亲就过了，看了看dls和newmeta都是这样做的，怀疑是题目模型侧面保证了该做法能过。
  • B：两个串交错构成新的串，所求等价于新串的回文串，之后跑manacher后取合法答案即可。
  • C：枚举r和s的距离，根据r对s的贡献可以算出r前面那位是多少，可以不断往前推，直到非法。一共只有log个，取字典序最小。
  • D：二分答案，把三个人都贴在边缘上，计算两两之间相切时的圆心角，小于360度合法，需要卡下常数。
  • E：解二次方程可得单步最小时间，8!暴力即可。
  • F：从大到小如果一个人他需要杀的士兵都能够或者已经被杀，就不取。
  • G：2-sat裸题。
  • H：直接根据当前01能放进某个卡组就放，不然就新建。对于第二个答案，先得到最小卡组数量，然后每一次选择牌数最小的卡组加入，注意一开始要记录以0和1打头的卡组数量。
  • I：从大到小枚举是否能加入答案集合，判定时每次有空位弹出给最早结束的区间。
  • J：sub
  • K：旋转卡壳求出所有最长对角线，建图，图能二分染色就TAK否则NIE。
附加文件