牛客小白月赛84

题目描述

小蓝非常喜欢玩FPS类游戏，最近他迷上了一款打靶游戏，已知总共会出现?n\mathit nn?个靶子，每次开枪如果打中了靶子则会得到?1\text 11?分，另外不论这次开枪打中与否，靶子都将消失，现在有?m\mathit mm?个靶子已经出现过（出现过的靶子不会再出现），现在小蓝已经得到了?X\mathit XX?分，小蓝想知道他是否有可能最终分数为?Y\mathit YY?。

输入描述:

第一行包含一个整数?T(1≤T≤100)T (1 \leq T \leq 100 )T(1≤T≤100)?，表示测试用例的组数。

对于每组测试用例：

输入一行包含四个整数?n,m,X,Y(1≤m≤n≤106,0≤X≤m,0≤Y≤109)n,m,X,Y( 1 \leq m \leq n \leq 10^6,0 \leq X \leq m,0 \leq Y \leq 10^9)n,m,X,Y(1≤m≤n≤106,0≤X≤m,0≤Y≤109)?。

输出描述:

对于每组测试用例：

输出一个字符串，若小蓝想最终分数有可能为?Y\mathit YY?则输出?"Yes" ，否则输出?"No" (不带引号)。

示例1

输入

3
5 3 1 3
5 3 2 3
5 3 1 4

输出

Yes
Yes
No

void sol(){
    int n,m,x,y;cin>>n>>m>>x>>y;
    cout<<(n-m>=y-x&&x<=y?"Yes":"No")<<endl;
}

题目描述

又到了上数学课的日子，老师在讲台上面讲课，问了一个问题，现有?a,ba,ba,b?两正整数，给定 gcd(a,b)gcd(a,b)gcd(a,b)?和 lcm(a,b)lcm(a,b)lcm(a,b)?，问能否求得 a,ba,ba,b?两正整数，恰好数学老师看到这时候小蓝在课堂上睡觉，于是数学老师点名提问了小蓝，小蓝想向你求助答案，如果有多对合法的?a,ba,ba,b?，输出 a\mathit aa?最小的那一对答案，若仍然有多个?a\mathit aa?最小的答案对，输出?a\mathit aa?最小且?b\mathit bb?最小的答案，否则输出 "-1" (不带引号)。

输入描述:

第一行包含一个整数?T(1≤T≤100)T (1 \leq T \leq 100)T(1≤T≤100)?，表示测试用例的组数。

对于每组测试用例：

输入一行包含两个整数 X,Y(1≤X,Y≤105)X,Y (1 \leq X,Y \leq 10^5)X,Y(1≤X,Y≤105)?分别表示?gcd(a,b)gcd(a,b)gcd(a,b)?和?lcm(a,b)lcm(a,b)lcm(a,b)?。

输出描述:

对于每组测试用例：

仅输出一行。若有合法的?a,ba,ba,b?则输出两个数表示答案。否则输出?"-1" (不带引号)。

void sol(){
    int x,y;cin>>x>>y;
    if(y%x!=0) return cout<<-1<<endl,void();
    cout<<x<<" "<<y<<endl;
}

题目描述

小蓝得到了一个长度为?n\mathit nn?的序列?a\mathit aa?，以及一个非负整数?k\mathit kk?，小蓝想知道是否存在一个长度为?n\mathit nn?的序列?b\mathit bb?使得??1≤i≤n,∣ai?bi∣≤k\forall 1\leq i \leq n,\left| a_i-b_i \right| \leq k?1≤i≤n,∣ai??bi?∣≤k?均满足并且?b\mathit bb?序列非降序。

我们称一个长度为?n\mathit nn?的序列?b\mathit bb?非降序当且仅当对于??2≤i≤n,bi?1≤bi\forall 2 \leq i \leq n,b_{i-1} \leq b_i?2≤i≤n,bi?1?≤bi??均满足。

输入描述:

第一行包含一个整数?T(1≤T≤105)T (1 \leq T \leq 10^5)T(1≤T≤105)?，表示测试用例的组数。

对于每组测试用例：

第一行输入两个整数?n,k(1≤n≤2?105,0≤k≤109)n,k (1 \leq n \leq 2 · 10^5,0 \leq k \leq 10^9 )n,k(1≤n≤2?105,0≤k≤109)?。

第二行输入?nnn?个整数表示序列?a(?109≤ai≤109)a (-10^9 \leq a_i \leq 10^9)a(?109≤ai?≤109)?。

保证?∑i=1Tn≤106\sum_{i=1}^{T}{n} \leq 10^6∑i=1T?n≤106?。

输出描述:

对于每组测试用例：

输出一个字符串，若存在序列?b\mathit bb?则输出?"Yes"?，否则输出?"No"?(不带引号)。

void sol(){
    int n,k;cin>>n>>k;
    vector<ll> a(n+1),b(n+1);
    b[0]=-1e18;

    rep(i,1,n) cin>>a[i];

    rep(i,1,n) {
        ll l=max(b[i-1],a[i]-k),r=a[i]+k;
        if(l>r) return cout<<"No"<<endl,void();
        b[i]=l;
    }

    cout<<"Yes"<<endl;
}

题目描述

对于第?i\mathit  ii?个询问，输出一个整数表示将区间?[l,r][ \mathit l, \mathit r][l,r]?翻转后，整个?010101?串中连续?1\text 11?的段数。

void sol(){

    int n,q;cin>>n>>q;
    string s;cin>>s;
    s+='0';

    int cnt=0;
    rep(i,1,n) if(s[i]=='0'&&s[i-1]=='1') cnt++;


    while(q--) {
        int L,R;cin>>L>>R;
        L--,R--;
        if(s[L]==s[R]) 
            cout<<cnt<<endl;
        else if(s[L]=='0') {
            int ans=cnt;
            if(L>0&&s[L-1]=='1') ans--;
            if(R<n-1&&s[R+1]=='1') ans++;
            cout<<ans<<endl;
        }
        else if(s[R]=='0') {
            int ans=cnt;
            if(L>0&&s[L-1]=='1') ans++;
            if(R<n-1&&s[R+1]=='1') ans--;
            cout<<ans<<endl;
        }
    }
}

void sol(){
    int n;cin>>n;

    vector<ll> a(n+1);
    rep(i,1,n) cin>>a[i];

    if(n==1) {
        if(a[1]==0) cout<<"Dog"<<endl;
        else cout<<(a[1]%2==1?"Dog":"Cat")<<endl;
    }
    else if(n==2) {
        if(abs(a[1]-a[2])!=1||max(a[1],a[2])==1) cout<<"Dog"<<endl;
        else cout<<"Cat"<<endl;
    }
    else {
        int cnt=count(all(a),0)-1;
        ll sum=-n+((n+1)/2-1);//减去 1 的数量
        for(int x:a) sum+=x;

        if(cnt*2>=n) cout<<"Dog"<<endl;
        else cout<<(sum%2==1?"Dog":"Cat")<<endl;
    }
}

如果有解，则输出一个长度为?n\mathit nn?的字符串表示答案，如果有多个答案 输出任意一个即可。否则输出?"-1" (不带引号)。

void sol(){
    int n;cin>>n;
    vector<int> f(n);
    rep(i,1,n-1) cin>>f[i];
    
    string s;
    auto check=[&](int fl)->bool {
        s=string(n,'0');
        rep(i,0,(n-1)/2+1) if(fl>>i & 1) s[i]='1';

        per(len,n-1,1) {
            int cnt=0;
            for(int i=0,j=len;j<n;i++,j++) 
                if(s[i]=='0'&&s[j]=='1') cnt++;       

            if(cnt!=f[len]) {
                if(len>=(n-1)/2+1&&cnt==f[len]-1&&s[0]=='0') s[len]='1';
                else return false;
            }
        }

        return true;
    };

    for(int i=0;i<(1<<((n-1)/2+1));i++) 
        if(check(i)) return cout<<s<<endl,void();

    cout<<-1<<endl;
}