2017-Sp74-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，sub读了L，让yzc秒了L，'''L1y4'''。发现有人过I，cjb把I秒了丢给yzc，'''I1y15'''。cjb读了A，也秒了A，跟sub讲了讲，sub推了一会儿，the一发后调整了一下二分，'''A2y33'''。cjb和yzc研究B，cjb丢了个dp，yzc上机'''B1y50'''。cjb读了F，发现是费马点模板题，随后找到了板子，sub看了看发现可行，之后cjb上机敲，调整了下参数后'''F1y70'''。此前cjb读了C，感觉是个简单构造题，丢给sub，sub之后'''C1y76'''。sub和yzc开出了H，yzc上机'''H1y97'''。sub独自思考G，cjb和yzc讨论J，之后sub上机写G，之后wa了，调整了之后终于'''G3y191'''。cjb和yzc讨论J到了很深一步了，sub加入讨论后给出了最后一击，cjb上机写预处理，yzc上机写work，之后wa了。cjb上机写了暴力，yzc对拍之后发现去重有些问题，修改之后终于'''J2y292'''。
== 总结 ==
=== chenjb ===
今天还行，希望以后能通过训练找到三个人的新的平衡点。
=== oipotato ===

=== subconscious  ===
== 题解 ==
 * D：
   * 题意：标准国际象棋8*8，王+城堡对王，求最优情况后手最多步数。
   * 题解：大力8^6^*2个状态记忆化搜索，转移16。注意城堡会被自己王挡住的情况。~~这个题为什么不是yzc的锅？~~
 * E：
   * 题意：一开始只存在一个区间[0,0]，n个修改，参数t,x,r，在t时刻将所有区间落在[x-r+1,x+r-1]的部分去掉。s个询问，参数t,x，t时刻时是否存在区间覆盖点x。
   * 题解：用set维护所有区间在t=0时刻的形态，对于询问显然只需找到对应区间即可，对于修改，暴力删除所有的在这个时间点被包含的区间，并记录这些区间在t=0时刻的最左端ll与最右端rr，然后将删除区间剩余部分放回set（显然剩余部分仅有包含ll和rr的两部分）。
 * K：
   * 题意：给出一个长串，多次询问一个短串，问出现的次数，其中可以有且仅有一个字母不同。
   * 题解：把长串和所有短串连起来做SA，然后对于每个询问串假设表示成S1+p+S2，先二分出S1的区间作为[L1,R1]，然后枚举字母p，进而缩小到区间[L2,R2]，最后把S2也确定，即区间[L3,R3]，最后再统计下这个区间里有效后缀的个数。SAM的做法见附录中官方题解。
 * [wiki:2016-E34-team1]
== 补题 ==
 * ~~D~~ by sub
 * ~~E~~ by yzc
 * ~~K~~ by cjb

流水账

开场各自看题，sub读了L，让yzc秒了L，L1y4。发现有人过I，cjb把I秒了丢给yzc，I1y15。cjb读了A，也秒了A，跟sub讲了讲，sub推了一会儿，the一发后调整了一下二分，A2y33。cjb和yzc研究B，cjb丢了个dp，yzc上机B1y50。cjb读了F，发现是费马点模板题，随后找到了板子，sub看了看发现可行，之后cjb上机敲，调整了下参数后F1y70。此前cjb读了C，感觉是个简单构造题，丢给sub，sub之后C1y76。sub和yzc开出了H，yzc上机H1y97。sub独自思考G，cjb和yzc讨论J，之后sub上机写G，之后wa了，调整了之后终于G3y191。cjb和yzc讨论J到了很深一步了，sub加入讨论后给出了最后一击，cjb上机写预处理，yzc上机写work，之后wa了。cjb上机写了暴力，yzc对拍之后发现去重有些问题，修改之后终于J2y292。

总结

chenjb

今天还行，希望以后能通过训练找到三个人的新的平衡点。

oipotato

subconscious

题解

D：
- 题意：标准国际象棋8*8，王+城堡对王，求最优情况后手最多步数。
- 题解：大力8⁶*2个状态记忆化搜索，转移16。注意城堡会被自己王挡住的情况。~~这个题为什么不是yzc的锅？~~
E：
- 题意：一开始只存在一个区间[0,0]，n个修改，参数t,x,r，在t时刻将所有区间落在[x-r+1,x+r-1]的部分去掉。s个询问，参数t,x，t时刻时是否存在区间覆盖点x。
- 题解：用set维护所有区间在t=0时刻的形态，对于询问显然只需找到对应区间即可，对于修改，暴力删除所有的在这个时间点被包含的区间，并记录这些区间在t=0时刻的最左端ll与最右端rr，然后将删除区间剩余部分放回set（显然剩余部分仅有包含ll和rr的两部分）。
K：
- 题意：给出一个长串，多次询问一个短串，问出现的次数，其中可以有且仅有一个字母不同。
- 题解：把长串和所有短串连起来做SA，然后对于每个询问串假设表示成S1+p+S2，先二分出S1的区间作为[L1,R1]，然后枚举字母p，进而缩小到区间[L2,R2]，最后把S2也确定，即区间[L3,R3]，最后再统计下这个区间里有效后缀的个数。SAM的做法见附录中官方题解。
2016-E34-team1

补题

D by sub
E by yzc
K by cjb

附加文件

handout-day-4.pdf by chenjb
1.png by chenjb
problems-e-001491.pdf by chenjb