G.Horse Drinks Water（模拟，数学）

时间复杂度：$O(t)$

题意

    将军饮马问题：马处于点$(x_G,y_G)$，将军处于点$(x_T,y_T)$，河水位于x轴正半轴与y轴的正半轴上，求将军饮马的最短距离.

数据范围

  • $ 0$ $\le x_G,y_G,x_T,y_T \le 10^9$

思路

    签到题，由数据范围知，将军和马一定同处于第一象限，所以将任一点的坐标转换到第二象限，求 直线两点的距离 即可。注意浮点数输入输出。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--){
        int xg, yg, xt, yt;
        cin >> xg >> yg >> xt >> yt;
        xg *= -1;
        //式子一定要加long long,不然局部int就炸了
        double res1 = sqrt(1LL * (xg - xt) * (xg - xt) + 1LL * (yg - yt) * (yg - yt));
        xg *= -1, yg *= -1;
        double res2 = sqrt(1LL * (xg - xt) * (xg - xt) + 1LL * (yg - yt) * (yg - yt));
        double ans = min(res1, res2);
        cout << fixed << setprecision(9) << ans << endl;
    }
    return 0;
}

I.Friends(双指针+set存图)

题意

    给定一张$n$个点$m$条边的图，定义区间$[l,r]$为点$l$到点$r$间每个点之间都两两有边,请问满足该区间条件的总数量是多少？

数据范围

  • $1 \le n,m \le 10^6$
  • $1 \le l \le r \le n$

思路

    题意可以转化为求区间各个节点是否构成一张完全图，对于区间$[l,r]$而言，当$l=r$时，只有一个孤立的点，显然满足条件；当$l < r$时，不难发现，当$[l,r-1]$满足条件时，只需满足节点$r$与节点$i \in [l,r-1]$均有边，也就是该点连通在区间中的边的个数是$r-l$，就能保证区间$[l,r]$是完全图。例如区间$[3,6]$，已知区间$[3,5]$互为两两有边，只需保证点$6$与$3,4,5$均有边即可.
    对区间的数量枚举，我们只需要找到每一个左节点对应的 右边最大满足下标 即可，不难发现该右端点一定是单调的，所以使用 双指针 去维护区间信息，统计各个枚举到的左端点对答案的贡献.
    对于存图，由于判断完全图的方法是统计区间中 小于R的边的个数 ,所以每次输入$u,v$时(题设已保证$u < v$)只需在$v$点保存$u$点的信息即可，自此，每次判断，也只要取$v$点的邻接表节点。同时各节点不能重复，可以使用set容器进行存图。
    关于复杂度，因为判断只会在右指针进行,只遍历一次就会取出所有的连通点，也就是恰好会取出所有边，那么复杂度就是严格的$m$,因$m<10^6$,所以整体复杂度是合法的.

Code:

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, m;
    cin >> n >> m;
    set<int> st[n + 1];
    for (int i = 1; i <= m;i++){
        int u, v;
        cin >> u >> v;
        st[v].insert(u);
    }
    auto check = [&](int L, int R) -> bool //判断区间[L,R]是否是完全图
    {
        if(L==R)
            return 1;
        int cnt = 0;
        for(auto it:st[R])
            if(it>=L)
                cnt++;
        return cnt == R - L;
    };
    i64 ans = 0;
    for (int i = 1, j = 1; i <= n;i++){
        while (j <= n && check(i, j))
            j++;
        //cout << i << ' ' << j << endl;
        ans += j - i; //贡献区间数量为右端点-左端点
    }
    cout << ans << endl;
    return 0;
}

C.Sort4(思维)

时间复杂度：$O(n)$

题意

    给定一个长度为$n$的排列,在一次操作中，最多可以 交换(调整)任意四个元素 的位置，请问最少经过多少次操作可以将整个排列升序？

数据范围

  • $1 \le n \le 10^6$
  • $\sum n \le 10^6$

思路

    根据排列的性质，如果是升序排列，那么每一个数一定满足$p_i=i$,我们从下标到值的映射角度看，整个排列实际上是由多种$i \rightarrow p_i$环组成的，且这些环一定相互独立。
    设环的长度为$len$，易证：

  • 顾名思义，$len=1$的环就是$p_i=i$本身，这些点显然无需操作
  • 当$len=2$，只需两两交换位置即可，一次操作能处理 最多两个环
  • 当$len=3 \:or \:4$时，一次操作只能 处理一个环
  • 当$len \ge 4$时，手玩数据后不难发现，每次最多能够消除三个点，也就是$len=len-3$；如$p_1=3,p_3=4,p_4=6,p_6=7,p_7=1$,也就是构成了$1 \rightarrow 3 \rightarrow 4 \rightarrow 6 \rightarrow 7$的环，此时我们将前四个元素调整到合适位置，那么$p_3=3,p_4=4,p_6=6$且$p_1=7,p_7=1$,只剩下$1 \rightarrow 7$的$len=2$的环，所以每次应当最多使得环长减去3

    使用一次DFS求出所有环的长度$len$，设$len=2$的环为$len2$,当遇到$len=2$时$len2$的计数值加一；设$len=3 \:or \:4$的环为$len3$，由于$len=3 \: or \:4$的环都需要耗费一次操作，遇到时同样将$len3$的计数值加一；当$len \ge 4$时，

    综上，答案为$\lceil {\dfrac{len2}{2}} \rceil +len3$.

Code:

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        vector<bool> vis(n + 1);
        for (int i = 1; i <= n;i++)
            cin >> a[i];
        int cnt, ans = 0;
        auto dfs = [&](auto dfs, int x) -> void
        {
            vis[x] = 1, cnt++;
            if(!vis[a[x]])
                dfs(dfs, a[x]);
        };
        int len2 = 0, len3 = 0;
        for (int i = 1; i <= n;i++){
            cnt = 0; //环的长度
            if (vis[i] || a[i] == i)
                continue;
            dfs(dfs, i);
            //cout << i << ' ' << cnt << endl;
            if(cnt==2)
                len2++;
            else if(cnt==3)
                len3++;
            else if(cnt%3==0||cnt%3==1)
                len3 += cnt / 3;
            else
                len2++, len3 += (cnt - 2) / 3;
        }
        ans = (len2 + 1) / 2 + len3;
        cout << ans << endl;
    }
    return 0;
}

H.Yet Another Origami Problem(数学)

题意

    给定一个长度为$n$的数组$a$，每次选择一个索引$p$，并执行以下任意次数(可为零)的操作：
        i.对于所有$i$，如$a_i \le a_p$，让$a_i \leftarrow a_i+2(a_p-a_i)$
        ii.对于所有$i$，如$a_i \ge a_p$，让$a_i \leftarrow a_i-2(a_i-a_p)$
    请问经过任意次操作后，最小化数组的最大和最小元素的差值，该差值的最小值是多少？

数据范围

  • $1 \le n \le 10^5$
  • $0 \le a_i \le 10^{16}$
  • $\sum n \le 5 \times 10^5$

思路

    结论$gcd(a_2-a_1,a_3-a_2,…diff_n)diff_i=a_i-a_{i-1}$秒了.

Code:

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<i64> a(n + 1), b(n + 1);
        for (int i = 1; i <= n;i++)
            cin >> a[i];
        if (n == 1){ //其实可以不特判n=1
            cout << "0" << endl;
            continue;
        }
        i64 g = 0;
        for (int i = 2; i <= n;i++){
            b[i] = a[i] - a[i - 1];
            g = __gcd(g, b[i]);
        }
        cout << g << endl;
    }
    return 0;
}

A.LCT(带权并查集)

前置知识：带权并查集

题意

    给定一棵有根的树，树上有$n$个节点和$n-1$条边。接下来$n-1$行，有三个整数$a_i$,$b_i$和$c_i$，表示节点$a_i$是节点$b_i$的父节点，并且进行一次询问，$c_i$表示在由当前$i$条边构成的森林中，从节点$c_i$开始的最长简单路径的长度。保证不存在$j$使得$1 \le j \le i$ 和 $b_j=c_i$，即$c_i$是森林中一棵树的根。

数据结构

  • $2 \le n \le 10^6$
  • $1 \le a_i,b_i,c_i \le n,a_i \ne b_i$
  • $\sum n \le 10^6$

思路

    由题意知，每次合并的时候一定是将一棵树的根合并到另一棵树的结点上的，并询问某棵树（不一定是当前合并后）的最大深度.
    很明显的思路是设$h[i]$为节点$i$到当前这棵树的根节点的距离，当两棵树合并时(假定树$b$合并到树$a$的一节点)只需将树$b$的所有深度加上树$a$当前结点的深度加一；用以维护$h[i]$在当前树上的深度以及合并的操作，很明显的做法就是带权并查集！对于合并，对树$b$进行集体增加深度的操作，只需并查集find操作的时候，同时递归地加上父节点深度即可.
    由于求的答案是根节点的最大路径长度，我们设$ans[i]$为根节点的最大深度，当每次节点$a_i$和$b_i$合并时，不难想到转移方程$ans[fa[a_i]]=Max(ans[fa[a_i]],h[a_i]+ans[b_i]+1)$.

Code:

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        vector<int> h(n + 1); // h[i]表示节点i距离所在树根的距离
        vector<int> ans(n + 1); // ans[i]表示根节点i包含的最大深度
        vector<int> fa(n + 1);
        auto find = [&](auto find, int x) -> int
        {
            if (x == fa[x])
                return x;
            int f = find(find, fa[x]);
            h[x] += h[fa[x]];
            return fa[x] = f;
        };
        iota(fa.begin(), fa.end(), 0); 
        for (int i = 1; i < n; i++){
            int u, v, root;
            cin >> u >> v >> root; // u是v的父亲节点
            int fu = find(find, u), fv = find(find, v);
            h[v] = h[u] + 1; //必须率先对"子树"根节点赋值
            ans[fu] = max(ans[fu], h[u] + ans[v] + 1);
            fa[fv] = fu;
            cout << ans[root] << ' ';
        }
        cout << endl;
    }
    return 0;
}