2017-Sp166-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，yzc发现A是ac自动机裸题，犹豫了一下让cjb上机，wa1 tle1，cjb独自思考A，yzc和sub讨论F，'''F1y35'''，cjb上机写A，'''A3y69'''。之后yzc上机写sub给的D构造，加了assert RE两发，cjb给了另一个构造，'''D3y91'''，之后sub上机写B，'''B1y118'''，之后三人讨论G，yzc上机，mle后改成滚动数组wa了，'''G3y142'''，之后cjb和sub讨论I，向yzc确认做法后上机wa了两发，期间sub和yzc讨论H，之后sub上机写H，'''H1y236'''，之后sub开出了J，等着I过后上去rush，结果I 拍了之后偏差越来越大，sub也加入了fix的路，无果而终，打出GG。
== 总结 ==
=== chenjb ===
封榜后cjb和yzc对I太乐观了(虽然是一些逻辑上的问题也比较难fix)，sub也应该更早开出J，不应该被错误的初印象蒙蔽了，而且封榜后cjb应该问下sub J实际需要的时间。综上导致封榜后爆炸，应该要至少过1题，8题才是能接受的水平。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：就是求AC自动机的fail指针，因为字符集较大，用字典树维护即可，每次取父亲fail指向的节点的主席树上该字母对应的值即可，每次向下走的时候更新主席树的值，直接用最新的覆盖就好，满足AC自动机的定义。

 * B：手写bitset，暴力广搜O(n^3^)，用bitset维护每次新增加的点。

 * C：考虑对偶图，就是棋盘的那些边框，每个连通块都是个环，每个环拿个 splay 维护就行，翻的时候加减边情况很复杂。by 叉姐

 * D：黑白染色，黑点在dfs时进入时填入答案，反之在dfs离开时填入答案。

 * E：结论：没有ban的情况，直接将斜率相邻的直线交点求凸包即可。将所有被ban的点所在的两条直线拿出来，O(n)统计最远的两个点加入集合求凸包即可。精度非常快乐，需要调宽一点（1e-9）。

 * F：f[mask1][mask2]代表前8前八位为mask1且后八位为mask2的方案数，查询时枚举后八位，插入时枚举前八位即可。

 * G：f[i][j][k]代表前i层，有j个树上节点，还有k个单词没放入，滚动数组转移即可。

 * H：容斥,先把ai预处理成non-decreasing的，f[i]表示1到i的答案，f[i]=C(a[i]+i,i)-f[j-1]*C(a[i]-a[j]+i-j,i-j+1)，快乐lucas。

 * I：将图分成A和B两块，先状压dp处理出A所有点匹配好之后B所有可能状态的方案数，然后对B内部再状压dp求出每种剩下的状态自行匹配的方案数，对应相乘即可。

 * J：枚举前两个组成的二元对，插到二维树状数组里，然后枚举后两个组成的二元对，查询。

 * [https://wiki.icpc.camp/twsf/ICPCCamp%202016%20Day1%20ftiasch’s%20Contest%20#4 The Way So Far]
 * [https://wiki.icpc.camp/dreadnought/ICPCCamp%202016%20Day%201%20-%20ftiasch’s%20Contest%20#4 Dreadnought]

流水账

出门各自看题，yzc发现A是ac自动机裸题，犹豫了一下让cjb上机，wa1 tle1，cjb独自思考A，yzc和sub讨论F，F1y35，cjb上机写A，A3y69。之后yzc上机写sub给的D构造，加了assert RE两发，cjb给了另一个构造，D3y91，之后sub上机写B，B1y118，之后三人讨论G，yzc上机，mle后改成滚动数组wa了，G3y142，之后cjb和sub讨论I，向yzc确认做法后上机wa了两发，期间sub和yzc讨论H，之后sub上机写H，H1y236，之后sub开出了J，等着I过后上去rush，结果I 拍了之后偏差越来越大，sub也加入了fix的路，无果而终，打出GG。

总结

chenjb

封榜后cjb和yzc对I太乐观了(虽然是一些逻辑上的问题也比较难fix)，sub也应该更早开出J，不应该被错误的初印象蒙蔽了，而且封榜后cjb应该问下sub J实际需要的时间。综上导致封榜后爆炸，应该要至少过1题，8题才是能接受的水平。

oipotato

subconscious

题解

A：就是求AC自动机的fail指针，因为字符集较大，用字典树维护即可，每次取父亲fail指向的节点的主席树上该字母对应的值即可，每次向下走的时候更新主席树的值，直接用最新的覆盖就好，满足AC自动机的定义。
B：手写bitset，暴力广搜O(n³)，用bitset维护每次新增加的点。
C：考虑对偶图，就是棋盘的那些边框，每个连通块都是个环，每个环拿个 splay 维护就行，翻的时候加减边情况很复杂。by 叉姐
D：黑白染色，黑点在dfs时进入时填入答案，反之在dfs离开时填入答案。
E：结论：没有ban的情况，直接将斜率相邻的直线交点求凸包即可。将所有被ban的点所在的两条直线拿出来，O(n)统计最远的两个点加入集合求凸包即可。精度非常快乐，需要调宽一点（1e-9）。
F：f[mask1][mask2]代表前8前八位为mask1且后八位为mask2的方案数，查询时枚举后八位，插入时枚举前八位即可。
G：f[i][j][k]代表前i层，有j个树上节点，还有k个单词没放入，滚动数组转移即可。
H：容斥,先把ai预处理成non-decreasing的，f[i]表示1到i的答案，f[i]=C(a[i]+i,i)-f[j-1]*C(a[i]-a[j]+i-j,i-j+1)，快乐lucas。
I：将图分成A和B两块，先状压dp处理出A所有点匹配好之后B所有可能状态的方案数，然后对B内部再状压dp求出每种剩下的状态自行匹配的方案数，对应相乘即可。
J：枚举前两个组成的二元对，插到二维树状数组里，然后枚举后两个组成的二元对，查询。
The Way So Far
Dreadnought

附加文件

1.png by chenjb