earth
【题目描述】
“啊，地球，我的流浪地球……”
——《流浪地球》
在一条直线上，从左到右排列着 \(n\) 台地球发动机，每台发动机有着固定的位置坐标 \(A_i\) 和功率 \(P_i\)，保证 \(A_i<A_i+1\)。此外，由于地球发动机的特性，每台发动机还有一个参数 \(X_i\)，如果一台发动机运行，则坐标范围在 \(\left[A_i,A_i+X_i \right]\) 的其它发动机就无法运行。现在你想让正在运行的发动机总功率最大，请输出这个总功率。
【输入数据】
第一行一个整数 \(n\),意义如上所述。
接下来 \(n\) 行，每行三个整数 \(A_i,P_i,X_i\),意义如题面所述。
【输出数据】
一行一个整数，表示可能的最大功率。
【样例输入】
4
2 5 1
5 4 3
8 10 3
9 2 2
【样例输出】
15
【数据范围】
对于 \(20\%\) 的数据，\(n \le 10，0 < A_i,P_i,X_i \le 10\)；
对于 \(50\%\) 的数据，\(n \le 2000，0 < A_i,P_i,X_i \le 10^5\)；
对于 \(100\%\) 的数据，\(n \le 105，0 < A_i,P_i,X_i \le 10^9\)。
一个 DP 题，调试时多写了个括号忘删了，然后第一个点就被卡了。
\(dp_i\)：第 \(i\) 个发动机能达到的最大总功率。
\(dp_i = \max(dp_{i + 1}, dp_x + p_i)\)，\(x\) 为距离 \(> A_i + x_i\) 的最小位置，可以二分找到。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n;
ll A[N], p[N], x[N], dp[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) {
scanf("%lld%lld%lld", &A[i], &p[i], &x[i]);
}
dp[n] = p[n];
for (int i = n - 1; i >= 1; -- i) {
int pos = A[i] + x[i];
if (A[i + 1] > pos) {
dp[i] = dp[i + 1] + p[i];
}
else {
if (A[n] < pos) {
dp[i] = max(dp[i + 1], p[i]);
}
else {
int x = upper_bound(A + i, A + n + 1, pos) - A;
dp[i] = max(dp[i + 1], dp[x] + p[i]);
}
}
}
printf("%lld\n", dp[1]);
return 0;
}
graph
【题目描述】
小 \(H\) 有一张 \(n\) 个点，\(m\) 条边的无向连通图，他想从图中选出一些边，保证通过这些边 \(a\) 和 \(b\) 连通,\(c\) 和 \(d\) 连通，同时选出的边数尽量少。
【输入数据】
第一行两个整数 \(n,m\)，表示图中的边数和点数。
第二行四个整数 \(a,b,c,d\)，意义如题面所述。
接下来 \(m\) 行，每行两个整数 \(a,b\),表示点 \(a\) 和点 \(b\) 间有一条边。
【输出数据】
一行一个整数，表示最少需要选出的边数。
【样例输入】
5 8
3 4 1 3
2 1
3 2
4 3
5 3
4 2
1 4
5 4
2 1
【样例输出】
2
【数据范围】
对于所有数据，保证 \(1 \le a,b,c,d \le n\)；
对于 \(10\%\) 的数据，\(0 < n,m \le 20\);
对于 \(30\%\) 的数据，\(0 < n,m \le 300\);
对于 \(60\%\) 的数据，\(0 < n \le 300\);
对于 \(100\%\) 的数据，\(0 < n,m \le 3000\)。
如果路径不相交，则答案为 \(a \Rightarrow b\)、\(c \Rightarrow d\) 的最短路，如果有相交的部分， \(n^2\) 枚举 相交部分的起始点和终点，判断这一段是否相交，求最大值。
点与点之间的最小距离，由于没有边权，可以直接设为 \(1\)，然后用 bfs 来做，\(O_{n^2}\)。堆优化的 dijkstra 也跑不过，别问我是怎么知道的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const int N = 3010;
int n, m, a, b, c, d;
ll dis[N][N];
bool vis[N], e[N][N];
vector<int> son[N];
void bfs(int s) {
for (int i = 1; i <= n; ++ i) {
vis[i] = 0;
}
queue<int> q;
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : son[u]) {
if (vis[v]) continue;
dis[s][v] = dis[s][u] + 1;
vis[v] = 1;
q.push(v);
}
}
}
int main() {
memset(dis, 0x3f, sizeof dis);
scanf("%d%d", &n, &m);
scanf("%d%d%d%d", &a, &b, &c, &d);
for (int i = 1; i <= n; ++ i) {
dis[i][i] = 0;
}
for (int i = 1, x, y; i <= m; ++ i) {
scanf("%d%d", &x, &y);
if (e[x][y]) continue;
e[x][y] = e[y][x] = 1;
son[x].push_back(y);
son[y].push_back(x);
}
for (int i = 1; i <= n; ++ i) {
bfs(i);
}
ll maxx = 0;
for (int x = 1; x <= n; ++ x) {
for (int y = 1; y <= n; ++ y) {
if (x == y) continue;
if ((dis[a][x] + dis[x][y] + dis[y][b] == dis[a][b] ||
dis[a][y] + dis[x][y] + dis[x][b] == dis[a][b]) &&
(dis[c][x] + dis[x][y] + dis[y][d] == dis[c][d] ||
dis[c][y] + dis[x][y] + dis[x][d] == dis[c][d])) {
maxx = max(maxx, dis[x][y]);
}
}
}
printf("%lld\n", dis[a][b] + dis[c][d] - maxx);
fclose(stdin);
fclose(stdout);
return 0;
}
tree
【题目描述】
小 \(H\) 有一棵 \(n\) 个节点的树 \(T\)，每个节点上有一个非负整数 \(A_i\),他想知道所有距离不超过k的点对 \(\left(x , y\right) (x<y)\) 上数的亦或值的和。
【输入数据】
第一行两个正整数 \(n,k\)，表示树上的节点数和给定的距离 \(k\)。
第二行 \(n\) 个非负整数，第 \(i\) 个数表示第 \(i\) 个节点上的数是 \(A_i\)。
接下来 \(n-1\) 行,每行两个正整数 \(u,v\),表示节点 \(u\) 和节点 \(v\) 之间有一条边。保证输入是一棵树。
【输出数据】
一行一个整数，表示所有距离不超过k的点对上数的亦或值的和。
【样例输入】
6 3
7 4 4 3 2 0
2 1
6 2
5 6
3 5
4 1
【样例输出】
51
【数据范围】
| 测试点编号 | n | k | \(A_i\) | 特殊性质 |
|---|---|---|---|---|
| 1 | 300 | n | 220 | |
| 2 | 300 | n | 220 | |
| 3 | 300 | n | 220 | |
| 4 | 2000 | n | 2 | |
| 5 | 2000 | n | 28 | |
| 6 | 2000 | 20 | 220 | |
| 7 | 2000 | n | 220 | 树是一条链 |
| 8 | 2000 | n | 220 | |
| 9 | 105 | n | 2 | |
| 10 | 105 | n | 28 | |
| 11 | 105 | 20 | 220 | |
| 12 | 105 | n | 220 | 树是一条链 |
| 13 | 105 | n | 220 | |
| 14 | 105 | n | 220 | |
| 15 | 3*105 | n | 2 | |
| 16 | 3*105 | n | 28 | |
| 17 | 3*105 | 20 | 220 | |
| 18 | 5*105 | n | 220 | 树是一条链 |
| 19 | 5*105 | n | 220 | |
| 20 | 5*105 | n | 220 |
40分的暴力很好打，\(n^2\) 暴力。
正解：点分治
暴力：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010;
int n, k;
int dep[N];
ll a[N], dis[N][N];
vector<int> son[N];
void dfs(int u, int fat) {
for (int v : son[u]) {
if (v == fat) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d%d", &n, &k);
if (n > 2000) {
cout << rand();
fclose(stdin);
fclose(stdout);
return 0;
}
for (int i = 1; i <= n; ++ i) {
scanf("%lld", &a[i]);
}
for (int i = 1, x, y; i <= n - 1; ++ i) {
scanf("%d%d", &x, &y);
son[x].push_back(y);
son[y].push_back(x);
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
dep[j] = 0;
}
dfs(i, 0);
for (int j = 1; j <= n; ++ j) {
dis[i][j] = dep[j];
}
}
ll ans = 0;
for (int x = 1; x < n; ++ x) {
for (int y = x + 1; y <= n; ++ y) {
if (dis[x][y] <= k) {
ans += (a[x] ^ a[y]);
}
}
}
printf("%lld\n", ans);
fclose(stdin);
fclose(stdout);
return 0;
}