2017-Sp127-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，yzc会做C之后上机写C，wa，cjb上机写K，也wa。yzc找到了问题，'''C2y25'''，cjb社保了，'''K2y35'''。sub上机冲B，wa，yzc上机写H，'''H1y59'''。之后sub终于'''B3y73'''。cjb上机艰难写A，wa了之后换yzc写L，'''L1y163'''。之后sub终于猜到了结论，'''J1y196'''。对拍找到A错误，还是wa。最后cjb看到一个hash可能溢出了，修改后'''A3y215'''。之后试图做G，刚不下来。
== 总结 ==
=== chenjb ===
A题写了一年，结果hash溢出了md。第8个题不会做有点烦，sub开场撸了B之后节奏没有起飞有点遗憾，主要是我和yzc都被题目困住了，要小心这样的题目场。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：把字符串排序放进A数组，倒过来排序放B数组，每个字符串在平面上的点即是(rkA,rkB)，对于每个询问的前缀和后缀，找到在A和B分别代表的区间，就变成了矩形求包含点个数问题，大力主席树求解，注意这样会计算到前后缀重叠的部分，需要套个哈希，枚举重叠长度来去掉非法解。

 * B：作辅助线可得答案要么是取中点，要么是一条直线，分类讨论一下即可，注意共线和都在圆心的情况。

 * C：每个位置相当于求出整个序列中挖掉其下标的倍数位置之后的最大值，挖掉之后显然整个序列被分成几个区间，分别用rmq求最大值即可，总区间数显然是nlogn个。

 * D：没有贡献相似度的点把树分割成多棵树。所以转化为把原树拆成3棵树，所以枚举两个断边，然后树hash，压进set里判断是否存在一种方案匹配即可。注意题目描述很迷，实际上是个有根树，所有节点的父亲是固定的，只是你可以重标号而已，得用有根树hash。

 * E：

 * F：用bfs来预处理所有不同的怪物死亡状态下能够获得的每一种buff的次数和可以攻击到哪些怪兽。考虑DP，f[mask][x][y]表示杀死的怪兽状态为mask，攻击力为x，防御力为y的最大的生命值。每一次转移时显然要将新得到的buff和魔法用完，于是枚举新的魔法使用次数中，多少次用来增加攻击力，多少次用来增加防御力，剩下的都加进生命即可。注意到怪兽的生命和攻击最多只有20点，所以攻击和防御超过20之后就没有意义了，所以实际状态数为O(2^7^*20^2^)，转移的复杂度为O(7*20^2^)。

 * G：维护所有左端点的答案，每次右端点延伸一格Ar，取出所有Ar|Ai&&i<r,定义Ai对起点在1<=l<=i的答案贡献为i到r之间gcd(Ai,Aj)==1&&Ar|Aj的位置数量。从右往左扫一遍，在质因子上容斥求出贡献，再用树状数组维护即可。总复杂度由均摊分析得到O(n log^2^ n)。

 * H：将所有答案的区间相向移动，可以得到两个区间相邻的端点要么贴在一起，要么差一格，显然所有的合法区间对都可以用这样两个点表示，枚举所有组合，向两端扩展，用two-pointer做到每次O(n)

 * I：

 * J：当且仅当存在完美匹配且Bob能将完美匹配完全割开时则获胜，反之Alice。

 * K：画出venn图，判断每一块是否>=0即可。

 * L：倍增从i开始写了 2^j^ 行到了哪个单词，对两种长度都做一遍，然后询问的时候直接倍增即可。


 * [http://bestcoder.hdu.edu.cn/blog/2017-multi-university-training-contest-6-solutions-by-福州大学/ Official]

流水账

开场各自看题，yzc会做C之后上机写C，wa，cjb上机写K，也wa。yzc找到了问题，C2y25，cjb社保了，K2y35。sub上机冲B，wa，yzc上机写H，H1y59。之后sub终于B3y73。cjb上机艰难写A，wa了之后换yzc写L，L1y163。之后sub终于猜到了结论，J1y196。对拍找到A错误，还是wa。最后cjb看到一个hash可能溢出了，修改后A3y215。之后试图做G，刚不下来。

总结

chenjb

A题写了一年，结果hash溢出了md。第8个题不会做有点烦，sub开场撸了B之后节奏没有起飞有点遗憾，主要是我和yzc都被题目困住了，要小心这样的题目场。

oipotato

subconscious

题解

A：把字符串排序放进A数组，倒过来排序放B数组，每个字符串在平面上的点即是(rkA,rkB)，对于每个询问的前缀和后缀，找到在A和B分别代表的区间，就变成了矩形求包含点个数问题，大力主席树求解，注意这样会计算到前后缀重叠的部分，需要套个哈希，枚举重叠长度来去掉非法解。
B：作辅助线可得答案要么是取中点，要么是一条直线，分类讨论一下即可，注意共线和都在圆心的情况。
C：每个位置相当于求出整个序列中挖掉其下标的倍数位置之后的最大值，挖掉之后显然整个序列被分成几个区间，分别用rmq求最大值即可，总区间数显然是nlogn个。
D：没有贡献相似度的点把树分割成多棵树。所以转化为把原树拆成3棵树，所以枚举两个断边，然后树hash，压进set里判断是否存在一种方案匹配即可。注意题目描述很迷，实际上是个有根树，所有节点的父亲是固定的，只是你可以重标号而已，得用有根树hash。
E：
F：用bfs来预处理所有不同的怪物死亡状态下能够获得的每一种buff的次数和可以攻击到哪些怪兽。考虑DP，f[mask][x][y]表示杀死的怪兽状态为mask，攻击力为x，防御力为y的最大的生命值。每一次转移时显然要将新得到的buff和魔法用完，于是枚举新的魔法使用次数中，多少次用来增加攻击力，多少次用来增加防御力，剩下的都加进生命即可。注意到怪兽的生命和攻击最多只有20点，所以攻击和防御超过20之后就没有意义了，所以实际状态数为O(2⁷*20²)，转移的复杂度为O(7*20²)。
G：维护所有左端点的答案，每次右端点延伸一格Ar，取出所有Ar|Ai&&i2 n)。
H：将所有答案的区间相向移动，可以得到两个区间相邻的端点要么贴在一起，要么差一格，显然所有的合法区间对都可以用这样两个点表示，枚举所有组合，向两端扩展，用two-pointer做到每次O(n)
I：
J：当且仅当存在完美匹配且Bob能将完美匹配完全割开时则获胜，反之Alice。
K：画出venn图，判断每一块是否>=0即可。
L：倍增从i开始写了 2^j 行到了哪个单词，对两种长度都做一遍，然后询问的时候直接倍增即可。
Official

附加文件

1.png by chenjb