A. Subset Mex
贪心。
B. Maximum Product
负数的情况只可能为0个，2个或者4个，枚举一下这所有的情况然后取个最大值就行。
C. Link Cut Centroids
首先容易发现一颗树至多两个重心。
一个重心的情况好处理，任意添加一条边即可。
两个重心的情况对应着一条边为桥，并且左右两部分的点数相同。这种情况只需要任选一个叶子结点，然后将其添加入这条边的另外一个端点即可。易证不会再一次出现两个重心的情况。
Code
// Author : heyuhhh
// Created Time : 2020/09/12 22:07:43
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
int n;
cin >> n;
vector<vector<int>> G(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u, --v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> size(n), up(n);
int Max = INF, x = -1, y = -1;
function<void(int, int)> dfs = [&] (int u, int fa) {
up[u] = fa;
size[u] = 1;
for (auto& v : G[u]) if (v != fa) {
dfs(v, u);
size[u] += size[v];
}
int tot = 0;
int maxv = 0;
for (auto& v : G[u]) if (v != fa) {
tot += size[v];
maxv = max(maxv, size[v]);
}
maxv = max(maxv, n - 1 - tot);
if (Max > maxv) {
Max = maxv;
x = u, y = -1;
} else if (Max == maxv) {
y = u;
}
};
dfs(0, -1);
if (n & 1 || y == -1) {
cout << 2 << ' ' << up[1] + 1 << '\n';
cout << 2 << ' ' << up[1] + 1 << '\n';
return;
}
int lf;
for (auto v : G[x]) {
if (v != y) {
lf = v;
break;
}
}
cout << lf + 1 << ' ' << up[lf] + 1 << '\n';
cout << lf + 1 << ' ' << y + 1 << '\n';
}
int main() {
#ifdef Local
freopen("input.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
D. Three Sequences
问题转化过后直接维护 \(a\) 的差值就行，只有非负的差值会产生贡献。
Code
// Author : heyuhhh
// Created Time : 2020/09/13 09:42:29
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<ll> d(n);
ll sum = 0;
for (int i = 1; i < n; i++) {
d[i] = a[i] - a[i - 1];
if (d[i] >= 0)
sum += d[i];
}
auto get = [&] () {
ll res = sum + a[0];
if (res > 0)
return (res + 1) / 2;
return res / 2;
};
auto add = [&] (int p, int v) {
if (d[p] > 0) sum -= d[p];
d[p] += v;
if (d[p] > 0) sum += d[p];
};
cout << get() << '\n';
int q;
cin >> q;
while (q--) {
int l, r, x;
cin >> l >> r >> x;
--l, --r;
if (l)
add(l, x);
else
a[0] += x;
if (r + 1 < n)
add(r + 1, -x);
cout << get() << '\n';
}
}
int main() {
#ifdef Local
freopen("input.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
E. Deleting Numbers
题意：
交互题。
一开始给定一个数 \(n\)，会产生一个 \(\{1,2,\cdots,n\}\)这样的集合。然后要猜测一个数 \(x,x\leq n\)。
之后可以执行不超过 \(10000\) 次操作，操作有三种：
- \(A\ a\):表示询问集合中有多少个数为 \(a\) 的倍数；
- \(B\ b\):表示询问集合中有多少个数为 \(a\) 的倍数，并且在集合中把这些数删去。
- \(C\ x\)，用于回答 \(x\) 是多少。
最后就是通过第三种操作回答 \(x\)。
思路：
因为 \(n\leq 10^5\)，所以 \(x\) 至多有一个 \(\geq 330\) 的质因子，并且打表可以发现这个范围内大概有 \(9300\) 多个质因子，和询问总次数比较接近。
那么对于较小的那些质因子，显然可以直接暴力询问来计算，比如先询问 \(B\ p\)，再询问一次 \(A\ p\)看个数是否为 \(0\)，如果不为 \(0\) 说明 \(p\) 为其中一个质因子，然后再枚举 \(p\) 的次幂来询问。
对于较大的质因子，朴素的想法就是对每个质因子类似于刚刚那样询问两次，但显然总的操作次数不允许。注意到这其实是一个数量变化的关系，并且每次至多变化 \(1\)，那么其实可以对质因子进行分块，也就是说用 \(A\) 操作来统计总的个数，然后在 \(B\) 操作了一定数量的质因子过后，再通过 \(A\) 操作来统计次数。这样就能快速的知道质因子存在于哪一块，把总的询问次数降下来了。
注意还有一个细节，就是处理完较小的质因子过后，如果当前答案为 \(1\)，那么直接上面这样做是没问题的。但是如果答案不为 \(1\)，直接上面那样做可能会有问题。因为比如说 \(n=x=6\)，那么我处理较大质因子时数量的变化是正确的，因为每次我只会删掉当前这个质数，但是不能找到答案。所以这种情况需要特殊处理。
详见代码：
Code
// Author : heyuhhh
// Created Time : 2020/09/13 10:20:40
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
int primes[N], tot;
bool vis[N];
void init(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
primes[++tot] = i;
}
for (int j = 1; j <= tot && primes[j] * i <= n; j++) {
vis[primes[j] * i] = true;
if (i % primes[j] == 0) {
break;
}
}
}
}
void run() {
int n;
cin >> n;
init(n);
int t = 1;
while (t * t <= n) ++t;
auto query = [&] (ll x, int op = 1) {
if (x > n) return 0;
if (op == 1)
cout << "B " << x << endl;
else
cout << "A " << x << endl;
cout << endl;
int y; cin >> y;
return y;
};
int p = 1;
int ans = 1;
for (; p <= tot && primes[p] < t; p++) {
query(primes[p]);
int x = query(primes[p]);
if (x) {
int now = primes[p] * primes[p];
for (int i = 2; now / primes[p] <= n; now *= primes[p]) {
if (!query(now)) {
ans *= now / primes[p];
break;
}
}
}
}
if (ans != 1) {
for (; p <= tot; p++) {
int x = query((ll)ans * primes[p]);
if (x > 0) {
ans *= primes[p];
break;
}
}
} else {
int B = 95;
int last = query(1, 2);
for (int cnt = 0; p <= tot; ++p) {
query(primes[p]);
if (++cnt == B || p == tot) {
int now = query(1, 2);
if (last - now != cnt) {
for (int i = p - cnt + 1; i <= p; i++) {
int x = query(primes[i]);
if (x) {
cout << "C " << ans * primes[i] << endl;
return;
}
}
}
last = now;
cnt = 0;
}
}
}
cout << "C " << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}