2023牛客暑期多校训练营6个人补题题解（G、E）

G-Gcd

题目大意：

给出两个元素a和b（）组成数集，每次操作可以进行如下任一操作：

1.选取S集合中的两个元素，向数组中插入元素

2.选取S集合中的两个元素，向数组中插入元素

规定==

求能否在若干次操作后使

思路：

1）当初始=或=时,不用进行任何操作就能满足题意

2）当初始=且不满足（1）时，由于每次操作选取，永远无法被插入。

3）除此之外的情况，由贝祖定理可得，设是不全为零的整数，则存在整数使+=，所以%==时满足题意

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
     
    int t;
    cin>>t;
    while(t--){
        ll x,y,z;
        cin>>x>>y>>z;
        ll temp = gcd(x,y);
        if(z==x || z==y){
            cout<<"YES"<<"\n";
        }
        else if(z==0)
            cout<<"NO"<<'\n';
        else{
            if(z%temp == 0)
                cout<<"YES"<<"\n";
            else
                cout<<"NO"<<"\n";
        }
    }
    return 0;
}

E-Sequence

大致题意：

给定含有个元素的数组和询问次数，每次询问给出

询问是否能找到含有个元素的递增下标数组满足 ++都是偶数。

定义=

大致思路：

用数组记录数组的前缀和，用和数组分别记录数组的奇偶前缀和数量的前缀和。 对于每一组样例，当且是奇数时，下标范围内每有一个前缀和为奇数的区间意味着出现一个和是偶数的子区间。判断

同理，当且是偶数时，下标范围内每有一个前缀和为偶数的区间意味着出现一个和为偶数的子区间。判断

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int a[N];
int sum[N];
int cnt1[N];
int cnt2[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >>t;
    while(t--)
    {
        int n,q;
        cin >>n>>q;
        for(int i=1;i<=n;i++){
            cin >>a[i];
            sum[i]=sum[i-1]+a[i];
            cnt1[i]=cnt1[i-1]+(sum[i]%2==1);
            cnt2[i]=cnt2[i-1]+(sum[i]%2==0);
        }
        while(q--)
        {
            int l,r,k;
            cin >>l>>r>>k;
            if(sum[l-1]%2==0&&sum[r]%2==0&&(cnt2[r]-cnt2[l-1])>=k)
                cout<<"YES"<<'\n';
            else if(sum[l-1]%2==1&&sum[r]%2==1&&(cnt1[r]-cnt1[l-1])>=k)
                cout<<"YES"<<'\n';
            else cout<<"NO"<<'\n';
        }
    }
    return 0;
}