C - Swappable

题意： 给n个数，问有多少对数,1<=i<j<=N, A i A_i Ai​!= A j A_j Aj​，问有多少对数吗？
思路：
思路1： 先排序，枚举每个 a i a_i ai​，然后看有多少个大于 a i a_i ai​,大于 a i a_i ai​的就是 a j a_j aj​，不用找小于 a i a_i ai​的，因为小于 a i a_i ai​枚举的时候，匹配过 a i a_i ai​了，不用重复寻找。
思路2： 可以用所有的数对，减去满足 A i = = A j A_i==A_j Ai​==Aj​的数量，就是满足的数量。总数就是n*(n-1)/2,再用桶记录其中的数量就行。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
ll a[N];
int main() {
    ll n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    sort(a, a + n);
    ll res = 0;
    for (int i = 0; i < n; i++) {
        res += (n - (upper_bound(a + i + 1, a + n, a[i]) - a));
    }
    cout << res << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
#define ll long long
map<int, int> m;

int n;

int main() {
    scanf("%d", &n);
    ll ans = (ll)(n - 1) * n / 2;
    for (int i = 1; i <= n; i++) {
        int a;
        scanf("%d", &a);
        ans -= (ll)m[a];
        ++m[a];
    }
    printf("%lld\n", ans);
    return 0;
}

D - KAIBUNsyo

题意： 给n个数，有一种操作，就是令数组中所有等于 x x x的数全部转变为 y y y,问最少操作几次，才能形成回文数组。
思路： 把 x x x变成 y y y，可以想成在 x x x和 y y y之间连一条边，代表在一个连通块中，在一个连通块中，代表连通块的数最后都要变成其中一个数（可以直接都变成祖先节点），而要将一个连通块中的数都变成一个数，那就要看连通块中有几个结点，转变次数就是除了祖先节点以为点的数量，也就是看有几个 f a [ i ] ! = i fa[i]!=i fa[i]!=i, f a [ i ] = = i fa[i]==i fa[i]==i都是祖先节点，这样就
每次就是对称的两个点，是不是同一个数字，是否对称，不对称的话，就要放一个连通块中，表示要操作。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int fa[N];
int a[N];

int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void Union(int a, int b) {
    if (find(a) != find(b)) {
        fa[find(a)] = find(b);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= N; i++) {
        fa[i] = i;
    }
    for (int l = 1, r = n; l < r; l++, r--) {
        Union(a[l], a[r]);
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += (fa[i] != i);
    }
    printf("%d\n", ans);
    return 0;
}

To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激