F. 省钱
建图后跑最小生成树即可。建图：
- 按 x 排序，相邻的点之间连边
- 按 y 排序，相邻的点之间连边
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010, maxm = 200010;
struct edge {
int u, v, w;
bool operator<(const edge &n) const { return w < n.w; }
}E[maxm];
int fa[maxn], n, m;
void init() {
for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void uni(int x, int y) {
int rx = find(x), ry = find(y);
fa[ry] = rx;
}
long long kru() {
init();
sort(E, E + m);
long long ans = 0;
for (int i = 0; i < m; ++i) {
edge e = E[i];
if (find(e.u) != find(e.v)) {
uni(e.u, e.v);
ans += e.w;
}
}
return ans;
}
// ----------------- 最小生成树模板
struct Node{
int id, x, y;
}node[maxn];
bool cmpX(Node x, Node y) {
return x.x < y.x;
}
bool cmpY(Node x, Node y) {
return x.y < y.y;
}
// ------------------ 按 X Y 排序类似 ch01 的 A 题
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> node[i].x >> node[i].y;
node[i].id = i;
}
sort(node + 1, node + 1 + n, cmpX);
for (int i = 2; i <= n; ++i) {
E[m].u = node[i - 1].id, E[m].v = node[i].id;
E[m].w = node[i].x - node[i - 1].x;
++m;
}
sort(node + 1, node + 1 + n, cmpY);
for (int i = 2; i <= n; ++i) {
E[m].u = node[i - 1].id, E[m].v = node[i].id;
E[m].w = node[i].y - node[i - 1].y;
++m;
}
cout << kru() << "\n";
return 0;
}
G. 打包
作为附加题。
对每个起点使用二分找终点。
每包确定起点，终点就一定固定，只有 n 对起点和终点，则 n+1 次打包中，一定有循环节。
将循环开始的盒数和循环节长度记录下来，就可以做到 O(1) 回答询问
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
using ll = long long;
bool vis[maxn];
ll sum[maxn], x;
ll mp[maxn], mp2[maxn];
int n;
// 当前盒子从数组下标 _p 开始，返回下一个盒子开始的数组下标（先不取模，因为要统计盒子中的蛋糕个数）
ll find(ll _p) { // find nxt
ll p = _p % n, s = x, cnt = 0;
if (p == 0) p = n;
cnt += s / sum[n] * n, s %= sum[n];
if (s > sum[n] - sum[p - 1]) {
cnt += n - p + 1, s -= sum[n] - sum[p - 1];
p = 1;
}
int pos = lower_bound(sum + 1, sum + 1 + n, sum[p - 1] + s) - sum;
cnt += pos - p + 1;
return _p + cnt;
}
// 第 1 个盒子从数组下标 p = 1 开始使用重量 w[1]
ll p = 1, cnt = 0;
void init() {
while (true) {
if (vis[p % n]) return;
vis[p % n] = 1;
ll nxt = find(p);
// 存第 cnt 个盒子装的蛋糕个数
mp[++cnt] = nxt - p;
// 记录下标 p 在路径中是第几个
mp2[p % n] = cnt, p = nxt;
}
}
int main() {
int q;
ll k, a;
cin >> n >> q >> x;
for (int i = 1; i <= n; ++i) {
cin >> a;
sum[i] = sum[i - 1] + a;
}
init();
// st: 环中的起点，cir: 环的大小
ll st = mp2[p % n], cir = cnt + 1 - st;
while (q--) {
cin >> k;
if (k < st) cout << mp[k] << "\n"; // 在环前面的链中
else cout << (mp[st + (k - st) % cir]) << "\n"; // 在环中
}
return 0;
}
I. 修炼
枚举每个点作为起点 O(n)，二分 S O(log 4e9)。已知起点和 S 后暴力建图跑 dfs/bfs O(n(n+m))
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, x[210], y[210], p[210];
bool vis[210];
void dfs(int u, ll s) {
vis[u] = 1;
for (int v = 1; v <= n; ++v) {
if (!vis[v] && p[u] * s - abs(x[u] - x[v]) - abs(y[u] - y[v]) >= 0)
dfs(v, s);
}
}
bool check(int st, ll s) {
memset(vis, 0, sizeof(vis));
dfs(st, s);
for (int i = 1; i <= n; ++i) {
if (!vis[i]) return 0;
}
return 1;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x[i] >> y[i] >> p[i];
}
ll res = 4e9;
for (int i = 1; i <= n; ++i) {
ll l = 0, r = 4e9;
while (l <= r) {
ll mid = (l + r) / 2;
if (check(i, mid)) r = mid - 1, res = min(res, mid);
else l = mid + 1;
}
}
cout << res << endl;
return 0;
}