USACO 2020 US Open已经结束了，
不知道同学们考的怎么样呢？
01
02
R表示疾病的传播半径 如果两个人距离小于R即会被传染
我们发现如果相邻的两个人 一个人传染一个人不传染 那么R不应该大于这两个人的距离
当求出最大的R以后 我们即可求出答案
03
01
即D越小越容易符合题意
二分答案即可
02
然后每个数只会挪动两次位置
所以总体复杂度O（n）
03
然后确保了 后出现的x更小
然后进行块合并即可
01
我们发现 当我们插入一个数时 前面还没有插的位置 此后一定比当前数大
所以使用树状数组统计即可
02
我们发现一个点的儿子都需要合并
我们假设x y需要合并 那么他们的儿子也需要合并 这个过程时O(n^2)的
我们可以用类似spfa的技巧将这个过程优化到O(n)或者启发式的思想优化到O(nlog(n))
03
计算答案即可
Platinum赛题
01
我们dp即可
我们设计dp[i][j][0..1]的状态
dp[i][j][0] 表示从dp[i – 1][j]即从上面转移的方案数的和
dp[i][j][1] 表示从dp[i][j – 1]即从左边转移的方案数的和
进行转移即可
我们在状态中只考虑当前轮廓线的最后一个点和到达最后一个点的方式
通过这样的方式消除前效性
02
由于循环节范围太大，对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倍数的排列数 可以用动态规划解决
03
