C - Swappable 171
数组中不相等的数对数量
D - KAIBUNsyo 879
每次操作可以把数组中等于 \(x\) 的数全变成 \(y\),问变成回文数组至少需要几次操作
简单的不错的并查集模拟题
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, a[N], p[N];
int get(int x) {
return x == p[x] ? x : p[x] = get(p[x]);
}
int main() {
iota(p, p + N, 0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0;
for (int i = 1; i <= n / 2; i++) {
int x = get(a[i]), y = get(a[n + 1 - i]);
if (x != y) {
ans++;
p[x] = y;
}
}
cout << ans;
return 0;
}
E - Divide Both 1745
统计 \([L,R]\) \((1e6)\) 之间公因数不是 \(1\),且皆不等于公因数的数对数量。
如果没有“两个数都不能等于公因数”这个要求,那做法就很简单:\(f(g)\) 表示 \([L,R]\) 中公因数为 \(g\) 的数对数量,从大到小递推,
\[f(g)=\left( \frac Rg - \frac{(L-1)}g \right)^2 - \sum_{g|x}f(x) \]现在多了点限制,答案稍微减点东西就行了
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll l, r, ans = 0;
cin >> l >> r;
vector<ll> f(r + 1);
for (int i = r; i >= 2; i--) {
ll cnt = r / i - (l - 1) / i;
f[i] = cnt * cnt;
for (int j = i + i; j <= r; j += i)
f[i] -= f[j];
ans += f[i];
if (i >= l) ans -= 2 * cnt - 1;
}
cout << ans;
return 0;
}
F - Interval Game 2 2221
100 个左闭右开区间 \([L,R), \ 1\le L< R\le100\),两人轮流操作,每次选择一个与之前已选区间都没有交集的区间,不能操作者输。
SG函数+区间dp 妙妙题!
不妨假设一开始的状态是 \([1,100)\),如果存在一个区间 \([x,y)\),我们就可以转移到一个由 \([1,x),[y,100)\) 组成的新状态。
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<pair<int, int>> seg(n);
for (auto &[x, y] : seg) {
cin >> x >> y;
}
vector<vector<int>> SG(101, vector<int>(101));
for (int len = 2; len <= 100; len++) {
for (int l = 1, r = l + len - 1; r <= 100; l++, r++) {
bitset<100> vis;
for (auto [x, y] : seg) { //枚举后继状态
if (l <= x && y <= r)
vis[SG[l][x] ^ SG[y][r]] = true;
}
while (vis[SG[l][r]]) SG[l][r]++; //求SG
}
}
cout << (SG[1][100] ? "Alice\n" : "Bob\n");
}
}
标签:abc206,int,cnt,cin,vector,using,公因数
From: https://www.cnblogs.com/wushansinger/p/17776846.html