OI笔记 | 2022.11 做题记录（一）
仍然是每 $10$ 题分一个文章。如果做的题多，可能会更新得更频繁一些。
- [NOIP2010 提高组] 关押罪犯
- [NOIP2010 提高组] 乌龟棋
- P1714 切蛋糕
- [HAOI2007]理想的正方形
- [COCI2020-2021#5] Po
- 没有上司的舞会
- Strategic game
- 最大子树和
- [HNOI2003]激光炸弹
- 贪婪大陆
[NOIP2010 提高组] 关押罪犯
有两座监狱，需要关押 $N$ 名罪犯，编号分别为 $1-N$。给出 $M$ 个关系，每个关系 $(u,v,c)$ 表示罪犯 $u$ 和 罪犯 $v$ 如果被关押在同一监狱，会造成影响力为 $c$ 的冲突事件。
分配这 $N$ 名罪犯到两个监狱，使得所有冲突事件的影响力的最大值最小，求出这个最小值。
题解
考虑将关系按影响力排序，我们优先解决影响力大的事件。用并查集维护当前罪犯分配的情况。
如果处理到此处， $u_i$ 和 $v_i$ 已经在同一个监狱，那么无法再解决了，直接输出这个影响力。否则，将 $u$ 分配到 $v$ 的敌人所关押的监狱，将 $v$ 分配到 $u$ 的敌人所关押的监狱。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, N = 20005;
struct edge {
int u, v, c;
bool operator < (const edge &t) const {return c > t.c;}
} E[MAX_N];
int f[MAX_N], d[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int find(int x) {
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
int main() {
int n = read(), m = read();
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), c = read();
E[i] = {u, v, c};
}
sort(E + 1, E + m + 1);
for(int i = 1; i <= m + 1; i++) {
int u = E[i].u, v = E[i].v;
int fu = find(u), fv = find(v);
if(fu == fv) {
write(E[i].c);
break;
}
else {
if(!d[u]) d[u] = v;
else f[fv] = find(d[u]);
if(!d[v]) d[v] = u;
else f[fu] = find(d[v]);
}
}
return 0;
}
[NOIP2010 提高组] 乌龟棋
乌龟棋的棋盘是一行 $N$ 个格子，从 $1$ 号格子出发，到 $N$ 号格子结束。每个格子上有一个分数。
乌龟棋中有 $M$ 张爬行卡片，分为 $1,2,3,4$ 共 $4$ 种。$1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。
保证到达终点时刚好用光 $M$ 张爬行卡片。给定每种卡片的数目，求从起点到终点的最大得分。
$1≤N≤350,1≤M≤120$，且 $4$ 种爬行卡片，每种卡片的张数 $k$ 不会超过$40$。
题解
考虑暴力 dp。我们用 $dp_{a,b,c,d}$ 表示使用 $a$ 张前进 $1$ 格的卡片， $b$ 张前进 $2$ 格的卡片， $c$ 张前进 $3$ 格的卡片， $d$ 张前进 $4$ 格的卡片时的最大得分。
则它可以从 $dp_{a-1,b,c,d}$ 或 $dp_{a,b-1,c,d}$ 或 $dp_{a,b,c-1,d}$ 或 $dp_{a,b,c,d-1}$ 转移过来。 $O(k^4)$ 暴力转移即可。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 360;
int a[MAX_N], cnt[5], dp[45][45][45][45];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= m; i++) {
int t = read();
cnt[t]++;
}
dp[0][0][0][0] = a[1];
for(int k1 = 0; k1 <= cnt[1]; k1++) {
for(int k2 = 0; k2 <= cnt[2]; k2++) {
for(int k3 = 0; k3 <= cnt[3]; k3++) {
for(int k4 = 0; k4 <= cnt[4]; k4++) {
int pos = 1 + k1 * 1 + k2 * 2 + k3 * 3 + k4 * 4;
if(k1 != 0) dp[k1][k2][k3][k4] = max(dp[k1][k2][k3][k4], dp[k1 - 1][k2][k3][k4] + a[pos]);
if(k2 != 0) dp[k1][k2][k3][k4] = max(dp[k1][k2][k3][k4], dp[k1][k2 - 1][k3][k4] + a[pos]);
if(k3 != 0) dp[k1][k2][k3][k4] = max(dp[k1][k2][k3][k4], dp[k1][k2][k3 - 1][k4] + a[pos]);
if(k4 != 0) dp[k1][k2][k3][k4] = max(dp[k1][k2][k3][k4], dp[k1][k2][k3][k4 - 1] + a[pos]);
}
}
}
}
write(dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
return 0;
}
P1714 切蛋糕
在数列 ${p_n}$ 中，找出一个子段 $[l,r] (r-l+1\le m)$，最大化 $\sum\limits_{i=l}^rp_i$。
$n \le 5 \times 10^5, \lvert p_i\rvert \le500$
题解
即不定长最大子段和。可以用线段树或st表或单调队列维护区间最值。
例如使用st表维护前缀和的区间最小值，只需枚举右端点 $r$，然后找到 $[r-m, r]$ 之间最小的 $sum_i$，那么以 $r$ 为右端点的最大子段和就是 $sum_r-sum_i$。时间复杂度：$O(n\log n)$
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e5 + 10, MAX_LOG = 19;
int sum[MAX_N], st[MAX_N][MAX_LOG], log_2[MAX_N], n, m, ans = -2147483647;
inline ll read() {...}
inline void write(ll x) {...}
inline void init() {
log_2[1] = 0, log_2[2] = 1;
for(int i = 3; i <= n; i++) log_2[i] = log_2[i >> 1] + 1;
for(int i = 1; i <= n; i++) st[i][0] = sum[i];
for(int j = 1; j < MAX_LOG; j++) {
for(int i = 1; i + (1 << (j - 1)) - 1 <= n; i++) {
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
inline int query(int l, int r) {
int len = log_2[r - l + 1];
return min(st[l][len], st[r - (1 << len) + 1][len]);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) {
int x = read();
sum[i] = sum[i - 1] + x;
}
init();
for(int r = 1; r <= n; r++) {
int l = max(0, r - m);
ans = max(ans, sum[r] - query(l, r));
}
write(ans);
return 0;
}
[HAOI2007]理想的正方形
有一个 $a \times b$ 的整数组成的矩阵，现请你从中找出一个 $n \times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
$2 \le a,b \le 1000,n \le a,n \le b,n \le 100$。
题解
用二维 st 表来维护所有正方形内的最值。具体的，用 $st_{i,j,k}$ 表示以 $(i,j)$ 为左上角，边长为 $2^k$ 的正方形内的最值，则它可以由四个子正方形转移过来。见下图：
询问则与一维比较类似。同样将正方形分割成四个子正方形，边长为 $\log_2{n}$。
时间复杂度： $O(ab \log (ab))$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e3 + 10, MAX_LOG = 10;
int log_2[MAX_N], a, b, n, ans = 1e9;
struct ST {
int maxn, minn;
} st[MAX_N][MAX_N][MAX_LOG], k1, k2, k3, k4;
inline ll read() {...}
inline void write(ll x) {...}
inline void init() {
log_2[1] = 0, log_2[2] = 1;
for(int i = 3; i < MAX_N; i++) log_2[i] = log_2[i >> 1] + 1;
for(int k = 1; k <= MAX_LOG; k++) {
for(int i = 1; i + (1 << (k - 1)) - 1 <= a; i++) {
for(int j = 1; j + (1 << (k - 1)) - 1 <= b; j++) {
k1 = st[i][j][k - 1];
k2 = st[i][j + (1 << (k - 1))][k - 1];
k3 = st[i + (1 << (k - 1))][j][k - 1];
k4 = st[i + (1 << (k - 1))][j + (1 << (k - 1))][k - 1];
st[i][j][k].minn = min(k1.minn, min(k2.minn, min(k3.minn, k4.minn)));
st[i][j][k].maxn = max(k1.maxn, max(k2.maxn, max(k3.maxn, k4.maxn)));
}
}
}
}
inline int query(int i, int j, int k, bool type) {
int len = log_2[k];
k1 = st[i][j][len];
k2 = st[i][j + k - (1 << len)][len];
k3 = st[i + k - (1 << len)][j][len];
k4 = st[i + k - (1 << len)][j + k - (1 << len)][len];
if(type == 0) return min(k1.minn, min(k2.minn, min(k3.minn, k4.minn)));
else return max(k1.maxn, max(k2.maxn, max(k3.maxn, k4.maxn)));
}
int main() {
a = read(), b = read(), n = read();
for(int i = 1; i <= a; i++) for(int j = 1; j <= b; j++) st[i][j][0].minn = st[i][j][0].maxn = read();
init();
for(int i = 1; i <= a - n + 1; i++) for(int j = 1; j <= b - n + 1; j++) ans = min(ans, query(i, j, n, 1) - query(i, j, n, 0));
write(ans);
return 0;
}
[COCI2020-2021#5] Po
有一个长度为 $n$ 的数组。在初始状态下，所有元素都为 $0$。
每次操作，可以将一个连续的区间 $[l,r]$ 内的所有数加上一个正整数 $x$，但要求任意两个操作区间要么互不相交，要么一个包含另外一个。
请问能将原数组变为给定数组 $a$ 的最少操作次数。
题解
维护一个单调递增栈。
每次入栈时把比它大的所有栈顶元素出栈，如果栈空了，或者栈顶元素小于当前元素，则不能把当前元素和之前的元素一起处理。让答案加一。
否则，忽略这个元素，因为它只可能与栈顶元素相等，可以在同一次操作中完成。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int a[MAX_N], ans;
stack<int> s;
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= n; i++) {
while(!s.empty() && s.top() > a[i]) s.pop();
if(a[i] > 0 && (s.empty() || s.top() < a[i])) ans++, s.push(a[i]);
}
write(ans);
return 0;
}
没有上司的舞会
某大学有 $n$ 个职员，编号为 $1\ldots n$。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
$1\leq n \leq 6 \times 10^3$
题解
第一次写树形 dp，这题比较裸，是一个好的开始。
树形 dp 一般递归求解。我们对某一子树的根节点设计状态，则它从它的所有儿子节点转移过来。
用 $dp(i, 0/1)$ 表示对于 $i$ 号节点，它参加或不参加舞会时的最大收益。则它不参加舞会时，它的儿子可参加可不参加，取其中较大的情况。它参加舞会时，它的儿子不可参加。
我们枚举它的所有儿子节点 $v_1, v_2 \dots v_k$，则状态转移方程如下：
\[dp(i,0)=\sum\limits_{j=1}^k[\max(dp(v_j,0),dp(v_j,1))] \\ dp(i,1)=a_i+\sum\limits_{j=1}^kdp(v_j,0)\]参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 6e3 + 10;
int dp[MAX_N][2];
bool child[MAX_N], vis[MAX_N];
vector<int> G[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void dfs(int r) {
vis[r] = 1;
for(int i = 0; i < G[r].size(); i++) {
int v = G[r][i];
if(vis[v]) continue;
dfs(v);
dp[r][0] += max(dp[v][1], dp[v][0]);
dp[r][1] += dp[v][0];
}
}
int main() {
int n = read(), root;
for(int i = 1; i <= n; i++) dp[i][1] = read(); // 对应状态转移方程中的 a_i
for(int i = 1; i <= n - 1; i++) {
int l = read(), k = read();
child[l] = 1;
G[k].push_back(l);
}
for(int i = 1; i <= n; i++) {
if(!child[i]) {
root = i;
break;
}
}// 找到根节点，从它开始 dfs
dfs(root);
write(max(dp[root][0], dp[root][1]));
return 0;
}
Strategic game
给定一个树，求它的最小点覆盖。
题解
我们用 $dp(i,0/1)$ 表示对于 $i$ 节点，它选或不选时的最少点数。
初始化 $dp(i,1) = 1$。
对于每个节点，它从它的所有子节点转移过来。如果这个节点不选，那么它的子节点必须选。如果这个节点选，那么它的子节点可选可不选。状态转移方程如下：
\[dp(u,1) = \sum\min(dp(v,0), dp(v,1))\\ dp(u,0) = \sum dp(v,1)\]注意 POJ 不能用万能头。
参考代码：
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX_N = 1510;
vector<int> G[MAX_N];
int dp[MAX_N][2];
bool child[MAX_N], vis[MAX_N];
void dfs(int r) {
vis[r] = 1;
dp[r][1] = 1, dp[r][0] = 0;
for(int i = 0; i < G[r].size(); i++) {
int v = G[r][i];
if(vis[v]) continue;
dfs(v);
dp[r][1] += min(dp[v][0], dp[v][1]);
dp[r][0] += dp[v][1];
}
}
int main() {
int n, u, m, v, root;
while(~scanf("%d", &n)) {
memset(vis, 0, sizeof(vis));
memset(child, 0, sizeof(child));
for(int i = 0; i < n; i++) {
scanf("%d:(%d)", &u, &m);
G[u].clear();
while(m--) {
scanf("%d", &v);
child[v] = 1;
G[u].push_back(v);
}
}
for(int i = 0; i < n; i++) {
if(!child[i]) {
root = i;
break;
}
}
dfs(root);
printf("%d\n", min(dp[root][0], dp[root][1]));
}
return 0;
}
最大子树和
找到树上点权之和最大的一个连通分量。
题解
我们选 $1$ 为根节点，转化为有根树，显然这不影响答案。
设 $dp_u$ 表示以 $u$ 为根节点的子树的最大权值，那么显然如果某个子节点的值 $dp_v<0$，则它不应该选，否则应该选它。形式化地：
\[dp_u = \sum\limits^{dp_v>0} dp_v\]答案要每个节点枚举过去的最大值，因为我们假定了根。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 16005, INF = 1e9;
int dp[MAX_N];
vector<int> G[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void dfs(int u, int fa) {
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v == fa) continue;
dfs(v, u);
if(dp[v] > 0) dp[u] += dp[v];
}
}
int main() {
int n = read(), ans = -INF;
for(int i = 1; i <= n; i++) dp[i] = read();
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read();
G[u].push_back(v), G[v].push_back(u);
}
dfs(1, 0);
for(int i = 1; i <= n; i++) ans = max(ans, dp[i]);
write(ans);
return 0;
}
[HNOI2003]激光炸弹
一种新型的激光炸弹，可以摧毁一个边长为 $m$ 的正方形内的所有目标。现在地图上有 $n$ 个目标，用整数 $x_i$ , $y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $v_i$ .激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 $m$ 的边必须与 $x$ 轴, $y$ 轴平行。若目标位于爆破正方形的边上，该目标不会被摧毁。
现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。
$n\le 10^4$
题解
二维前缀和模板题，不需要什么特别的数据结构，枚举就好。
时间复杂度：$O(n^2)$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e3 + 10;
int sum[MAX_N][MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), m = read(), ans = -1;
for(int i = 1; i <= n; i++) {
int x = read(), y = read(), v = read();
sum[x + 1][y + 1] = v;
}
for(int i = 1; i < MAX_N; i++) {
for(int j = 1; j < MAX_N; j++) {
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
for(int i = m; i < MAX_N; i++) {
for(int j = m; j < MAX_N; j++) {
int s = sum[i][j] - sum[i - m][j] - sum[i][j - m] + sum[i - m][j - m];
ans = max(ans, s);
}
}
write(ans);
return 0;
}
贪婪大陆
需要支持两种操作：
-
在 $[l,r]$ 区间内叠加上一种地雷（种类不与之前布过的任意一种相同）。
-
查询 $[l,r]$ 区间内有几种不同的地雷。
题解
类似于扫描线，我们把一个区间的左端点记为 $head$，右端点记为 $tail$。
我们用两个树状数组，它们分别维护 $head$ 的个数的前缀和 $sum_{head}$、 $tail$ 的个数的前缀和 $sum_{tail}$。
略加思考可以得知，当我们查询 $[l,r]$ 时，它的地雷种类数 = $sum_{head}[r] - sum_{tail}[l - 1]$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
struct node {
int head, tail;
} tree[MAX_N];
int n, m;
inline ll read() {...}
inline void write(ll x) {...}
inline int lowbit(int x) {return x & -x;}
inline void update(int x, bool type) {
while(x <= n) {
if(type) tree[x].head++;
else tree[x].tail++;
x += lowbit(x);
}
}
inline int query(int x, bool type) {
int ret = 0;
while(x > 0) {
if(type) ret += tree[x].head;
else ret += tree[x].tail;
x -= lowbit(x);
}
return ret;
}
int main() {
n = read(), m = read();
while(m--) {
int op = read(), l = read(), r = read();
if(op == 1) update(l, 1), update(r, 0);
else write(query(r, 1) - query(l - 1, 0)), putchar('\n');
}
return 0;
}
- 上一篇 OI笔记 | 2022.10 做题记录（二）
- 下一篇 OI笔记 | 基础图论模板
♥