abc388f

Gordon_Song · 2025-01-11 22:29:49 · 题解

有一个 O(nB) 的做法，设 dp_i 表示 i 是否可以到达。

然而，注意到只需要关注每一段区间前的 B 个和后 B 个位置的 dp 状态，其他的都可以用同余最短路找到规律（当然，由于 B 很小，也可以直接暴力）。所以复杂度降为 O(m B^2)。

code:

const int MAXN=2e4+5;
bool can[MAXN];
ll n,m,a,b,lcm,gcd;
int l[MAXN],r[MAXN];
vector<int>pos;
bool cou(int l,int r){
    if(r<=0||l<=0)return false;
    if(l>r)return false;
    if(r>n)return false;
    int len=r-l;
    if(len%gcd!=0){
        return false;
    }
    if(len>lcm)return true;
    return can[len];
}
bool check(int x){
    for(int i=0;i<pos.size();i++){
        if(cou(pos[i],x)){
            return true;
        }
    }return false;
}
bool check_(int x){
    for(int i=0;i<pos.size();i++){
        if(x-pos[i]>=a&&x-pos[i]<=b){
            return true;
        }
        if(pos[i]==x){
            return true;
        }
    }return false;
}
map<int,bool>mp;
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&l[i],&r[i]);
        if(l[i]+b<=r[i]){
            printf("No\n");
            return 0;
        }
        for(int j=l[i];j<=r[i];j++){
            mp[j]=true;
        }
    }   
    lcm=a*b/__gcd(a,b);
    gcd=__gcd(a,b);
    can[0]=true;
    for(int i=1;i<=lcm;i++){
        if(i>=a)can[i]|=can[i-a];
        if(i>=b)can[i]|=can[i-b];
    }pos.push_back(1);
    l[m+1]=n+1;
    for(int i=1;i<=m;i++){
        vector<int>t;
        for(int j=0;j<=b;j++){
            if(!mp[l[i]-j]&&check(l[i]-j)){
                t.push_back(l[i]-j);
            }
        }
        for(int j=0;j<pos.size();j++){
            if(pos[j]>r[i]){
                t.push_back(pos[j]);
            }
        }
        pos.clear();
        for(int j=0;j<t.size();j++)pos.push_back(t[j]);
        t.clear();
        for(int j=0;j<=b;j++){
            if(!mp[r[i]+j]&&check_(r[i]+j)){
                pos.push_back(r[i]+j);
                t.push_back(r[i]+j);
            }
        }
        pos.swap(t);
    }
    if(check(n)){
        printf("Yes");
    }else{
        printf("No");
    }
}