USACO 2020 US Open赛题解析

R表示疾病的传播半径 如果两个人距离小于R即会被传染

我们发现如果相邻的两个人 一个人传染一个人不传染 那么R不应该大于这两个人的距离

当求出最大的R以后 我们即可求出答案

然后确保了 后出现的x更小

然后进行块合并即可

我们发现 当我们插入一个数时 前面还没有插的位置 此后一定比当前数大

所以使用树状数组统计即可

我们发现一个点的儿子都需要合并

我们假设x y需要合并 那么他们的儿子也需要合并 这个过程时O(n^2)的

我们可以用类似spfa的技巧将这个过程优化到O(n)或者启发式的思想优化到O(nlog(n))

计算答案即可

我们dp即可

我们设计dp[i][j][0..1]的状态

dp[i][j][0] 表示从dp[i – 1][j]即从上面转移的方案数的和

dp[i][j][1] 表示从dp[i][j – 1]即从左边转移的方案数的和

进行转移即可

我们在状态中只考虑当前轮廓线的最后一个点和到达最后一个点的方式

通过这样的方式消除前效性

由于循环节范围太大，对t分解质因数 t = p1^q1 * p2^q2 * … * pk^qk 贡献可以分解成质因数p的q次方的贡献。

p的q次方的贡献 = q次p的贡献  因为p^q除1外刚好q个约数，可以等效算q次p的贡献

统计循环节是p^q倍数的排列数 = N! – 循环节没有p^q倍数的排列数

循环节没有p^q倍数的排列数 可以用动态规划解决