ABC F wa*3 求调
  • 板块题目总版
  • 楼主__vector__
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/12 08:20
  • 上次更新2025/1/12 08:48:40
查看原帖
ABC F wa*3 求调
507348
__vector__楼主2025/1/12 08:20

赛时就这样,不知道咋回事 /ll

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=2e4+5;
ll n;
int m;
int a,b;
pll _seqs[maxn];
pll seq[maxn];
bool ok[maxn*10];
bool dp[maxn][25];
void solve(int id_of_test){
	read(n);
    read(m);
    read(a);
    read(b);
    ok[0]=1;
    FOR(i,1,maxn*10-1){
        FOR(j,a,b){
            if(i-j>=0){
                ok[i]|=ok[i-j];
            }
        }
    }
    FOR(i,1,m){
        read(_seqs[i].fi);
        read(_seqs[i].se);
    }
    int cnt=0;
    FOR(i,1,m){
        if(_seqs[i].fi-_seqs[i-1].se-1>=1){
            ++cnt;
            seq[cnt].fi=_seqs[i-1].se+1;
            seq[cnt].se=_seqs[i].fi-1;
        //    printf("[%d,%d] ",seq[cnt].fi,seq[cnt].se);
        }
    }
    ++cnt;
    seq[cnt].fi=_seqs[m].se+1;
    seq[cnt].se=n;
  //  printf("[%d,%d] ",seq[cnt].fi,seq[cnt].se);
  //  pln
    dp[1][0]=1;
    // 
    FOR(i,1,cnt){
        FOR(s,0,b){
            // 枚举出发点是起点之后多少个位置
            if(!dp[i][s])continue;
           // printf("ok %d %d\n",i,s);
            // 枚举,先到达当前区间终点前多少个位置
                FOR(j,0,b){
                    ll len=seq[i].se-j-(seq[i].fi+s);
                    // 距离 
                    if(len<0)continue;
                    bool chk=0;
                    if(a!=b){
                        if(len>=maxn*10)chk=1;
                        else{
                            chk=ok[len];
                        }
                    }else{
                        if(len%a==0)chk=1;
                    }
                    if(chk){
                    //    printf("reach %d\n",seq[i].se-j);
                        // 可以到达,现在计算下一个区间的 dp
                        if(seq[i].se-j==n){
                            puts("Yes");
                            exit(0);
                        }
                        if(i==cnt)continue;
                        FOR(nxt,0,b){
                            if(seq[i+1].fi+nxt>seq[i+1].se)break;
                            // 达到下一个的
                            ll cha=seq[i+1].fi+nxt-(seq[i].se-j);
                       //     printf("nxt %d cha %d\n",seq[i+1].fi+nxt,cha);
                            if(cha>=a&&cha<=b){
                                dp[i+1][nxt]=1;
                            }
                        }
                    }
                }
        }   
    }
    puts("No");
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}

2025/1/12 08:20
加载中...