2017-Sp165-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，sub以为自己会C，上机摸了一会儿走远了，之后sub上机写I，'''I2y66'''，cjb上机抄SAM，yzc '''J1y80'''，cjb试图搞F， wa了，叉了算法，改帮yzc写L，'''L1y122'''，之后cjb在机上疯狂艹F，wa了一万发，之后yzc上机写B，wa了之后对拍'''B2y216'''，cjb上机写点分治，sub上机补二分，'''K1y256'''，之后cjb和yzc刚F，wa了一年，赛后发现cjb参数反了，才过。
== 总结 ==
=== chenjb ===
朝鲜人真厉害，一个个题都真鸡儿大。好气啊，感觉如果不是我F题dfs参数写反就win了mdzz，gtmsub。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：

 * B：f[i]代表1~i最多能分成几段，转移的前提条件是s[i] xor s[j] <= a[j]，用trie维护插入删除求子树最小值即可。

 * C：

 * D：

 * E：

 * F：答案只会是[-1,3]区间的，需要大力分类讨论，如果u=v则答案为0，否则如果dis(u,v)>=d则答案为1，否则如果u和v到直径的某一端距离都>=d则答案为2，之后就考虑是否存在一个点能够作为中转站，需要分类讨论这个点位于中点左侧还是右侧，需要预处理+rmq，存在则答案为2，否则考虑是否能从u到某个端点，然后到另一个端点，然后到v，这样则答案为3，再不行答案为-1。

 * G：

 * H：

 * I：考虑容斥，发现两条路径有交点的方案可以视为两个人交换的终点，容斥的式子刚好是矩阵A的行列式，A[i][j]代表第i个人起点到第j个人终点的方案数，大力求解即可。

 * J：广义后缀自动机裸题。

 * K：二分答案，小于等于二分值的边赋k-1，否则赋-1，点分治判断是否存在大于0的路径即可。

 * L：二分答案，网络流求时间为T时最大的净收入，S向左边点连A[i]，右边点向T连B[i]，中间边流量inf。

 * M：

 * [http://bestcoder.hdu.edu.cn/blog/2016-multi-university-training-contest-9-solutions-by-金策工业综合大学/ Official]

流水账

出门各自看题，sub以为自己会C，上机摸了一会儿走远了，之后sub上机写I，I2y66，cjb上机抄SAM，yzc J1y80，cjb试图搞F， wa了，叉了算法，改帮yzc写L，L1y122，之后cjb在机上疯狂艹F，wa了一万发，之后yzc上机写B，wa了之后对拍B2y216，cjb上机写点分治，sub上机补二分，K1y256，之后cjb和yzc刚F，wa了一年，赛后发现cjb参数反了，才过。

总结

chenjb

朝鲜人真厉害，一个个题都真鸡儿大。好气啊，感觉如果不是我F题dfs参数写反就win了mdzz，gtmsub。

oipotato

subconscious

题解

• A：
• B：f[i]代表1~i最多能分成几段，转移的前提条件是s[i] xor s[j] <= a[j]，用trie维护插入删除求子树最小值即可。
• C：
• D：
• E：
• F：答案只会是[-1,3]区间的，需要大力分类讨论，如果u=v则答案为0，否则如果dis(u,v)>=d则答案为1，否则如果u和v到直径的某一端距离都>=d则答案为2，之后就考虑是否存在一个点能够作为中转站，需要分类讨论这个点位于中点左侧还是右侧，需要预处理+rmq，存在则答案为2，否则考虑是否能从u到某个端点，然后到另一个端点，然后到v，这样则答案为3，再不行答案为-1。
• G：
• H：
• I：考虑容斥，发现两条路径有交点的方案可以视为两个人交换的终点，容斥的式子刚好是矩阵A的行列式，A[i][j]代表第i个人起点到第j个人终点的方案数，大力求解即可。
• J：广义后缀自动机裸题。
• K：二分答案，小于等于二分值的边赋k-1，否则赋-1，点分治判断是否存在大于0的路径即可。
• L：二分答案，网络流求时间为T时最大的净收入，S向左边点连A[i]，右边点向T连B[i]，中间边流量inf。
• M：
• Official

附加文件

• 1.png by chenjb