给定一棵有根树，每次询问前$i$条边组成的森林中，第$c_i$个点为根的树的深度。
- $2\leq n\leq 10^6$
- $1\leq a_i,b_i,c_i\leq n,a_i\neq b_i$
带权并查集，维护每个节点在当前所属树的层数，维护所有以该节点为根节点的树的深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| int deep[maxn], fa[maxn], dis[maxn];
int findfa(int x) {
if (x == fa[x])return x;
int fx = findfa(fa[x]);
// 更新deep,旧根:fa[x],新根:fx
deep[x] += deep[fa[x]];
return fa[x] = fx;
}
void merge(int u, int v) {
int fu = findfa(u);
fa[v] = fu;
deep[v] = deep[u] + 1;
dis[fu] = max(dis[fu], dis[v] + deep[v]);
}
void solve() {
int n;cin >> n;
for (int i = 1;i <= n;i++) {
fa[i] = i;
deep[i] = 0;
dis[i] = 0;
}
for (int i = 1;i <= n - 1;i++) {
int u, v, c;cin >> u >> v >> c;
merge(u, v);
cout << dis[c] << " ";
}
cout << "\n";
}
|
给出一个排列，每次选择四个位置交换其中的元素，求将该排列排序成上升序列的最小操作次数。
- $1\leq t\leq 10^5$
- $1\leq n\leq 10^6$
令$p_i$是排序之后数$a_i$的位置，每个$(p_i,a_i)$对应了一个关系。易知这样的关系会形成若干个环，如果环的长度是$3$或$4$，则一次交换可以让这个环上的数字都归位，如果是大于$4$的环，每次在这个环上进行一次操作可以让环的长度减少$3$，如果是两个长度为$2$的环，则一次操作可以让两个长度为$2$的环归位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| int p[maxn], fa[maxn], len[maxn];
int findfa(int x) {
if (x == fa[x])return x;
int fx = findfa(fa[x]);
len[fa[x]] = len[fx];
return fa[x] = fx;
}
void merge(int x, int y) {
int fx = findfa(x), fy = findfa(y);
if (fx == fy)return;
fa[fx] = fy;
len[fy] += len[fx];
}
void solve() {
int n;cin >> n;
for (int i = 1;i <= n;i++) {
len[i] = 1;fa[i] = i;
}
for (int i = 1;i <= n;i++) {
cin >> p[i];
merge(i, p[i]);
}
map<int, int>mp;
for (int i = 1;i <= n;i++) {
int fx = findfa(i);
if (mp.count(fx))continue;
mp[fx] = len[fx];
}
int ans = 0, cnt2 = 0;
for (auto [i, s] : mp) {
if (s == 1)continue;
else if (s == 3 || s == 4)ans++;
else if (s > 4) {
int t = s / 3;
ans += t;
if (s % 3 == 2) {
cnt2++;
}
}
else cnt2++;
}
ans += (cnt2 + 1) / 2;
cout << ans << "\n";
}
|
一棵树，树上的边权都是$1$，定义$f(u)=\sum_v dis(u,v)$，给出一个$x$，寻找一个满足存在两个点$u,v$使得$f(u)-f(v)=x$成立的最少节点子树，输出节点数。
- $1\leq t\leq 10^5$
- $1\leq x \leq 10^{18}$
$f(u)$为点$u$到各个其他节点的距离之和，只有$u\rightarrow v$一条路径的时候，$f(u)=f(v)=dia(u,v)$，若要增加$f(u)$和$f(v)$之间的差值，每在$v$上增加一个在$v$的子树中的节点，$f(u)-f(v)$的值就会增加一倍$dis(u,v)$。
当有奇数个点，$2\times k +1$个点，另$dis(u,v)=k$，剩余$k$个点都是$v$的子树中的节点，$f(u)-f(v)$最大是$k^2$。
当有偶数个点，$2\times k+2$，同理，$f(u)-f(v)$的最大值是$k(k+1)$。
下一个奇数是$(k+1)^2$，再下一个偶数的是$(k+1)(k+2)$…
故对于一个确定的$x$，我们需要确定落在哪个$(k^2,(k+1)^2]$区间，然后再确定是在区间$(k^2,k(k+1)]$还是$(k(k+1),(k+1)^2]$，也就是点数应该至少是大于$2\times k+1$还是$2\times k+2$。
在区间$(k(k+1),(k+1)^2)$中，一定可以构造出$2\times k+3$的方法；
在区间$(k^2,k(k+1)]$中，如果$k$为奇数，可以构造出$2\times k+3$，如果$k$为偶数，可以构造出$2\times k+2$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void solve() {
ll x;cin >> x;
ll k = sqrtl(x); // 注意开方long long
if (k * k == x) {
cout << 2 * k + 1 << "\n";
}
else if (k * (k + 1) < x) {
cout << 2 * k + 3 << "\n";
}
else if ((x - k * k) % 2ll != k % 2ll) {
cout << 2 * k + 3 << "\n";
}
else {
cout << 2 * k + 2 << "\n";
}
}
|
将军饮马问题。在平面坐标轴中，只有$x、y$轴的飞负半轴是水源，给出马儿的坐标和营地的坐标，求最短距离。
- $1\leq t\leq 10^5$
- $0\leq x_G,y_G,x_T,u_T\leq 10^9$
将坐标按坐标轴对称，求距离。
1
2
3
4
5
6
7
8
9
10
11
12
| ld dist(ld r, ld c) {
return sqrt(r * r + c * c);
}
void solve() {
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
ld ans1 = dist(1.0 * abs(y1 - y2), 1.0 * (abs(x1) + abs(x2)));
ld ans2 = dist(1.0 * (abs(y1) + abs(y2)), 1.0 * abs(x1 - x2));
ld ans = min(ans1, ans2);
printf("%.12lf\n", ans);
}
|
可以选择任意坐标$p$，进行如下二选一操作：
- 若符合$a_i\leq a_p$，可以重新赋值$a_i\leftarrow a_i + 2(a_p-a_i)$。
- 若符合$a_i\geq a_p$，可以重新赋值$a_i \leftarrow a_i-a(a_i-a_p)$
可以进行上述操作若干次，求问可以将$a$数组的范围收敛到多小。
- $1\leq t\leq 5\times 10^5$
- $1\leq n\leq 10^5$
- $0\leq a_i\leq 10^{16}$
上面的操作可以进行无数次，通过模拟可以意识到，这是一个类似折纸的操作，是将某个数沿着某条线折叠到另一边的操作。注意到每次操作不是必须要对每个$a_i$进行这样的翻折的，例如当$a_i\lt a_p$时选择操作2，可以避免$a_i$的翻折。
通过翻折让数组的范围收束到最小。假设当前只有3个各不相同的数，这三个数从小到大排列之后是${a,b,c}$，那么在数轴上形成了距离$x=b-a$和$y=c-b$，对于这三个数来说，通过折叠，假设是$a$沿着$b$向$c$折叠，将$x$变为$x\bmod y$（不断沿着$y$的两边折叠，直到落在$b、c$之间），若此时$x\neq 0$，则$y$也可以通过一样的方法收束到小于$x$的某个长度。故获得的最小的范围应该是$x、y$的$gcd$。
同样的思想可以拓展到多个数的时候。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| ll a[maxn];
void solve() {
int n;cin >> n;
for (int i = 0;i < n;i++) { cin >> a[i]; }
sort(a, a + n);
if (n == 1) {
cout << 0 << "\n";
return;
}
if (n == 2) {
cout << a[1] - a[0] << "\n";
return;
}
ll ans = a[1] - a[0];
for (int i = 2;i < n;i++) {
ans = gcd(ans, a[i] - a[i - 1]);
}
cout << ans << "\n";
}
|
$n$个人从左到右排成一排，编号从$1$到$n-1$，这$n$个人之间有$m$对好朋友，求有多少个区间$[l,r]$中每两对都是好朋友。
假设已有一个区间$[l,r]$符合要求，且$r$是以$l$为左端点的时候最远的符合要求的右端点。那么显然有：
当加入$r+1$时，$r+1$号与$[l,r]$中的至少一个人不是好友关系。同时，区间$[l+1,r]$是一个友好区间，于是在移动左端点时，右端点只需要从上一个左端点的最远右端点开始检查即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| void solve() {
int n, m;cin >> n >> m;
vector<map<int, bool>>links(n + 1);
for (int i = 0;i < m;i++) {
int u, v;cin >> u >> v;
links[u][v] = true;
links[v][u] = true;
}
int ans = 0;
int prer = 1;
for (int i = 1;i <= n;i++) {
int j = prer;
while (j <= n) {
// check
bool f = true;
for (int k = i;k < j;k++) {
if (links[j].count(k))continue;
f = false;
break;
}
if (!f)break;
j++;
}
ans += j - i;
prer = j - 1;
}
cout << ans << "\n";
}
|
