Lut本科回忆录

更新至G,E…
有点多愁善感了

题G

题意：给定一个初始集合其中仅有 $x,y(x!=y)$, 可以执行任意次以下两种操作

1、选择a,b(a!=b),往集合中添加a-b
2、选择a,b(a!=b),往集合中添加gcd(|a|,|b|)

问最终能否得到$z$

解:当 $z=0$ 时，仅有 $a=0或b=0$时，可以直接得到目标值，否则无法通过相减不同值得到 $0$
当 $z!=0$ 时，我们通过 $gcd(a,b)$ 可以得到一系列 $gcd(a,b)$ 的倍数，如果能整除就存在.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    while(T --){
        int a, b, c; cin >> a >> b >> c;
        if(c == 0){
            if(a == 0 || b == 0) cout << "YES\n";
            else cout << "NO\n";
        }
        else if(c % __gcd(a, b) == 0) cout << "YES\n";
        else cout << "NO\n";
    }
}

题E

题意：给定一个长为 $n$ 的数组 $a$，每次询问给定 $l,r,k$，问能否将 $l-r$ 的区间划分为 $k$ 个部分，且每个部分的和都是偶数 $(1\le n,q \le 10^5, 0\le a_i \le 10^{10}, 1\le l \le r \le n, 1 \le k \le 10^5)$。

解：因为要满足划分后的每个部分和都是偶数，那么我们可以直接从左到右扫描前缀和，统计到当前的前缀和的偶数和个数和奇数和个数，当且仅当一个区间内的和为偶数且两个奇偶性前缀差 $\ge k$。

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int, int>
#define INF 1ll << 30
#define ll long long
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
int st[N], s[N];
void solve(){
    int n, q, t = 0; cin >> n >> q;
    for(int i = 1, a = 0, b = 0; i <= n; ++ i){
        int x; cin >> x; 
        s[i] = s[i - 1] + x;
        if(s[i] & 1) st[i] = ++ a;
        else st[i] = ++ b;
    }
    while(q --){
        int l, r, k; cin >> l >> r >> k;
        if((s[r] - s[l - 1]) % 2 == 0 && (st[r] - st[l - 1]) >= k) 
            cout << "YES\n"; 
        else cout << "NO\n";
    }
}
int main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    while(n--) solve();
    return 0;
}