OI笔记 | 2022.11 做题记录（二）
又正好攒了 $10$ 题。主要是做不出来的题就会顺便写一下题解，所以攒的快。总的来说还是自己菜阿。
话说最近的两场模拟赛全都是原题，挺不好的，但是方便补题（可以看不同的题解，有订正的动力）。
晚上复习一下最近做的题和模板，然后看看有没有时间写一点数学题，感觉whk已经寄了，文科好久都没听课了。虽然半期考免考了，但是不想丢掉数学的题感，总不能一点都不学吧。
- 寻找段落
- 会议
- 逛画展
- Divisibility by 2^n
- [NOIP2008 提高组] 传纸条
- 灾后重建
- 三步必杀
- [BalticOI 2013 Day1] Ball Machine
- [ZJOI2008] 骑士
- Lockdown
寻找段落
在数组 $a$ 中找到一个长度在 $[S,T]$ 之间的子段，使得这个子段的平均值最大。
题解
二分答案。考虑到单调性：平均值越大，越难找到合法的子段。
所以对于一个答案 $mid$，我们将所有 $a_i$ 减去 $mid$ 后做前缀和，在前缀和数组中如果能找到一个长度在 $[S,T]$ 之间的子段，使得 $sum[r]-sum[l]>0$ ，则它合法，我们应该往更大的数找，即 $l=mid$；否则 $r=mid$。
其中，显然 $\exists \ l,\ sum[r] - sum[l]>0 \Leftrightarrow sum[r]-(sum[l])_{\text{min}} > 0$，所以用单调队列维护最小值即可。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
const double eps = 1e-5;
int n, s, t;
double sum[MAX_N], a[MAX_N];
deque<int> q;
inline ll read() {...}
inline void write(ll x) {...}
bool check(double x) {
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i] - x;
q.clear();
for(int i = s; i <= n; i++) {
while(!q.empty() && sum[q.back()] > sum[i - s]) q.pop_back();
q.push_back(i - s);
while(!q.empty() && q.front() + t < i) q.pop_front();
if(!q.empty() && sum[i] - sum[q.front()] >= 0) return true;
}
return false;
}
int main() {
n = read(), s = read(), t = read();
for(int i = 1; i <= n; i++) a[i] = read();
double l = -10000, r = 10000;
while(r - l > eps) {
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.3lf", l);
return 0;
}
会议
有一个村庄居住着 $n$ 个村民，有 $n-1$ 条路径使得这 $n$ 个村民的家联通，每条路径的长度都为 $1$。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。
$n \le 5 \times 10^4$。
题解
我们以 $1$ 为根，dfs 一遍，处理出每个点到 $1$ 号点的距离 $d_i$ 以及 每个点的子树大小 $s_i$。（子树大小：子树的节点个数$+1$）。
我们用 $f_v$ 表示在 $v$ 节点召开会议的距离之和。它可以从它的父亲节点 $u$ 转移过来：
\[f_v=f_u+(n-s_v)-s_v=f_u+n-2\times s_v\]这是因为不在 $v$ 的子树下的节点（共 $n-s_v$ 个），它们的距离都要 $+1$；在 $v$ 的子树下的节点（共 $s_v$ 个），它们的距离都要 $-1$。
用树形 dp 的常见手段，递归转移即可。
时间复杂度：$O(n)$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e4 + 10;
vector<int> G[MAX_N];
int d[MAX_N], s[MAX_N], f[MAX_N], n;
inline ll read() {...}
inline void write(ll x) {...}
void dfs1(int u, int fa) {
s[u] = 1;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v == fa) continue;
d[v] = d[u] + 1;
dfs1(v, u);
s[u] += s[v];
}
}
void dfs2(int u, int fa) {
if(fa != 0) f[u] = f[fa] + n - 2 * s[u];
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v == fa) continue;
dfs2(v, u);
}
}
int main() {
n = read();
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read();
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1, 0);
for(int i = 1; i <= n; i++) f[1] += d[i];
dfs2(1, 0);
int ans = 1e9, t;
for(int i = 1; i <= n; i++) {
if(f[i] < ans) {
ans = f[i];
t = i;
}
}
write(t), putchar(' '), write(ans);
return 0;
}
逛画展
博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。
游客在购买门票时必须说明两个数字，$a$ 和 $b$，代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。
Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。
请求出他购买门票时应选择的 $a,b$，数据保证一定有解。
若存在多组解，输出 $a$ 最小的那组。
$1\leq n\le10^6$，$1 \leq a_i \leq m\le2\times10^3$。
题解
用尺取法。让右端点 $r$ 一直右移，如果左端点 $l$ 的画师的话已经出现过，则让 $l$ 右移。期间维护合法的最小的区间长度即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 10;
int a[MAX_N], f[MAX_N];
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();
int i = 1, j = 1, cnt = 0, ansi, ansj, anslen = MAX_N;
while(j <= n) {
if(!f[a[j]]) cnt++; // 区间内的画师数
f[a[j]]++;
while(f[a[i]] > 1) {
f[a[i]]--;
i++;
}
if(cnt >= m && j - i + 1 < anslen) {
anslen = j - i + 1;
ansi = i;
ansj = j;
}
j++;
}
write(ansi), putchar(' '), write(ansj);
return 0;
}
Divisibility by 2^n
给定正数数列 $a_1\dots a_n$，你需要用最少次操作，使得 $2^n \mid \prod\limits_{i=1}^n a_i$。
在一次操作中，你可以选择一个 $i(1\le i\le n)$，让 $a_i$ 变为 $a_i\times i$。不能重复选取相同的 $i$。
求出最少的操作次数。
题解
记 $x$ 能贡献的因子 $2$ 的个数为 $\operatorname{count}(x)$。
若 $cnt=\sum\limits_{i=1}^n \operatorname{count}(a_i) \ge n$，则不用操作。
否则，我们发现每次乘法操作实际上只会贡献 $\operatorname{count}(i)$ 个 $2$，所以我们按 $\operatorname{count}(i)$ 的大小从大到小排序，贪心地加到原来的 $cnt$ 上，直到 $cnt\ge n$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + 10;
int f[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline int count(int x) {
int ret = 0;
while(!(x & 1)) x >>= 1, ret++;
return ret;
}
int solve(int cnt, int n) {
if(cnt >= n) return 0;
int ret = 0;
for(int i = 1; i <= n; i++) f[i] = count(i);
sort(f + 1, f + n + 1, greater<int>());
for(int i = 1; i <= n; i++) {
cnt += f[i];
ret++;
if(cnt >= n) return ret;
}
return -1;
}
int main() {
int t = read();
while(t--) {
int n = read(), cnt = 0;
bool flag = 1;
for(int i = 1; i <= n; i++) {
int x = read();
cnt += count(x);
}
write(solve(cnt, n)), putchar('\n');
}
return 0;
}
[NOIP2008 提高组] 传纸条
给定一个 $n$ 行 $m$ 列的矩阵，找到从 $(1,1)$ 到 $(n,m)$ 的两条不同的路径，使得经过的所有数之和最大。
$1 \le n,m\le 50$
题解
我们用 $dp(k,i,j)$ 表示一共走了 $k$ 步，第一个人往下走了 $i$ 步，第二个人往下走了 $j$ 步时的最大和。
容易从这三个信息算出，当前状态，第一个人处于 $(i,k-i+2)$，第二个人处于 $(j,k-j+2)$。则显然有状态转移方程如下：
\[dp(k,i,j)=\max[dp(k-1,i,j),dp(k-1,i-1,j), \\dp(k-1,i,j-1),dp(k-1,i-1,j-1)]+a_{i,k-i+2}+a_{j,k-j+2}\]需要特判 $i=j$ 的情况，重复加了一个数。
这里用滚动数组稍微优化了一下空间复杂度，降到了 $O(nm)$。时间复杂度为 $O(nmk)$，其中 $k=n+m-2$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 55;
int a[MAX_N][MAX_N], dp[2][MAX_N][MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), m = read();
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = read();
dp[0][1][1] = a[1][1];
bool lst, now;
for(int k = 1; k <= n + m - 2; k++) {
for(int i = 1; i <= n && i <= k + 1; i++) {
for(int j = 1; j <= n && j <+ k + 1; j++) {
if(k & 1) lst = 0, now = 1;
else lst = 1, now = 0;
int p = k - i + 2, q = k - j + 2;
int k1 = dp[lst][i][j];
int k2 = dp[lst][i - 1][j];
int k3 = dp[lst][i][j - 1];
int k4 = dp[lst][i - 1][j - 1];
dp[now][i][j] = max(k1, max(k2, max(k3, k4)));
if(i == j) dp[now][i][j] += a[i][p];
else dp[now][i][j] += a[i][p] + a[j][q];
}
}
}
write(dp[now][n][n]);
return 0;
}
灾后重建
给出 B 地区的村庄数 $N$，村庄编号从 $0$ 到 $N-1$，和所有 $M$ 条公路的长度，公路是双向的。并给出第 $i$ 个村庄重建完成的时间 $t_i$，你可以认为是同时开始重建并在第 $t_i$ 天重建完成，并且在当天即可通车。若 $t_i$ 为 $0$ 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 $Q$ 个询问 $(x,y,t)$，对于每个询问你要回答在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果无法找到从 $x$ 村庄到 $y$ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $x$ 或村庄 $y$ 在第 $t$ 天仍未重建完成，则需要返回 -1。
$t_0 ≤ t_1 ≤ … ≤ t_{N-1}$。$N≤200$，$M≤N \times (N-1)/2$，$Q≤50000$，询问时的 $t$ 不降。
题解
Floyd 参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 205, MAX_DIS = 1e9;
int n, m, dis[MAX_N][MAX_N], t[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
n = read(), m = read();
for(int i = 0; i < n; i++) t[i] = read();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
dis[i][j] = MAX_DIS;
}
}
for(int i = 0; i < m; i++) {
int u = read(), v = read(), w = read();
dis[u][v] = dis[v][u] = w;
}
for(int i = 0; i < n; i++) dis[i][i] = 0;
int q = read(), now = 0;
while(q--) {
int x = read(), y = read(), T = read();
while(t[now] <= T && now < n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(dis[i][j] > dis[i][now] + dis[now][j]) dis[i][j] = dis[i][now] + dis[now][j];
}
}
now++;
}
if(t[x] > T || t[y] > T || dis[x][y] == MAX_DIS) write(-1);
else write(dis[x][y]);
putchar('\n');
}
return 0;
}
三步必杀
往一个初始值为零的 $n$ 阶数列中进行 $m$ 次操作，每次操作选定一段 $[l, r]$，给定 $s$ 和 $e$，将 $[l,r]$ 每个数加上 $s\sim e$ 的等差数列。
题解
快乐推式子，差分两次。
下面用 $d$ 表示公差。
一阶差分数组的变化：
\[b[l] = b[l] + s\] \[b[x] = b[x] + d\] \[b[r + 1] = b[r + 1] - e\\\]二阶差分数组的变化：
\[c[l] = b[l] + s - b[l - 1] = c[l] + s\] \[c[l + 1] = b[l + 1] + d - (b[l] + s) = c[l + 1] + d - s\] \[c[x] = b[x] + d - b[x - 1] - d = c[x]\] \[c[r + 1] = b[r + 1] - e - (b[r] + d) = c[r + 1] - d - e\] \[c[r + 2] = b[r + 2] - (b[r + 1] - e) = c[r + 2] + e\]可知，改一阶是 $O(n)$ 的，直接改二阶则是 $O(1)$ 的，只用改固定的 $4$ 个。然后做两边前缀和即得到答案。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e7 + 10;
ll c[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
ll n = read(), m = read();
while(m--) {
ll l = read(), r = read(), s = read(), e = read();
ll d = (e - s) / (r - l);
c[l] += s, c[l + 1] += d - s, c[r + 1] -= d + e, c[r + 2] += e;
}
ll mx = 0, x = 0, y = 0, ans = 0;
for(int i = 1; i <= n; i++) {
y += c[i], x += y;
mx = max(mx, x);
ans ^= x;
}
write(ans), putchar(' '), write(mx);
return 0;
}
[BalticOI 2013 Day1] Ball Machine
有一个树型的机器，每个节点最多可以放一个球。有下面两种操作：
-
从根放入一个球，只要下方有空位，球会沿着树滚下。设 $f_i$ 表示以 $i$ 为根的子树内最小编号，如果同时有多个儿子节点是空的，那么会选 $f$ 值最小的儿子节点。球会一直下落直到没有空的子节点。
-
从某个位置拿走一个球，那么它上方的球会落下来。
每次给定一些操作，分别为在根节点放若干个球，和把某个节点的球拿走，求最后的结果。
- 如果 $opt=1$，代表在根节点放 $num$ 个球。输出最后一个球落到了哪里。
- 如果 $opt=2$，代表撤掉 $num$ 节点的球。输出撤掉那个球会有多少个球滚下来。
$1 \le N,Q \le 10^5$。
题解
模拟赛 Div.2 的 T1，居然是个紫题。场上暴力 dfs，每次操作 $1$ 需要 $O(num\cdot n)$ ，操作 $2$ 需要 $O(n)$，总的大概是个 $O(n^2)$ 以上，T 飞了。由于是捆绑测试，只得 $10pts$ (一个子任务)。
讲评没怎么听懂，不过在某谷上有原题所以可以看神犇的题解和代码，比较好懂。
首先 dfs 一遍求出 $f$ 值，然后按 $f$ 值把边排个序。
然后可以看出由于树是不动的，每个球最终落到地方的顺序是一定的。进一步说，这个顺序就是树的后序遍历序。所以我们把边按 $f$ 值 排序后 再 dfs 一遍，求出每个节点的序 $dfn_i$，然后用 priority_queue 维护 $dfn_i$ 最小的且没有球的节点 $i$。
对于操作 $1$，优先队列的 top 就是这个球应该去的地方，记录一下然后 pop，输出也顺便搞定了。单次操作时间复杂度 $O(num\cdot \log n)$
对于操作 $2$，我们在之前的 dfs 时顺便处理出 $fa_{u,i}$ 即 $u$ 的 $2^i$ 祖先，这样在每次操作时倍增地跳到第一个父亲没有球的祖先 $ffa$，球就是从它这里掉下来的，记录一下然后把它 push 进优先队列。可以直接输出，因为会有 $depth_{num}-depth_{ffa}$ 个球落下来。单次操作时间复杂度 $O(\log n)$
所以总的时间复杂度大概是 $O(n\log n)$？
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, MAX_LOG = 21;
vector<int> G[MAX_N];
int depth[MAX_N], dfn[MAX_N], f[MAX_N], fa[MAX_N][MAX_LOG], dfncnt;
bool ball[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
bool cmp(int x, int y) {return f[x] < f[y];}
struct cmp1 {bool operator() (const int &x, const int &y) const {return dfn[x] > dfn[y];}};
priority_queue<int, vector<int>, cmp1> pq;
void dfs1(int u) {
f[u] = u;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
dfs1(v);
f[u] = min(f[u], f[v]);
}
}
void dfs2(int u) {
for(int i = 1; (1 << i) <= depth[u]; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
depth[v] = depth[u] + 1;
fa[v][0] = u;
dfs2(v);
}
dfn[u] = ++dfncnt;
}
int main() {
int n = read(), q = read(), root;
for(int i = 1; i <= n; i++) {
int u = read();
G[u].push_back(i);
if(u == 0) root = i;
}
dfs1(root);
for(int i = 1; i <= n; i++) sort(G[i].begin(), G[i].end(), cmp);
depth[root] = 1;
dfs2(root);
for(int i = 1; i <= n; i++) pq.push(i);
while(q--) {
int op = read(), num = read();
if(op == 1) {
for(int i = 1; i <= num; i++) {
ball[pq.top()] = 1;
if(i == num) write(pq.top()), putchar('\n');
pq.pop();
}
}
else {
int ffa = num;
for(int i = MAX_LOG - 1; i >= 0; i--) {
if(ball[fa[ffa][i]]) {
ffa = fa[ffa][i];
}
}
ball[ffa] = 0;
pq.push(ffa);
write(depth[num] - depth[ffa]), putchar('\n');
}
}
return 0;
}
[ZJOI2008] 骑士
给定一个基环树组成的森林，求每个基环树的最大独立集之和。
题解
这题是 11.7 小模拟赛 T2 的原题。
基环树(环套树)指的是有 $n$ 个点 $n$ 条边的连通图，形如一棵树上多了一个唯一的环。
对于每一个基环树，我们可以这么做：先 dfs 一遍找到这个环的所在，然后随便选取环上的一条边 $(S,T)$，把这条边断掉，使得基环树变成树。然后做两次普通的树形 dp ($dp(i,0/1)$ 表示选或不选 $i$ 节点的最大独立集)：
\[dp(u,0) = \sum_{u\to v} \max(dp(v, 1),dp(v,0))\] \[dp(u,1) = \sum\limits_{u\to v} dp(v,0) + c_u\]然后这个基环树的答案就是 $\max(dp(S,0), dp(T,0))$。这是因为只要强制 $S$ 不选或者 $T$ 不选就能覆盖所有的情况。累加到最终答案即可。
一个小 Trick 就是我们如果用存编号的方式存图的话，E^1 的编号正好就是起点和终点反过来的那条边。因为我们先存了 $(u,v)$，再存了 $(v,u)$，它们的编号一定相邻，而 2^1=3, 3^1=2，正好对应了编号的相邻。所以删边的具体实现就是在 dp 的时候跳过 E 和 E^1 这两条边。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 10;
bool vis[MAX_N];
ll dp[MAX_N][2], c[MAX_N], S, T, E;
struct edge{int u, v;};
vector<edge> edges;
vector<int> G[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void AddEdge(int u, int v) {
edges.push_back({u, v});
G[u].push_back(edges.size() - 1);
}
void find_circle(int u, int fa) {
vis[u] = 1;
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v;
if(v == fa) continue;
if(vis[v]) {
S = u, T = v, E = G[u][i];
continue;
}
find_circle(v, u);
}
}
void dfs(int u, int fa) {
dp[u][1] = c[u], dp[u][0] = 0;
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v;
if(G[u][i] == E || G[u][i] == (E ^ 1) || v == fa) continue;
dfs(v, u);
dp[u][1] += dp[v][0];
dp[u][0] += max(dp[v][1], dp[v][0]);
}
}
int main() {
int n = read();
for(int i = 1; i <= n; i++) {
c[i] = read(); int v = read();
AddEdge(i, v); AddEdge(v, i);
}
ll ans = 0;
for(int i = 1; i <= n; i++) {
if(vis[i]) continue;
find_circle(i, -1);
ll ans1, ans2;
dfs(S, -1); ans1 = dp[S][0];
dfs(T, -1); ans2 = dp[T][0];
ans += max(ans1, ans2);
}
write(ans);
return 0;
}
然后 洛谷 P1453 这题是单棵基环树的版本，比较好做，不用 dfs 找环，可以并查集找环。
Lockdown
给定一棵 $n$ 个节点的树，每条边都有一个正的边权 $w$。有 $q$ 次询问，每次询问给出一个阈值 $K$ 与一个点 $v$，让你求出删掉所有 边权小于 $K$ 的边 后，点 $v$ 能到达多少个点。
题解
11.7 小模拟 T1，睡着了完全没写。起来直接看题解了，还好不太难（看了题解说话就是这么自信orz）。
我们发现询问完全可以离线处理，按每个询问的 $K$ 从大到小排序，这样我们就不用真的删边，只要把边权也排个序，每次把 $w\ge K$ 的边加上就可以，然后用并查集维护 $v$ 所在连通块的大小即可。很像 Kruskal。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
struct edge {
int u, v, w;
bool operator < (const edge &t) const {return w > t.w;}
} edges[MAX_N];
struct query {
int k, v, id, ans;
} querys[MAX_N];
bool cmp1(query a, query b) {return a.k > b.k;}
bool cmp2(query a, query b) {return a.id < b.id;}
int fa[MAX_N], siz[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
inline void U(int x, int y) {
int fx = find(x), fy = find(y);
if(fx != fy) {
fa[fx] = fy;
siz[fy] += siz[fx];
siz[fx] = 0;
}
}
int main() {
int n = read(), q = read();
for(int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
for(int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
edges[i] = (edge){u, v, w};
}
for(int i = 1; i <= q; i++) {
int k = read(), v = read();
querys[i] = (query){k, v, i, -1};
}
sort(edges + 1, edges + n);
sort(querys + 1, querys + q + 1, cmp1);
int p = 1;
for(int i = 1; i <= q; i++) {
int k = querys[i].k;
while(p < n && edges[p].w >= k) {
U(edges[p].u, edges[p].v);
p++;
}
querys[i].ans = siz[find(querys[i].v)] - 1;
}
sort(querys + 1, querys + q + 1, cmp2);
for(int i = 1; i <= q; i++) write(querys[i].ans), putchar('\n');
return 0;
}
- 上一篇 OI笔记 | 基础数据结构模板
- 下一篇 OI笔记 | 重链剖分笔记
♥