2017-Sp108-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，cjb秒了D，'''D1y8'''。yzc秒了B，'''B1y16'''。cjb读了F，问了下sub的坐标变换，丢给yzc搞，cdc一下'''F1y35'''。sub思考了H，和cjb讨论了一下后上机，'''H1y41'''。cjb上机写C，ac自动机搞了搞丢给sub高斯消元，'''C1y83'''。cjb丢了个线段树优化建图的东西给yzc，三个人讨论了一下，yzc上机写A，之后过不了样例，sub上机写I，yzc和cjb讨论了之后明晰了做法，上机fix，'''A1y140'''。sub上机I wa了，yzc上机写之前和sub讨论的J，也wa了。之后找到错误又wa，cjb读题发现J的坑，'''J3y186'''。sub上机写I，还是wa，cjb开了G，质疑了sub的模型，sub发现读题有点偏差，就变成了sb题，cjb上机写G，'''G1y227'''。sub和yzc在机下研究I，发现I读错题意了，sub思考做法，G过后上机，'''I1y243'''。yzc全场一直在努力用n^2^刚E，又wa又tle，怀疑人生。cjb封榜后大致想到了E点分的统计，写不完了GG。
== 总结 ==
=== chenjb ===
抢下了D的一血，开心。今天还是比较顺，但是有三道题读错了，稍微拍下sub的头，不过一个值得提醒的点是：模型转化的时候一定要注意不要漏掉corner case，如果wa了要先回到题面找细节。另外E最后才想到点分治的统计方式，写不完了。最后被claris 30发交K反杀，真难过QAQ
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：线段树优化建图，然后跑tarjan，用set维护块里的最小值，注意去掉无关的点。

 * B：set维护即可。

 * C：KMP或者AC自动机建起来，跑高斯消元。

 * D：连续的两个字母可以消掉，观察题面还可获得ababa可以变成bab，缩到最后如果剩下字母就是open，反之close。

 * E：yzc

 * F：(x,y)变成(x+y,x-y)，变成询问一个矩形的点数，cdq分治。

 * G：认真观察式子，会发现极值只在t=0和T的时候取得，把一个点变化为(a*0+b,a*T+b)，跑最小圆覆盖，半径的平方就是答案。

 * H：f[mask]存一个二元组表示mask下最少背包数及最空的背包是多少，2^24^*24暴力转移。

 * I：a直接dp记录物品数，b二分答案，对于大于小于mid的物品分两个背包合并，c先每种加一个，不断增加轮次，d用双堆栈模拟队列即可。

 * J：f[i][0/1]表示第一个序列匹配到i这个位置，向上/下答案，把B序列逐个加入，用树状数组维护转移。注意题意有坑，任意一个长度为2的公共子序列都是答案。

 * K：

流水账

开场各自看题，cjb秒了D，D1y8。yzc秒了B，B1y16。cjb读了F，问了下sub的坐标变换，丢给yzc搞，cdc一下F1y35。sub思考了H，和cjb讨论了一下后上机，H1y41。cjb上机写C，ac自动机搞了搞丢给sub高斯消元，C1y83。cjb丢了个线段树优化建图的东西给yzc，三个人讨论了一下，yzc上机写A，之后过不了样例，sub上机写I，yzc和cjb讨论了之后明晰了做法，上机fix，A1y140。sub上机I wa了，yzc上机写之前和sub讨论的J，也wa了。之后找到错误又wa，cjb读题发现J的坑，J3y186。sub上机写I，还是wa，cjb开了G，质疑了sub的模型，sub发现读题有点偏差，就变成了sb题，cjb上机写G，G1y227。sub和yzc在机下研究I，发现I读错题意了，sub思考做法，G过后上机，I1y243。yzc全场一直在努力用n²刚E，又wa又tle，怀疑人生。cjb封榜后大致想到了E点分的统计，写不完了GG。

总结

chenjb

抢下了D的一血，开心。今天还是比较顺，但是有三道题读错了，稍微拍下sub的头，不过一个值得提醒的点是：模型转化的时候一定要注意不要漏掉corner case，如果wa了要先回到题面找细节。另外E最后才想到点分治的统计方式，写不完了。最后被claris 30发交K反杀，真难过QAQ

oipotato

subconscious

题解

A：线段树优化建图，然后跑tarjan，用set维护块里的最小值，注意去掉无关的点。
B：set维护即可。
C：KMP或者AC自动机建起来，跑高斯消元。
D：连续的两个字母可以消掉，观察题面还可获得ababa可以变成bab，缩到最后如果剩下字母就是open，反之close。
E：yzc
F：(x,y)变成(x+y,x-y)，变成询问一个矩形的点数，cdq分治。
G：认真观察式子，会发现极值只在t=0和T的时候取得，把一个点变化为(a*0+b,a*T+b)，跑最小圆覆盖，半径的平方就是答案。
H：f[mask]存一个二元组表示mask下最少背包数及最空的背包是多少，2²⁴*24暴力转移。
I：a直接dp记录物品数，b二分答案，对于大于小于mid的物品分两个背包合并，c先每种加一个，不断增加轮次，d用双堆栈模拟队列即可。
J：f[i][0/1]表示第一个序列匹配到i这个位置，向上/下答案，把B序列逐个加入，用树状数组维护转移。注意题意有坑，任意一个长度为2的公共子序列都是答案。
K：

附加文件

1.png by chenjb