2026夏个人训练赛第十八场
A. 幂次方
直接枚举底数统计。
cpp
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 100010;
bool a[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
LL n, l, res = 0;
cin >> n;
l = sqrt(n);
for (int i = 2; i <= l; ++i) {
if (a[i]) continue;
for (LL j = i; j <= l; j *= i) {
a[j] = true;
}
res += floor(log(n) / log(i) - 1);
}
cout << n - res << endl;
return 0;
}B. 自学
二分答案，贪心验证，如果旷课更优优先旷课，否则就尽可能上课，还不够就旷其他课（不需要具体找到那个要旷的课），只需要记录次数即可，每次检查次数是否不大于 m。我刚开始不小心把 Long long 爆了
cpp
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 300010;
int n;
LL a[N], b[N], m;
bool check(__int128_t mid) {
__int128_t t = 0;
for (int i = 1; i <= n; ++i) {
if (b[i] >= a[i]) t += (mid + b[i] - 1) / b[i];
else {
if ((mid + a[i] - 1) / a[i] <= m) t += (mid + a[i] - 1) / a[i];
else t += m + (mid - a[i] * m + b[i] - 1) / b[i];
}
}
return t <= m * n;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
__int128_t l = 0, r = 1e18;
while (l < r) {
__int128_t mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << (LL)l << endl;
return 0;
}C. 假期
- 尽可能做收益最大的
- 尽可能晚做，给别的留机会
因为我们只在意左边的空位，可以直接用并查集维护，如果占用了就把父亲给左边的，查询根就是左边第一个空位。
cpp
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
pair<LL, LL> a[N];
int fa[N];
int getfa(int x) {
if (x < 0) return 0;
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i].second >> a[i].first;
}
sort(a + 1, a + n + 1, greater<pair<LL, LL>>());
LL res = 0;
for (int i = 1; i <= m; ++i) fa[i] = i;
for (int i = 1; i <= n; ++i) {
auto [x, y] = a[i];
int p = getfa(m - y + 1);
if (p) {
res += x;
int q = getfa(p - 1);
fa[p] = q;
}
}
cout << res << endl;
return 0;
}D. 排队
我一直 wa（待补）
E. 传送
只有四种可能
1 → n
1 → 未确定点 → 未确定边 → n
1 → 未确定边 → 未确定点 → n
1 → 未确定边 → 未确定点 → 未确定边 → n正反分别跑一遍 bfs 维护一下即可。
cpp
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N = 300010;
int head[N], ver[N * 2], ne[N * 2], tot;
int d1[N], d2[N], v1[N], v2[N], f1[N], f2[N];
void add(int x, int y) {
ver[++tot] = y, ne[tot] = head[x], head[x] = tot;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
add(x, y), add(y, x);
}
memset(d1, 0x3f, sizeof(d1));
memset(d2, 0x3f, sizeof(d2));
queue<int> q;
d1[1] = 0;
v1[1] = 1;
q.emplace(1);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (!v1[y]) {
v1[y] = 1;
d1[y] = d1[x] + 1;
if (y) q.emplace(y);
}
if (y == 0 && d1[y] == d1[x] + 1) {
f1[x] = true;
}
}
}
d2[n] = 0;
v2[n] = 1;
q.emplace(n);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (!v2[y]) {
v2[y] = 1;
d2[y] = d2[x] + 1;
if (y) q.emplace(y);
}
if (y == 0 && d2[y] == d2[x] + 1) {
f2[x] = true;
}
}
}
int dis = d1[n];
for (int i = 1; i <= n; ++i) {
int res = min(dis, min(d1[0] + d2[i] - f1[i], min(d1[i] + d2[0] - f2[i], d1[0] + d2[0] - f1[i] - f2[i])));
// cout << dis << ' ' << d1[0] + d2[i] - f1[i] << ' ' << d1[i] + d2[0] - f2[i] << endl;
cout << (res == 0x3f3f3f3f ? -1 : res) << ' ';
}
cout << '\n';
return 0;
}F. Paintball
没什么知识含量的计算几何，竟有 11 min 就敲完了的，肯定是 codex 发力了…
G. Islands
反着做，用并查集动态维护连通块数量，按照高度排序，然后根据查询分批加入更低的点。
cpp
#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
const int N = 1010, M = 100010;
int a[N][N], fa[N * N], t[M], res[M], cnt;
tuple<int, int, int> b[N * N];
int n, m;
int get(int x, int y) {
return (x - 1) * m + y;
}
int getfa(int x) {
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
void merge(int x, int y) {
x = getfa(x), y = getfa(y);
if (x != y) fa[y] = x, cnt--;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
b[get(i, j)] = {a[i][j], i, j};
fa[get(i, j)] = get(i, j);
}
}
sort(b + 1, b + n * m + 1);
int q;
cin >> q;
for (int i = 1; i <= q; ++i) {
cin >> t[i];
}
cnt = 0;
for (int i = q, j = n * m; i; --i) {
while (j && get<0>(b[j]) > t[i]) {
auto [_, x, y] = b[j--];
cnt++;
int p = get(x, y);
for (int k = 0; k < 4; ++k) {
int tx = x + dx[k], ty = y + dy[k];
if (tx > 0 && tx <= n && ty > 0 && ty <= m && a[tx][ty] > t[i]) {
int q = get(tx, ty);
merge(p, q);
}
}
}
res[i] = cnt;
}
for (int i = 1; i <= q; ++i) cout << res[i] << ' ';
cout << endl;
}
return 0;
}H. 旅游巴士
就是个分层图最短路，走不动了只需要假定来之前等了几个 k 即可。
cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 10010, M = 110;
LL dis[N][M], t[N * 2];
bool vis[N][M];
int head[N], ver[N * 2], ne[N * 2], tot;
struct Node {
LL d;
int x, p;
bool operator <(const Node &_) const {
return d > _.d;
}
};
void add(int x, int y, int tt) {
ver[++tot] = y, ne[tot] = head[x], head[x] = tot, t[tot] = tt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= m; ++i) {
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
memset(dis, 0x3f, sizeof(dis));
priority_queue<Node> q;
dis[1][0] = 0;
q.emplace(Node({0, 1, 0}));
while (!q.empty()) {
auto [_, x, p] = q.top();
q.pop();
if (vis[x][p]) continue;
vis[x][k] = true;
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
LL d = dis[x][p] + 1 + max(0LL, (t[i] - dis[x][p] + k - 1) / k * k);
if (dis[y][d % k] > d) {
dis[y][d % k] = d;
q.emplace(Node({dis[y][d % k], y, int(d % k)}));
}
}
}
cout << (dis[n][0] == 0x3f3f3f3f3f3f3f3f ? -1 : dis[n][0]) << endl;
return 0;
}J. Counting regions
没人开的题
- I. Protecting lawn
- K. Playing games
- L. Permuting cows
- M. Calculating sums
- N. Decoding graphs