USACO open 2024 铂金组 T3

· · 题解

如果你通关铂金组了，那么你就没有贝提拔的机会了。

难道这道题就我需要卡常吗？虽然我知道有复杂度更优的做法。

考虑将状态压缩到极致，设 f_{S,x} 表示集合 S 的位置被放置了，最后一个放置的位置是 x 的最早时间。

这个状态也压缩了当前的人的位置，这样之所以不会漏情况，是因为人不比 robotto 慢，所以能在一个较早的时刻达到该状态就一定能在较晚的时刻到达。

每次考虑新放置的 robotto，这是有两种情况，也就是小学奥数中的相遇问题和追及问题，我们可以暂时忽略关键点的限制，从相遇和追及的角度找到该 robotto 和人的最早相遇时间，然后 std::lower_bound 求出相遇后碰到的第一个关键点即可。

这里时间复杂度 O(R^22^R\log n)，理论上擦边能过，但我刚开始写的代码常数太大，于是考虑如何卡常。

发现比最终答案早的状态（一般只能卡到）O(2^R) 个，考虑使用优先队列维护 dp，这样一般数据的复杂度是 O(R2^R(R+\log n)) 的，可以通过。

欢迎 Hack，不过后面卡了常所以直接转移也能过：

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<19)+100;
int n,L,R,a[N],f[N*23],K,ans,v1,v2,cntt;
int dst(int l,int r){
    l=abs(l-r);
    return min(l,L-l);
}
priority_queue<pair<int,int>>q1;
bitset<N*23>vs;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int i,j,k,l,r,x,y,z,p,q;
    cin>>L>>R>>n>>K;
    for(x=1;x<=n;++x)cin>>a[x];
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    a[n+1]=a[1]+L;
    for(k=0;k<(1<<R-1);++k)
        for(x=0;x<R;++x)f[k*R+x]=L+L+1;
    q1.emplace(f[0]=0,0);
    ans=L+L+1;
    while(1){
        x=q1.top().second,q1.pop();
        if(vs[x])continue;
        vs[x]=1,v1=f[x],k=x/R,x%=R;
        p=(v1+x*(L/R))%L;
        if(k==(1<<R-1)-1){
            printf("%lld\n",1ll*v1*K);
            return 0;
        }
        for(y=1;y<R;++y){
            if((k>>y-1)&1)continue;
            q=(v1+y*(L/R))%L;
            v2=((p-q+L)%L+K)/(K+1);
            if(K>1){
                if(q<p)q+=L;
                v2=min(v2,(q-p-1)/(K-1)+1);
            }
            r=(k|(1<<y-1))*R+y,v2+=v1;
            q=(v2+y*(L/R))%L;
            v2+=*lower_bound(a+1,a+n+1,q)-q;
            if(f[r]>v2)q1.emplace(-(f[r]=v2),r);
        }
    }
}