🫟2024牛客暑假多校训练营Day4||补题

A-LCT

题意

给定一棵有根树，每次询问前 $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
int deep[maxn], fa[maxn], dis[maxn];
2
int findfa(int x) {
3
    if (x == fa[x])return x;
4
    int fx = findfa(fa[x]);
5
    // 更新deep,旧根:fa[x],新根:fx
6
    deep[x] += deep[fa[x]];
7
    return fa[x] = fx;
8
}
9

10
void merge(int u, int v) {
11
    int fu = findfa(u);
12
    fa[v] = fu;
13
    deep[v] = deep[u] + 1;
14
    dis[fu] = max(dis[fu], dis[v] + deep[v]);
15
}
16

17
void solve() {
18
    int n;cin >> n;
19
    for (int i = 1;i <= n;i++) {
20
        fa[i] = i;
21
        deep[i] = 0;
22
        dis[i] = 0;
23
    }
24
    for (int i = 1;i <= n - 1;i++) {
25
        int u, v, c;cin >> u >> v >> c;
26
        merge(u, v);
27
        cout << dis[c] << " ";
28
    }
29
    cout << "\n";
30
}

C-Sort4

题意

给出一个排列，每次选择四个位置交换其中的元素，求将该排列排序成上升序列的最小操作次数。

数据范围

$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
int p[maxn], fa[maxn], len[maxn];
2

3
int findfa(int x) {
4
    if (x == fa[x])return x;
5
    int fx = findfa(fa[x]);
6
    len[fa[x]] = len[fx];
7
    return fa[x] = fx;
8
}
9

10
void merge(int x, int y) {
11
    int fx = findfa(x), fy = findfa(y);
12
    if (fx == fy)return;
13
    fa[fx] = fy;
14
    len[fy] += len[fx];
15
}
16

17
void solve() {
18
    int n;cin >> n;
19
    for (int i = 1;i <= n;i++) {
20
        len[i] = 1;fa[i] = i;
21
    }
22
    for (int i = 1;i <= n;i++) {
23
        cin >> p[i];
24
        merge(i, p[i]);
25
    }
26
    map<int, int>mp;
27
    for (int i = 1;i <= n;i++) {
28
        int fx = findfa(i);
29
        if (mp.count(fx))continue;
30
        mp[fx] = len[fx];
31
    }
32
    int ans = 0, cnt2 = 0;
33
    for (auto [i, s] : mp) {
34
        if (s == 1)continue;
35
        else if (s == 3 || s == 4)ans++;
36
        else if (s > 4) {
37
            int t = s / 3;
38
            ans += t;
39
            if (s % 3 == 2) {
40
                cnt2++;
41
            }
42
        }
43
        else cnt2++;
44
    }
45
    ans += (cnt2 + 1) / 2;
46
    cout << ans << "\n";
47
}

F-Good Tree

题意

一棵树，树上的边权都是 $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
void solve() {
2
    ll x;cin >> x;
3
    ll k = sqrtl(x); // 注意开方long long
4
    if (k * k == x) {
5
        cout << 2 * k + 1 << "\n";
6
    }
7
    else if (k * (k + 1) < x) {
8
        cout << 2 * k + 3 << "\n";
9
    }
10
    else if ((x - k * k) % 2ll != k % 2ll) {
11
        cout << 2 * k + 3 << "\n";
12
    }
13
    else {
14
        cout << 2 * k + 2 << "\n";
15
    }
16
}

G-Horse Drinks Water

题意

将军饮马问题。在平面坐标轴中，只有 $x\text{、} y$ 轴的飞负半轴是水源，给出马儿的坐标和营地的坐标，求最短距离。

数据范围

$1\leq t\leq 10^5$
$0\leq x_G,y_G,x_T,u_T\leq 10^9$

思路

将坐标按坐标轴对称，求距离。

代码

1
ld dist(ld r, ld c) {
2
    return sqrt(r * r + c * c);
3
}
4

5
void solve() {
6
    ll x1, y1, x2, y2;
7
    cin >> x1 >> y1 >> x2 >> y2;
8
    ld ans1 = dist(1.0 * abs(y1 - y2), 1.0 * (abs(x1) + abs(x2)));
9
    ld ans2 = dist(1.0 * (abs(y1) + abs(y2)), 1.0 * abs(x1 - x2));
10
    ld ans = min(ans1, ans2);
11
    printf("%.12lf\n", ans);
12
}

H-Yet Another Origami Problem

题意

可以选择任意坐标 $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\text{、} c$ 之间），若此时 $x\neq 0$ ，则 $y$ 也可以通过一样的方法收束到小于 $x$ 的某个长度。故获得的最小的范围应该是 $x\text{、}y$ 的 $gcd$ 。

同样的思想可以拓展到多个数的时候。

代码

1
ll a[maxn];
2
void solve() {
3
    int n;cin >> n;
4
    for (int i = 0;i < n;i++) { cin >> a[i]; }
5
    sort(a, a + n);
6
    if (n == 1) {
7
        cout << 0 << "\n";
8
        return;
9
    }
10
    if (n == 2) {
11
        cout << a[1] - a[0] << "\n";
12
        return;
13
    }
14
    ll ans = a[1] - a[0];
15
    for (int i = 2;i < n;i++) {
16
        ans = gcd(ans, a[i] - a[i - 1]);
17
    }
18
    cout << ans << "\n";
19
}

I-Friends

题意

$n$ 个人从左到右排成一排，编号从 $1$ 到 $n-1$ ，这 $n$ 个人之间有 $m$ 对好朋友，求有多少个区间 $[l,r]$ 中每两对都是好朋友。

数据范围

$1\leq n,m \leq 10^6$

思路

假设已有一个区间 $[l,r]$ 符合要求，且 $r$ 是以 $l$ 为左端点的时候最远的符合要求的右端点。那么显然有：

当加入 $r+1$ 时， $r+1$ 号与 $[l,r]$ 中的至少一个人不是好友关系。同时，区间 $[l+1,r]$ 是一个友好区间，于是在移动左端点时，右端点只需要从上一个左端点的最远右端点开始检查即可。

代码

1
void solve() {
2
    int n, m;cin >> n >> m;
3
    vector<map<int, bool>>links(n + 1);
4
    for (int i = 0;i < m;i++) {
5
        int u, v;cin >> u >> v;
6
        links[u][v] = true;
7
        links[v][u] = true;
8
    }
9
    int ans = 0;
10
    int prer = 1;
11
    for (int i = 1;i <= n;i++) {
12
        int j = prer;
13
        while (j <= n) {
14
            // check
15
            bool f = true;
16
            for (int k = i;k < j;k++) {
17
                if (links[j].count(k))continue;
18
                f = false;
19
                break;
20
            }
21
            if (!f)break;
22
            j++;
23
        }
24
        ans += j - i;
25
        prer = j - 1;
26
    }
27

28
    cout << ans << "\n";
29
}