1月USACO计算机竞赛'金牌'解题分析！附备考资料领取！

01

Au1:

算法：二分，观察性质

首先假设当前在x轴朝向上行走，什么时候会转向到y轴？

我们发现当且仅当当前道路距离下一条道路是奇数距离的时候会转向

于是我们可以考虑去二分转向的次数，计算出在当前转向次数下运动的距离，判断它是否小于等于题目给出的运动距离

代码实现较为复杂，需要注意细节

时间复杂度: $O((n+q)*log)

Au2:

算法：动态规划

和银组第一题类似

定义$i$这个位置是前缀最大值当且仅当$a[i]>a[j]$ (for all $1le j<i$)< p="">

我们会发现对于某个$(a[i],h[i])$相当于要求$[a[i]+1,h[i]-1]$这一段不能是前缀最大值，$h[i]$这个位置必须是前缀最大值

最终我们将相同情况的序列合并在一起，那么就是有最多$3*Q$段的序列（每一段内部要么要求一定是前缀最大值/一定不是前缀最大值/没有要求），求最终合法的方案数

定义$dp[i][j]$代表当前考虑到前$i$段数，选的数的最大值是$j$的方案数

假设当前这一段序列长度为$len$

当一定是前缀最大值时:

$dp[i][j]=sum_{k=1}^{j-1} dp[i-1][k]$

当一定不是前缀最大值时:

$dp[i][j]=dp[i-1][j]*j^{len}$

当没有要求时：

$dp[i][j]=dp[i-1][j]j^{len} + sum_{k=1}^{j-1} dp[i-1][k](j^{len} -(j-1)^{len})$

时间复杂度: $O(qclog)$

Au3:

算法：二分

注意到分给Bessie自己的数越多答案相应的会越大，但是会越容易满足题目限制

所以我们考虑去二分 分给Bessie的个数$mid$

那么它们分别被加入序列的时间就是$mid, mid + (mid-1) ,... , mid+...+1$

显然我们比较希望尽量靠后的数能被加入到Bessie的序列中，所以对于每一个加入序列的时间我们可以贪心的去找到第一个大于当前时间且没有被插入到序列中的数，将它插入到序列中

这个过程可以用类似于双指针的思想来优化

最终$min(数字最大值,mid*(mid+1)/2)$就是我们的答案

时间复杂度: $O(n*log)$

02