Codeforces Round 969 (Div. 2)

传送门

A.

题意：集合里有 \([l, r]\)，每次操作选择集合中三个互质的不同的整数并从集合中删除，最多可以进行多少次操作

\(gcd(i, i + 1) = 1\)，每次选择相邻的三个数，且第一个数为奇数，这样保证这三个数一定互质，判断 \(l\) 和 \(r\)，统计个数即可。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 7;
void solve() {
    int l, r;
    cin >> l >> r;
    int p = (r - l + 1);
    if(r % 2 == 1) p ++;
    cout << p / 4 << endl;
}
int main() {
    int T;
    cin >> T;
    while(T --) solve();
}

B.

不难发现操作若干次后最大值的位置不变，比较好证明，模拟即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 7;
int a[N];
void solve() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int mx = 0;
    for(int i = 1; i <= n; i ++) mx = max(mx, a[i]);
    for(int i = 1; i <= m; i ++) {
        string s;
        int l, r;
        cin >> s >> l >> r;
        if(s == "+") {
            if(mx >= l && mx <= r) mx ++;

        }
        else {
            if(mx >= l && mx <= r) mx --;
        }
        cout << mx << " ";
    }
    cout << endl;
}
signed main() {
    int T;
    cin >> T;
    while(T --) solve();
}

C.

\(+ A, + B\) 等价于 \(\pm k \gcd(A, B)\)，在模 \(\gcd(A, B)\) 找差的最小的即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 7;
int c[N];
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i ++) cin >> c[i];
    int d = __gcd(a, b);
    for(int i = 1; i <= n; i ++) c[i] %= d;
    sort(c + 1, c + n + 1);
    int ans = c[n] - c[1];
    for(int i = 1; i < n; i ++) {
        ans = min(ans, c[i] - c[i + 1] + d); 
    }
    cout << ans << endl;
}
signed main() {
    int T;
    cin >> T;
    while(T --) solve();
}

D.

一条链的权值只与链的两个端点有关，若根不为 ?，答案即为 \(sumx / 2\)，其中 \(sumx\) 为叶子中 ? 的个数。

否则要判断两种情况哪一个获得权值最大，稍微有点细节。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 7;
vector<int> g[N];
int p[N], cnts, cnt0, cnt1;
int owo;
string s;
void dfs(int u, int fa) {
	int cnt = 0;
	for(int v : g[u]) {
		if(v == fa) continue;
		dfs(v, u);
		cnt ++;
	}
	if(!cnt) {
		if(s[u] == '?') cnts ++;
		else if(s[u] == '0') cnt0 ++;
		else cnt1 ++;
	}
	else if(u != 1 && s[u] == '?') {
		owo ++;
	}
}
void solve() {
	cnt1 = cnt0 = cnts = owo = 0;
	int n;
	cin >> n;
	for(int i = 0; i <= n; i ++) g[i].clear();
	for(int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v), g[v].push_back(u);
		
	}
	cin >> s;
	s = ' ' + s;
	dfs(1, 0);
	if(s[1] != '?') {
		if(s[1] == '1') {
			cout << cnt0 + (cnts + 1) / 2 << endl;
		}
		else cout << cnt1 + (cnts + 1) / 2 << endl;
	} 
	else {
		if(cnt1 ^ cnt0) {
			cout << max(cnt1, cnt0) + cnts / 2 << endl;
		}
		else {
			cout << (cnt0 + cnt1 + cnts + (owo & 1)) / 2 << endl;
		}
	}
	
}
int main() {
	int T;
	cin >> T;
	while(T --) solve();
}

E.