A-LCT
题意
给定一棵有根树，每次询问前条边组成的森林中，第个点为根的树的深度。
数据范围
思路
带权并查集，维护每个节点在当前所属树的层数，维护所有以该节点为根节点的树的深度。
代码
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";
}C-Sort4
题意
给出一个排列，每次选择四个位置交换其中的元素，求将该排列排序成上升序列的最小操作次数。
数据范围
思路
令是排序之后数的位置，每个对应了一个关系。易知这样的关系会形成若干个环，如果环的长度是或，则一次交换可以让这个环上的数字都归位，如果是大于的环，每次在这个环上进行一次操作可以让环的长度减少，如果是两个长度为的环，则一次操作可以让两个长度为的环归位。
代码
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";
}F-Good Tree
题意
一棵树，树上的边权都是，定义，给出一个，寻找一个满足存在两个点使得成立的最少节点子树，输出节点数。
数据范围
思路
为点到各个其他节点的距离之和，只有一条路径的时候，，若要增加和之间的差值，每在上增加一个在的子树中的节点，的值就会增加一倍。
当有奇数个点，个点，另，剩余个点都是的子树中的节点，最大是。
当有偶数个点，，同理，的最大值是。
下一个奇数是，再下一个偶数的是…
故对于一个确定的，我们需要确定落在哪个区间，然后再确定是在区间还是，也就是点数应该至少是大于还是。
在区间中，一定可以构造出的方法；
在区间中，如果为奇数，可以构造出，如果为偶数，可以构造出。
代码
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";
}
}G-Horse Drinks Water
题意
将军饮马问题。在平面坐标轴中，只有轴的飞负半轴是水源，给出马儿的坐标和营地的坐标，求最短距离。
数据范围
思路
将坐标按坐标轴对称，求距离。
代码
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);
}H-Yet Another Origami Problem
题意
可以选择任意坐标，进行如下二选一操作：
- 若符合，可以重新赋值。
- 若符合，可以重新赋值
可以进行上述操作若干次，求问可以将数组的范围收敛到多小。
数据范围
思路
上面的操作可以进行无数次，通过模拟可以意识到，这是一个类似折纸的操作，是将某个数沿着某条线折叠到另一边的操作。注意到每次操作不是必须要对每个进行这样的翻折的，例如当时选择操作2，可以避免的翻折。
通过翻折让数组的范围收束到最小。假设当前只有3个各不相同的数，这三个数从小到大排列之后是，那么在数轴上形成了距离和，对于这三个数来说，通过折叠，假设是沿着向折叠，将变为（不断沿着的两边折叠，直到落在之间），若此时，则也可以通过一样的方法收束到小于的某个长度。故获得的最小的范围应该是的。
同样的思想可以拓展到多个数的时候。
代码
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";
}I-Friends
题意
个人从左到右排成一排，编号从到，这个人之间有对好朋友，求有多少个区间中每两对都是好朋友。
数据范围
思路
假设已有一个区间符合要求，且是以为左端点的时候最远的符合要求的右端点。那么显然有：
当加入时，号与中的至少一个人不是好友关系。同时，区间是一个友好区间，于是在移动左端点时，右端点只需要从上一个左端点的最远右端点开始检查即可。
代码
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";
}