2017-Sp129-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
开场yzc读A失败，cjb读了之后丢给yzc，上机'''A1y11'''，sub上机'''K1y16'''。cjb读了B和C，丢给yzc上机写B，the之后卡了卡，'''B2y50'''。之后sub上机冲H，the，然后回过头来写F，wa。之后F和H刚了许久，cjb和yzc讨论了C，yzc上机'''C1y102'''，之后sub上机对拍了一下'''F1y128'''，然后开始帮H卡常，之后发现做法有点问题，忘记排序，排序之后还是tle，没去重，改了之后变成wa，对拍获得通过，'''H7y206'''，之后sub上机写L，mle之后改了做法，'''L3y242'''。最后cjb和yzc联手写I，wa了，没能找到错误。
== 总结 ==
=== chenjb ===
有点难受，前面节奏有点慢，因为vjudge的原因没看到有个签到题很伤，H出现了很多问题，之后I没时间debug了，交了获得wa，但是时间复杂度也不自信。这TM好像是个数学场啊gtmBUAA。
[[BR]]淦啊这个I其实没过样例，特判了就过了md，赛后一直都看不出来直到试图对拍才发现自己样例最简单的一个wa掉了....
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：取对数。

 * B：计算每一种字母的贡献，排序后贪心赋值25~0，注意处理前导0的情况。

 * C：考虑计算每种颜色的贡献，要计算的是至少经过一次该种颜色的路径数量，转化为没有经过该种颜色的路径数量，只要求出去掉这些点后树的每个连通块大小即可，对于每一种颜色，按dfs倒序处理，每一次枚举当前点的所有儿子，则这一块连通块的大小为为这个子树减去这个子树内已插入的大小，处理完每个点的儿子之后将这个点插入线段树即可。

 * D：sub

 * E：sub

 * F：显然对于a[i]的每个循环节，其取值必然是b[i]的某一个循环节，且b[i]的环长能够整除a[i]的环长，预处理统计一下，乘起来即可。

 * G：cjb

 * H：把查询排序，从大到小nth-element即可。

 * I：考虑一条边至多存在一个环，那么变成有m个环，需要删掉一条边，求k小的和，可以转化成有m个集合，每个集合取一个值加起来求前k大。把集合一个一个合并进来，直接做的复杂度看起来是O(m*klogk)，但是我们如果每次保证堆的大小是要并入的集合的大小，则复杂度变成O(Σklog(m[i]))，等价于O(klog(π(m[i])))，最坏情况下也是O(nk)的。注意写法要科学一点，不然可能需要特判原本是一棵树的情况。

 * J：sub

 * K：手画一下，可得前n个是1到n，接下来会以2n-2循环。

 * L：每次找出当前区间的最小值，这个位置会把区间分成两个部分，两个部分的组合贡献用组合数算出即可，分治下去。

 * [http://bestcoder.hdu.edu.cn/blog/2017-multi-university-training-contest-8-solutions-by-北京航空航天大学/ Official]

流水账

开场yzc读A失败，cjb读了之后丢给yzc，上机A1y11，sub上机K1y16。cjb读了B和C，丢给yzc上机写B，the之后卡了卡，B2y50。之后sub上机冲H，the，然后回过头来写F，wa。之后F和H刚了许久，cjb和yzc讨论了C，yzc上机C1y102，之后sub上机对拍了一下F1y128，然后开始帮H卡常，之后发现做法有点问题，忘记排序，排序之后还是tle，没去重，改了之后变成wa，对拍获得通过，H7y206，之后sub上机写L，mle之后改了做法，L3y242。最后cjb和yzc联手写I，wa了，没能找到错误。

总结

chenjb

有点难受，前面节奏有点慢，因为vjudge的原因没看到有个签到题很伤，H出现了很多问题，之后I没时间debug了，交了获得wa，但是时间复杂度也不自信。这TM好像是个数学场啊gtmBUAA。

淦啊这个I其实没过样例，特判了就过了md，赛后一直都看不出来直到试图对拍才发现自己样例最简单的一个wa掉了....

oipotato

subconscious

题解

• A：取对数。
• B：计算每一种字母的贡献，排序后贪心赋值25~0，注意处理前导0的情况。
• C：考虑计算每种颜色的贡献，要计算的是至少经过一次该种颜色的路径数量，转化为没有经过该种颜色的路径数量，只要求出去掉这些点后树的每个连通块大小即可，对于每一种颜色，按dfs倒序处理，每一次枚举当前点的所有儿子，则这一块连通块的大小为为这个子树减去这个子树内已插入的大小，处理完每个点的儿子之后将这个点插入线段树即可。
• D：sub
• E：sub
• F：显然对于a[i]的每个循环节，其取值必然是b[i]的某一个循环节，且b[i]的环长能够整除a[i]的环长，预处理统计一下，乘起来即可。
• G：cjb
• H：把查询排序，从大到小nth-element即可。
• I：考虑一条边至多存在一个环，那么变成有m个环，需要删掉一条边，求k小的和，可以转化成有m个集合，每个集合取一个值加起来求前k大。把集合一个一个合并进来，直接做的复杂度看起来是O(m*klogk)，但是我们如果每次保证堆的大小是要并入的集合的大小，则复杂度变成O(Σklog(m[i]))，等价于O(klog(π(m[i])))，最坏情况下也是O(nk)的。注意写法要科学一点，不然可能需要特判原本是一棵树的情况。
• J：sub
• K：手画一下，可得前n个是1到n，接下来会以2n-2循环。
• L：每次找出当前区间的最小值，这个位置会把区间分成两个部分，两个部分的组合贡献用组合数算出即可，分治下去。
• Official