OI笔记 | 2022.11 做题记录（四）
NOIP 结束了。把 11 月写的剩下的题解搬上来（其实还剩 5 题没发，留着下次再发，以 10 题的量为分块标准）。
- 饥饿的奶牛
- [SCOI2005] 互不侵犯
- [SDOI2009] HH的项链
- [NOIP2014 提高组] 飞扬的小鸟
- 「KDOI-03」还原数据
- [NOI Online 2022 入门组] 数学游戏
- 地铁涨价
- 表达式的转换
- Qtree3
- d
饥饿的奶牛
给定 $n$ 个区间，选出若干个不重叠的区间，使得它们的长度之和最大。
题解
设计 $dp_i$ 表示前 $i$ 个区间的最大长度，则状态转移方程为：
\[dp_i = \max(dp_{i-1}, dp_{t}+a_i.len)\]其中 $t$ 为 $r<a_i.l$ 的最大区间，可以二分查找。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1.5e5 + 10;
struct range {
int L, R;
bool operator < (const range &t) const {return R < t.R;}
int length() {return R - L + 1;}
} a[MAX_N];
int dp[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline int search(int l, int r, int k) {
while(l < r - 1) {
int mid = (l + r) >> 1;
if(a[mid].R < k) l = mid;
else r = mid;
}
return l;
}
int main() {
int n = read();
for(int i = 1; i <= n; i++)
a[i].L = read(), a[i].R = read();
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++)
dp[i] = max(dp[i - 1], dp[search(0, i, a[i].L)] + a[i].length());
write(dp[n]);
return 0;
}
[SCOI2005] 互不侵犯
在 $N×N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。
题解
抄的。感受了一下状压dp的样子。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, cnt, ans, sta[2005], sit[2005], dp[15][2005][105];
inline ll read() {...}
inline void write(ll x) {...}
void dfs(ll now, ll num, ll p) {
if(p >= n) {
sit[++cnt] = now;
sta[cnt] = num;
return;
}
dfs(now, num, p + 1);
dfs(now + (1 << p), num + 1, p + 2);
}
bool cp(int x, int y) {return !((sit[x] & sit[y]) || ((sit[x] << 1) & sit[y]) || ((sit[x]) & (sit[y] << 1)));}
int main() {
n = read(), k = read();
dfs(0, 0, 0);
for(int i = 1; i <= cnt; i++) dp[1][i][sta[i]] = 1;
for(int i = 2; i <= n; i++)
for(int j = 1; j <= cnt; j++)
for(int x = 1; x <= cnt; x++)
if(cp(j, x))
for(int l = sta[j]; l <= k; l++)
dp[i][j][l] += dp[i - 1][x][l - sta[j]];
for(int i = 1; i <= cnt; i++) ans += dp[n][i][k];
write(ans);
return 0;
}
[SDOI2009] HH的项链
给定一个数组 $a$，有 $q$ 次询问，每次询问一个区间 $[l,r]$ 内有多少个不同的数。
题解
我们把询问离线，按 $r$ 排序。用树状数组维护前缀和，初始都为 $0$。
对每次询问，我们从上次询问的右端点扫到当前的右端点，把扫到的数的位置在树状数组中 $+1$，把这个数上一次出现的位置 $-1$。
于是答案为 $\operatorname{query}(r)-\operatorname{query}(l-1)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 10;
int a[MAX_N], pre[MAX_N], tree[MAX_N], n, q;
struct qr {
int l, r, id, ans;
} qs[MAX_N];
inline bool cmp1(qr a, qr b) {return a.r < b.r;}
inline bool cmp2(qr a, qr b) {return a.id < b.id;}
inline int lowbit(int x) {return x & -x;}
inline void update(int pos, int x) {
for(int i = pos; i <= n; i += lowbit(i))
tree[i] += x;
}
inline int query(int pos) {
int ret = 0;
for(int i = pos; i >= 1; i -= lowbit(i))
ret += tree[i];
return ret;
}
inline ll read() {...}
inline void write(ll x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + 48);
}
int main() {
n = read();
for(int i = 1; i <= n; i++)
a[i] = read();
q = read();
for(int i = 1; i <= q; i++) qs[i].l = read(), qs[i].r = read(), qs[i].id = i;
sort(qs + 1, qs + q + 1, cmp1);
int lst = 1;
for(int i = 1; i <= q; i++) {
for(int k = lst; k <= qs[i].r; k++) {
if(pre[a[k]]) update(pre[a[k]], -1);
update(k, 1);
pre[a[k]] = k;
}
lst = qs[i].r + 1;
qs[i].ans = query(qs[i].r) - query(qs[i].l - 1);
}
sort(qs + 1, qs + q + 1, cmp2);
for(int i = 1; i <= q; i++)
write(qs[i].ans), putchar('\n');
return 0;
}
[NOIP2014 提高组] 飞扬的小鸟
Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。
为了简化问题，我们对游戏规则进行了简化和改编:
游戏界面是一个长为 $n$，高为 $m$ 的二维平面，其中有 $k$ 个管道（忽略管道的宽度）。
小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。
小鸟每个单位时间沿横坐标方向右移的距离为 $1$，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 $x$，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 $y$。小鸟位于横坐标方向不同位置时，上升的高度 $x$ 和下降的高度 $y$ 可能互不相同。
小鸟高度等于 $0$ 或者小鸟碰到管道时，游戏失败。小鸟高度为 $m$ 时，无法再上升。
现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。
$5 \leq n \leq 10000$，$5 \leq m \leq 1000$，$0 \leq k < n$，$0 < x,y < m$，$0 < p < n$，$0 \leq l < h \leq m$， $l + 1 < h$。
题解
全是看题解做的，有点难。
设在横坐标为 $i$ 时点击一次的上升高度为 $up_i$，不点击的下降高度为 $down_i$。
考虑用 $dp(x,y,0/1)$ 表示位于位置 $(x,y)$ 时点击或不点击时的最少点击屏幕数。则考虑没有柱子时的朴素转移：
\[dp(x,y,0)=\min(dp(x-1,y+down_i,0), dp(x,y,1))\]即在上个位置不点，或在这个位置点。
\[dp(x,y,1)=\min(dp(x-1,y-up_i,0/1),dp(x,y-up_i,1))+1\]即在上一个位置点或不点，或在这个位置点。
然后考虑直接把最后一维滚动掉，不影响结果。又因为只会从 $x-1$ 转移，也可以把第一维滚动掉。然后每次转移时要初始化，把 $dp(x,1\sim m)$ 全设为 $\inf$。还要注意当 $y> m$ 时的特判。
考虑管道的处理，我们把管道的横坐标排序，当遇到管道时，判断能否通过：把 $dp(x,0\sim l),dp(x, h\sim m)$ 都设为 $\inf$，然后判断所有 $dp(x, 0\sim m)$ 的最小值如果还是 $\inf$，则不能通过，输出当前管道数 $-1$。
如果顺利通过所有管道，则答案为 $\min\limits_{y=1}^mdp(n,y)$。
洛谷上的题解写的更详细一些。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX_N = 1e4 + 10, INF = 1e13;
ll dp[2][MAX_N], up[MAX_N], down[MAX_N];
struct bl {
ll x, l, h;
bool operator < (const bl &t) const {
return x < t.x;
}
} bls[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
ll n = read(), m = read(), k = read();
for(int i = 1; i <= n; i++)
up[i] = read(), down[i] = read();
for(int i = 1; i <= k; i++)
bls[i].x = read(), bls[i].l = read(), bls[i].h = read();
sort(bls + 1, bls + k + 1);
bool now = 0; ll cnt = 1;
for(int i = 1; i <= n; i++) {
now ^= 1;
for(int j = 0; j <= m; j++)
dp[now][j] = INF;
for(int j = up[i] + 1; j <= up[i] + m; j++)
dp[now][j] = min(dp[now ^ 1][j - up[i]] + 1, dp[now][j - up[i]] + 1);
for(int j = m + 1; j <= up[i] + m; j++)
dp[now][m] = min(dp[now][j], dp[now][m]);
for(int j = 1; j <= m - down[i]; j++)
dp[now][j] = min(dp[now][j], dp[now ^ 1][j + down[i]]);
if(i == bls[cnt].x) {
ll minn = INF;
for(int j = 0; j <= bls[cnt].l; j++)
dp[now][j] = INF;
for(int j = bls[cnt].h; j <= m; j++)
dp[now][j] = INF;
for(int j = 1; j <= m; j++)
minn = min(minn, dp[now][j]);
if(minn == INF) {
write(0), putchar('\n'), write(cnt - 1);
return 0;
}
cnt++;
}
}
ll ans = INF;
for(int j = 1; j <= m; j++)
ans = min(ans, dp[now][j]);
write(1), putchar('\n'), write(ans);
return 0;
}
「KDOI-03」还原数据
小 E 正在做一道经典题：
给定一个长度为 $n$ 的序列 $a$ 和 $q$ 个操作，操作共有 $2$ 种类型：
- $\tt{1~l~r~x}$：对于所有 $l\le i\le r$，$a_i\leftarrow a_i+x$。
- $\tt{2~l~r~x}$：对于所有 $l\le i\le r$，$a_i\leftarrow \max(a_i,x)$。
题目要求输出所有操作结束后的最终序列 $a’$。
小 E 迅速写了一份代码提交，但是发现，由于宇宙射线的影响，输入数据出现了一些小问题。具体地，对于所有 $2$ 操作，操作中给出的 $x$ 均被丢失了，也就是说，输入数据中的 $2$ 操作只剩下了 $\tt{2~l~r}$。输出数据则没有问题。小 E 现在想要通过剩余的数据恢复原来的输入数据，请你帮助他完成这个任务。
当然，可能会有多种合法的输入数据，你需要找到其中任意一种。数据保证有解。
题解
考虑 $a_i \gets \max(a_i, x)$ 操作前面会被后面的覆盖，所以我们考虑以 $a’$ 为初始数组，倒序考虑操作。
操作 $1$ 直接变成区间减。
设 $M=\min\limits_{i=l}^r a_i$，由于操作 $2$ 相当于把区间内所有小于 $x$ 的数都改成 $x$，所以恒有 $x\le M$。
则 $x$ 恰好取 $M$ 即可，这能使尽可能多的值靠近最终值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX_N = 1e5 + 10, INF = 1e18;
ll a[MAX_N], d[MAX_N << 2], b[MAX_N << 2];
struct opt {ll op, l, r, val;} ops[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return s + ((t - s) >> 1);}
inline void pu(int p) {d[p] = min(d[lc(p)], d[rc(p)]);}
inline void pd(int p) {
if(b[p]) {
d[lc(p)] += b[p], d[rc(p)] += b[p];
b[lc(p)] += b[p], b[rc(p)] += b[p];
b[p] = 0;
}
}
void build_tree(int s, int t, int p) {
b[p] = 0;
if(s == t) {d[p] = a[s]; return;}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
pu(p);
}
void update(int s, int t, int p, int l, int r, ll k) {
if(l <= s && t <= r) {
d[p] += k, b[p] += k;
return;
}
pd(p);
int m = mid(s, t);
if(l <= m) update(s, m, lc(p), l, r, k);
if(r > m) update(m + 1, t, rc(p), l, r, k);
pu(p);
}
ll query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) return d[p];
pd(p);
int m = mid(s, t);
ll ret = INF;
if(l <= m) ret = min(ret, query(s, m, lc(p), l, r));
if(r > m) ret = min(ret, query(m + 1, t, rc(p), l, r));
return ret;
}
int main() {
ll T = read();
while(T--) {
ll n = read(), q = read(), x;
for(int i = 1; i <= n; i++)
x = read();
for(int i = 1; i <= q; i++) {
ll op = read(), l = read(), r = read();
x = (op == 1 ? read() : -1);
ops[i] = {op, l, r, x};
}
for(int i = 1; i <= n; i++)
a[i] = read();
build_tree(1, n, 1);
vector<ll> ans;
for(int i = q; i >= 1; i--) {
opt t = ops[i];
if(t.op == 1) update(1, n, 1, t.l, t.r, -t.val);
else ans.push_back(query(1, n, 1, t.l, t.r));
}
for(int i = ans.size() - 1; i >= 0; i--)
write(ans[i]), putchar(' ');
putchar('\n');
}
return 0;
}
[NOI Online 2022 入门组] 数学游戏
给出 $z,x$，求满足下式的最小正整数 $y$。
\[z=x\times y\times \gcd(x, y)\]若无解，输出 -1。
题解
设 $x=d\times a,y=d\times b$，其中 $\gcd(a,b)=1$，从而 $\gcd(x,y)=d$。
设 $\frac{z}{x}=M$，则 $M$ 已知，原式等价于
\[M=y\times \gcd(x,y)=d^2\times b\]考虑 $\gcd(M,x^2)=\gcd(d^2\times b, d^2\times a^2)=d^2$，则容易求出 $d$，也就容易求出 $y$。
\[y=d\times b=\frac{d^2\times b}{d}=\frac{M}{\sqrt{\gcd(M,x^2)}}\]代入求解即可。无解的情况就是 $z\nmid x$ 或 $\gcd(M,x^2)$ 不是完全平方数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
ll gcd(ll x, ll y) {return x % y == 0 ? y : gcd(y, x % y);}
int main() {
ll t = read();
while(t--) {
ll x = read(), z = read();
if(z % x != 0) {
write(-1), putchar('\n');
continue;
}
ll M = z / x, g = gcd(M, x * x), sq = sqrt(g);
if(sq * sq != g) {
write(-1), putchar('\n');
continue;
}
write(M / sq), putchar('\n');
}
return 0;
}
地铁涨价
博艾地铁系统是一个无向连通图，有 $N$ 个地铁站，同时有 $M$ 小段地铁连接两个不同的站。每经过一小段铁路（连接直接相邻的两个点的一条边），就要收取 $1$ 博艾元，显然选择最短路来坐车的话，票价最便宜。
博艾地铁公司打算提价。提价一次就是将一小段铁路原来收费 $1$ 元改收 $2$ 元。同一小段的铁路不会多次提价。他们打算提价 $Q$ 次。
学校在 $1$ 号节点，学生在其他各个站点。如果他们到学校的一条最短路径中的一小段提价了，可能可以改变路径，使总票价不变。当居住在某个站附近的学生发现，提价后，没有任何一种方案可以从家到学校的费用和初始费用相等时，就会不满。
对于每一次涨价，有多少个站，学生会因为涨价而不满呢？
$N\le100000, Q\le M\le 200000$
题解
涨价相当于删边，与其真的删边，不如离线下来倒序加边，询问的就是每个站点到 $1$ 的距离变成原来的最短路的时间。
由于边权为 $1$，可以 bfs 一遍 $O(n)$ 求出原来 $1$ 到每个点的最短路 $dis_i$。
然后把所有边删掉，先加上不会被涨价的边，跑一遍 bfs，处理出现在的距离 $d_i$。
倒序枚举涨价的边，我们先判断这次加边前有多少点到 $1$ 的距离会变得和原来一样，然后把这次涨价的边加上。
至于判断的方法，只需要考虑当前的边 $(u,v)$。如果满足 $dis_u=d_u$ 且 $dis_v=d_u+1$ 且 $dis_v \neq d_v$，则 $v$ 也满足条件。也就是通过 $u$ 已经满足条件来推出 $v$ 满足条件。
确定 $v$ 满足条件后，再从 $v$ 出发 dfs 一下，和上面一样更新附近所有满足条件的边，统计这次有多少点 新变成 满足条件的点。答案只要加前缀和就行。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2e5 + 10;
int n, m, q, dis[MAX_N], d[MAX_N], r[MAX_N], ans[MAX_N], cnt;
bool vis[MAX_N], del[MAX_N];
struct edge {int u, v;};
vector<edge> edges;
vector<int> G[MAX_N];
void AddEdge(int u, int v) {
edges.push_back({u, v});
G[u].push_back(edges.size() - 1);
}
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
inline void bfs(bool type) {
queue<int> q; q.push(1); vis[1] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < (int)G[u].size(); i++) {
int v = edges[G[u][i]].v;
if(vis[v]) continue;
if(!type) dis[v] = dis[u] + 1;
else d[v] = d[u] + 1;
vis[v] = 1;
q.push(v);
}
}
}
void dfs(int u, int pre) {
for(int i = 0; i < (int)G[u].size(); i++) {
int v = edges[G[u][i]].v;
if(v != pre && dis[v] == d[u] + 1 && dis[v] != d[v])
d[v] = dis[v], cnt++, dfs(v, u);
}
}
int main() {
n = read(), m = read(), q = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read();
AddEdge(u, v), AddEdge(v, u);
}
for(int i = 1; i <= q; i++)
r[i] = read(), del[r[i]] = 1;
bfs(0);
for(int i = 1; i <= n; i++)
G[i].clear(), vis[i] = 0;
for(int i = 1; i <= m; i++) {
if(!del[i]) {
int u = edges[(i << 1) - 1].u, v = edges[(i << 1) - 1].v;
AddEdge(u, v), AddEdge(v, u);
}
}
bfs(1);
for(int i = q; i >= 1; i--) {
cnt = 0;
int u = edges[(r[i] << 1) - 1].u, v = edges[(r[i] << 1) - 1].v;
if(dis[u] == d[u] && dis[v] == d[u] + 1 && dis[v] != d[v])
cnt++, d[v] = dis[v], dfs(v, u);
swap(u, v);
if(dis[u] == d[u] && dis[v] == d[u] + 1 && dis[v] != d[v])
cnt++, d[v] = dis[v], dfs(v, u);
AddEdge(u, v), AddEdge(v, u);
ans[i] = cnt;
}
for(int i = 1; i <= q; i++)
ans[i] += ans[i - 1], write(ans[i]), putchar('\n');
return 0;
}
表达式的转换
给定中缀表达式，转化为后缀表达式。
例如给定 8-(3+2*6)/5+4，你要输出后缀表达式的计算过程：
8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9
输入的符号中只有这些基本符号 0123456789+-*/^()。注意 ^ 是右结合性的： $a^{b^c}=a^{(b^c)}\neq(a^b)^c$。
题解
大模拟。以下步骤来自 oi-wiki：
-
如果遇到数字，直接输出该数字。
-
如果遇到左括号，那么将其放在运算符栈上。
-
如果遇到右括号，不断输出栈顶元素，直至遇到左括号，左括号出栈。换句话说，执行一对括号内的所有运算符。
-
如果遇到其他运算符，不断输出所有运算优先级大于等于当前运算符的运算符。最后，新的运算符入运算符栈。
-
在处理完整个字符串之后，一些运算符可能仍然在堆栈中，因此把栈中剩下的符号依次输出，表达式转换结束。
这里的输出指的是输出到后缀表达式中。需要注意的是，乘方 ^ 为右结合的运算符，所以判断优先级方面，需要把原来的 >= 改为 >，以滞后 ^ 的输出。
计算的子任务模拟即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
bool type;
int num; char op;
};
vector<node> f;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
bool OP(char c) {return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');}
int priority(char c) {
if(c == '^') return 3;
if(c == '*' || c == '/') return 2;
if(c == '+' || c == '-') return 1;
return -1;
}
void AddOp(char c) {
node t;
t.type = 0, t.op = c;
f.push_back(t);
}
void AddNum(int num) {
node t;
t.type = 1, t.num = num;
f.push_back(t);
}
int main() {
string s;
cin >> s;
stack<char> op;
for(int i = 0; i < (int)s.size(); i++) {
if(s[i] == '(') op.push('(');
else if(s[i] == ')') {
while(op.top() != '(') {
putchar(op.top()), putchar(' ');
AddOp(op.top());
op.pop();
}
op.pop();
}
else if(OP(s[i])) {
char cur = s[i];
while(!op.empty() && ((cur == '^' && priority(op.top()) > priority(cur)) || (cur != '^' && priority(op.top()) >= priority(cur)))) {
putchar(op.top()), putchar(' ');
AddOp(op.top());
op.pop();
}
op.push(cur);
}
else {
int num = 0;
while(i < (int)s.size() && isdigit(s[i]))
num = (num << 1) + (num << 3) + (s[i++] ^ 48);
i--;
write(num), putchar(' ');
AddNum(num);
}
}
while(!op.empty()) {
putchar(op.top()), putchar(' ');
AddOp(op.top());
op.pop();
}
putchar('\n');
vector<int> st;
for(int i = 0; i < (int)f.size(); i++) {
node t = f[i];
if(t.type == 1) st.push_back(t.num);
else {
char cur = t.op;
int a = st.back(); st.pop_back();
int b = st.back(); st.pop_back();
int res;
if(cur == '^') res = pow(b, a);
if(cur == '+') res = a + b;
if(cur == '-') res = b - a;
if(cur == '*') res = a * b;
if(cur == '/') res = b / a;
st.push_back(res);
for(int j = 0; j < (int)st.size(); j++)
write(st[j]), putchar(' ');
for(int j = i + 1; j < (int)f.size(); j++) {
if(f[j].type == 0) putchar(f[j].op);
else write(f[j].num);
putchar(' ');
}
putchar('\n');
}
}
return 0;
}
Qtree3
给出 $N$ 个点的一棵树（$N-1$ 条边），节点有白有黑，初始全为白。
有两种操作：
0 i：改变某点的颜色（原来是黑的变白，原来是白的变黑）。
1 v：询问 $1$ 到 $v$ 的路径上的第一个黑点，若无，输出 $-1$。
题解
不妨用 set 维护一条重链上的所有黑点，按 $dfn$ 排序，这样 set.begin() 即为这条重链上的第一个黑点。
向上跳到 $1$ 号节点，维护答案的最小值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int n, q;
vector<int> G[MAX_N];
int siz[MAX_N], dep[MAX_N], fa[MAX_N], hson[MAX_N];
int dfn[MAX_N], top[MAX_N], rnk[MAX_N], col[MAX_N], dfncnt;
set<int> blk[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void dfs1(int u, int pre) {
siz[u] = 1, hson[u] = -1;
for(int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if(v == pre) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
dfs1(v, u);
siz[u] += siz[v];
if(hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp;
dfn[u] = ++dfncnt;
rnk[dfncnt] = u;
if(hson[u] == -1) return;
dfs2(hson[u], tp);
for(int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if(v != hson[u] && v != fa[u]) dfs2(v, v);
}
}
int main() {
n = read(), q = 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), dfs2(1, 1);
while(q--) {
int op = read(), x = read();
if(op == 0) {
if(!col[x]) blk[top[x]].insert(dfn[x]);
else blk[top[x]].erase(dfn[x]);
col[x] ^= 1;
}
else {
int ans = -1;
while(x) {
if(!blk[top[x]].empty()) {
int t = *blk[top[x]].begin();
if(dep[rnk[t]] <= dep[x]) ans = rnk[t];
}
x = fa[top[x]];
}
write(ans), putchar('\n');
}
}
return 0;
}
d
给定一张 $n$ 个点的图，初始没有边，有 $q$ 次操作：
1 x y ：加一条 $x,y$ 之间的边，边权为 $1$。
2 x ：询问从点 $x$ 开始，不经过重复的点，能走到的最远距离。
保证加边的过程中对于任意两个点之间，只有唯一的一条简单路径。
题解
题面告诉我们这是一棵树。
考虑用启发式合并的并查集维护当前 $x$ 所在的连通块，以及这个连通块的直径两端 $L,R$。那么考虑 $x$ 能走到的最远距离一定为到直径两端的距离，即 $\max(\operatorname{dis}(x,L), \operatorname{dis}(x,R))$。
求 $\operatorname{dis}(x,y)$ 可以用 $\operatorname{dis}(x,y)=dep_x + dep_y - 2\times dep_{\operatorname{lca}(x,y)}$，为此我们在合并的时候需要 dfs 一遍处理出新的 $dep_i$ 和 新的用于倍增的 $fa_{i,j}$。
考虑合并时如何确定新的连通块的直径两端 $L, R$，可以证明，若原来两个连通块的直径为 $Lx,Rx,Ly,Ry$，则 $L,R\in{Lx, Rx, Ly, Ry}$。可以直接枚举出距离最大的两点，只需比较 $\binom{4}{2}=6$ 次。(crc 的神仙写法)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 3e5 + 10, MAX_LOG = 20;
vector<int> G[MAX_N];
int dep[MAX_N], f[MAX_N], L[MAX_N], R[MAX_N], siz[MAX_N];
int fa[MAX_N][MAX_LOG];
inline ll read() {...}
inline void write(ll x) {...}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[x][i] && dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if(x == y) return y;
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[x][i] && fa[y][i] && fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int dis(int x, int y) {return dep[x] + dep[y] - 2 * dep[lca(x, y)];}
int find(int x) {
if(x == f[x]) return x;
return f[x] = find(f[x]);
}
void dfs(int u, int pre) {
dep[u] = dep[pre] + 1;
fa[u][0] = pre;
for(int i = 1; i < MAX_LOG; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if(v == pre) continue;
dfs(v, u);
}
}
void U(int x, int y) {
int fx = find(x), fy = find(y);
if(siz[fx] < siz[fy]) swap(x, y), swap(fx, fy);
siz[fx] += siz[fy], f[fy] = fx;
dfs(y, x);
int Lx = L[fx], Ly = L[fy], Rx = R[fx], Ry = R[fy];
G[x].push_back(y), G[y].push_back(x);
int mx = 0, nd, nx, ny;
nd = dis(Lx, Ly); if(nd > mx) mx = nd, nx = Lx, ny = Ly;
nd = dis(Lx, Rx); if(nd > mx) mx = nd, nx = Lx, ny = Rx;
nd = dis(Lx, Ry); if(nd > mx) mx = nd, nx = Lx, ny = Ry;
nd = dis(Ly, Rx); if(nd > mx) mx = nd, nx = Ly, ny = Rx;
nd = dis(Ly, Ry); if(nd > mx) mx = nd, nx = Ly, ny = Ry;
nd = dis(Rx, Ry); if(nd > mx) mx = nd, nx = Rx, ny = Ry;
L[fx] = nx, R[fx] = ny;
}
int main() {
bool type = read();
int n = read(), q = read(), lst = 0;
for(int i = 1; i <= n; i++)
f[i] = L[i] = R[i] = i, dep[i] = siz[i] = 1;
for(int i = 1; i <= q; i++) {
int op = read();
if(op == 1) {
int u = read(), v = read();
if(type) u ^= lst, v ^= lst;
U(u, v);
}
else {
int x = read();
if(type) x ^= lst;
int fx = find(x);
write(lst = max(dis(x, L[fx]), dis(x, R[fx])));
putchar('\n');
}
}
return 0;
}
♥