2026夏个人训练赛第十七场
A. 点名
开线段树二分。
cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 30010;
int tr[N * 4];
long long a[N];
vector<long long> values;
void modify(int u, int l, int r, int p, int v) {
if (l == r) tr[u] += v;
else {
int mid = l + r >> 1;
if (p <= mid) modify(u << 1, l, mid, p, v);
else modify(u << 1 | 1, mid + 1, r, p, v);
tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
}
int query(int u, int l, int r, int t) {
if (l == r) return l;
else {
int mid = l + r >> 1;
if (t <= tr[u << 1]) return query(u << 1, l, mid, t);
else return query(u << 1 | 1, mid + 1, r, t - tr[u << 1]);
}
}
void print(int u, int l, int r) {
if (l == r) cout << tr[u] << ' ';
else {
int mid = l + r >> 1;
print(u << 1, l, mid), print(u << 1 | 1, mid + 1, r);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
values.emplace_back(a[i]);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
int m = values.size();
for (int i = 1, j = 1; i <= q; ++i) {
int r;
cin >> r;
while (j <= r) {
modify(1, 1, m, lower_bound(values.begin(), values.end(), a[j]) - values.begin() + 1, 1);
j++;
// print(1, 1, m);
// cout << endl;
}
cout << values[query(1, 1, m, i) - 1] << endl;
}
return 0;
}B. 巧克力
找到两条不相交的链求和的最大值，我这里写的有点混乱了。我的思路是钦定根一定在一条链上，那么还需要选两个儿子的链和一条完整的字数的链，可以通过换根 DP 钦定根节点。
cpp
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 100010;
int head[N], ver[N * 2], ne[N * 2], tot;
LL a[N], f[N][2], g[N], res;
void add(int x, int y) {
ver[++tot] = y;
ne[tot] = head[x];
head[x] = tot;
}
void dp(int x, int fa) {
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (y == fa) continue;
dp(y, x);
if (f[y][0] + a[y] >= f[x][0]) f[x][1] = f[x][0], f[x][0] = f[y][0] + a[y];
else if (f[y][0] + a[y] > f[x][1]) f[x][1] = f[y][0] + a[y];
g[x] = max(g[x], g[y]);
}
g[x] = max(g[x], f[x][0] + f[x][1] + a[x]);
}
void dfs(int x, int fa) {
priority_queue<PII, vector<PII>, greater<PII>> q1, q2;
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (q1.size() < 3) q1.emplace(f[y][0] + a[y], y);
else if (f[y][0] + a[y] > q1.top().first) q1.pop(), q1.emplace(f[y][0] + a[y], y);
if (q2.size() < 2) q2.emplace(g[y], y);
else if (g[y] > q2.top().first) q2.pop(), q2.emplace(g[y], y);
}
vector<PII> v1, v2;
while (!q1.empty()) v1.emplace_back(q1.top()), q1.pop();
while (!q2.empty()) v2.emplace_back(q2.top()), q2.pop();
for (int i = 0; i < v1.size(); ++i) {
for (int j = 0; j < v1.size(); ++j) {
for (int k = 0; k < v2.size(); ++k) {
if (v1[i].second == v1[j].second && v1[i].second == v2[k].second) res = max(res, v2[k].first + a[x]);
else if (v1[i].second == v1[j].second) res = max(res, max(v1[i].first, v1[j].first) + v2[k].first + a[x]);
else if (v1[i].second == v2[k].second) res = max(res, v1[j].first + v2[k].first + a[x]);
else if (v1[j].second == v2[k].second) res = max(res, v1[i].first + v2[k].first + a[x]);
else res = max(res, v1[i].first + v1[j].first + v2[k].first + a[x]);
}
}
}
LL bk[3] = {f[x][0], f[x][1], g[x]};
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (y == fa) continue;
LL t;
LL bk2[3] = {f[y][0], f[y][1], g[y]};
if (f[x][0] == f[y][0] + a[y]) t = f[x][1];
else t = f[x][0];
if (t + a[x] >= f[y][0]) f[y][1] = f[y][0], f[y][0] = t + a[x];
else if (t + a[x] > f[y][1]) f[y][1] = t + a[x];
g[y] = max(g[y], f[y][0] + f[y][1] + a[y]);
f[x][0] = f[x][1] = 0;
g[x] = 0;
for (int i = 0; i < v1.size(); ++i) {
if (v1[i].second == y) continue;
if (v1[i].first >= f[x][0]) f[x][1] = f[x][0], f[x][0] = v1[i].first;
else if (v1[i].first > f[x][1]) f[x][1] = v1[i].first + a[v1[i].second];
g[x] = max(g[x], g[v1[i].second]);
}
g[x] = max(g[x], f[x][0] + f[x][1] + a[x]);
dfs(y, x);
f[x][0] = bk[0], f[x][1] = bk[1], g[x] = bk[2];
f[y][0] = bk2[0], f[y][1] = bk2[1], g[y] = bk2[2];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i < n; ++i) {
int x, y;
cin >> x >> y;
add(x, y), add(y, x);
}
dp(1, 0);
dfs(1, 0);
cout << res << endl;
return 0;
}E. 选数问题
二分答案。
cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
typedef long long LL;
const int N = 500010;
LL a[N];
int n, r, c;
bool check(int mid) {
int i = c, t = 0;
while (i <= n) {
if (a[i] - a[i - c + 1] <= mid) i += c, t++;
else i++;
}
return t >= r;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> r >> c;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 0, r = 1000000000;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}F. 互质划分
所有 2 的倍数都得占用一组。
python
print(max(1, int(input()) // 2))G. 出租车
看这里
cpp
#include <iostream>
using namespace std;
const int N = 200010;
int p[N], id[N], s[N], res[N];
int n, m;
int findl(long long val) {
int l = 1, r = n + m;
while (l < r) {
int mid = (l + r) >> 1;
if (p[mid] >= val) r = mid;
else l = mid + 1;
}
return l;
}
int findr(int val) {
int l = 1, r = n + m;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (p[mid] <= val) l = mid;
else r = mid - 1;
}
return l;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n + m; ++i) {
scanf("%d", &p[i]);
}
for (int i = 1; i <= n + m; ++i) {
scanf("%d", &id[i]);
s[i] = s[i - 1] + id[i];
}
for (int i = 1; i <= n + m; ++i) {
if (!id[i]) {
int l = 0, r = 1000000000;
while (l < r) {
int mid = (l + r) >> 1;
if (s[findr((long long)p[i] + mid)] - s[findl((long long)p[i] - mid) - 1]) r = mid;
else l = mid + 1;
}
int L = findl((long long)p[i] - l), R = findr((long long)p[i] + l);
// cout << L << ' ' << R << endl;
if (id[L] && id[R])
if (p[i] - p[L] <= p[R] - p[i]) res[L]++;
else res[R]++;
else if (id[L]) res[L]++;
else if (id[R]) res[R]++;
else return 213;
}
}
for (int i = 1; i <= n + m; ++i) {
if (id[i]) printf("%d ", res[i]);
}
printf("\n");
return 0;
}H. 木雕玩具
看这里
cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200010;
int a[N], n;
bool check(int mid) {
int t = 0, cur = -0x3f3f3f3f;
for (int i = 1; i <= n; ++i) {
if (a[i] - cur > mid) {
t++;
cur = a[i] + mid;
}
}
return t <= 3;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
int l = 0, r = 1000000000;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
return 0;
}其他没做的题
- 函数
- 怪兽
- 幽默数
- Connecting segments
- Filling pools
- Counting paths
- Compressing data
- Touring cities