D
题目大意：给定长度为 $n$ 的数组 $a$ ，求最小的 $x$ ，使得存在某个 $i$ 满足 $\gcd(a_i,x)=1$ 。如果 $[2,10^{18}]$ 内不存在这样的 $x$ ，输出 $-1$ 。
数据范围：$1 \leq t \leq 10^4, 1 \leq n \leq 10^5, 1 \leq a_i \leq 10^{18}, \sum n \leq 10^5$
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| constexpr int M = 1e5 + 5;
bool is_prime[M];
vector<int> primes;
auto init = [] {
ranges::fill(is_prime, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i < M; i++) {
if (is_prime[i]) {
primes.push_back(i);
for (ll j = 1LL * i * i; j < M; j += i) {
is_prime[j] = false;
}
}
}
return 0;
}();
// 函数指针在创建时自动调用
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll res = LLONG_MAX;
rep(i, 0, n - 1) {
for (int& p : primes) {
if (a[i] % p != 0) {
res = min(res, 1LL * p);
break;
}
}
}
cout << (res == LLONG_MAX ? -1 : res) << endl;
return;
}
|
E
题目大意：给定 $n$ 个朋友在 $[0,x]$ 上的位置 $a_i$ ，需要选择 $k$ 个互不相同的传送点，也位于 $[0,x]$ 内。最大化所有朋友到最近传送点距离的最小值，并输出任意一组最优传送点。
数据范围：$1 \leq t \leq 10^4, 1 \leq n,k \leq 2 \cdot 10^5, k-1 \leq x \leq 10^9, 0 \leq a_i \leq x, \sum n \leq 2 \cdot 10^5, \sum k \leq 2 \cdot 10^5$
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| void solve() {
ll n, k, x;
cin >> n >> k >> x;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
ll l = 0, r = 1e9, mid, ans = 0;
auto check = [&](ll mid) -> bool {
ll res = 0;
rep(i, 0, n - 1) {
if (i == 0) {
res += max(0LL, a[i] - mid + 1);
}
if (i != n - 1) {
res += max(0LL, a[i + 1] - a[i] - 2 * mid + 1);
} else {
res += max(0LL, x - a[i] - mid + 1);
}
}
return res >= k;
};
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
if (ans == 0) {
rep(i, 0, k - 1) cout << i << ' ';
return;
}
vl res(k);
int idx = 0;
rep(i, 0, n - 1) {
if (i == 0) {
for (int j = 0; j <= a[i] - ans && idx < k; j++) res[idx++] = j;
}
if (i == n - 1) {
for (int j = a[i] + ans; j <= x && idx < k; j++) res[idx++] = j;
} else {
for (int j = a[i] + ans; j <= a[i + 1] - ans && idx < k; j++) res[idx++] = j;
}
}
rep(i, 0, k - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
F
题目大意：给定一棵 $n$ 点树和整数 $k$ 。对每个根 $r$ ，考虑所有大小为 $k$ 的点集在以 $r$ 为根时的 LCA 集合 $S_r$ ，求 $\sum_{r=1}^{n}|S_r|$ 。
数据范围：$1 \leq t \leq 10^4, 2 \leq k \leq n \leq 2 \cdot 10^5, 1 \leq u,v \leq n, \sum n \leq 2 \cdot 10^5$
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| void solve() {
ll n, k, x, y;
cin >> n >> k;
vvi ma(n);
rep(i, 1, n - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
}
vl siz(n);
auto dfs = [&](this auto&& dfs, int x, int pa) -> void {
ll tem = 1;
for (int& p : ma[x]) {
if (p == pa) continue;
dfs(p, x);
tem += siz[p];
}
siz[x] = tem;
return;
};
dfs(0, -1);
vl res(n);
rep(i, 0, n - 1) res[0] += (siz[i] >= k);
auto dfs2 = [&](this auto&& dfs2, int x, int pa) -> void {
for (int& p : ma[x]) {
if (p == pa) continue;
res[p] = res[x];
if (siz[p] < k) res[p]++;
if (n - siz[p] < k) res[p]--;
dfs2(p, x);
}
};
dfs2(0, -1);
ll ans = 0;
rep(i, 0, n - 1) ans += res[i];
cout << ans << endl;
return;
}
|
G
题目大意：给定数组 $a$ 和修改费用 $c$ 。可以选择任意位置 $i$ ，花费 $c_i$ 后把 $a_i$ 改成任意整数；未修改的位置保持原值。求使最终数组非递减的最小费用。
数据范围：$1 \leq t \leq 5000, 1 \leq n \leq 8000, 1 \leq a_i,c_i \leq 10^9, \sum n \leq 8000$
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl c(n);
rep(i, 0, n - 1) cin >> c[i];
vl pre(n + 1);
rep(i, 1, n) pre[i] = pre[i - 1] + c[i - 1];
vl dp(n + 1, LLONG_MAX / 3);
dp[0] = 0;
ll ans = LLONG_MAX / 3;
rep(i, 1, n) {
dp[i] = pre[i - 1];
rep(j, 1, i - 1) {
if (a[j - 1] <= a[i - 1]) dp[i] = min(dp[i], dp[j] + pre[i - 1] - pre[j]);
}
}
rep(i, 0, n) { ans = min(ans, pre[n] - pre[i] + dp[i]); }
cout << ans << endl;
return;
}
|
