题解：P14906 [NHSPC 2024] 数字丛集

Sweet_Corn · 2026-01-19 18:04:29 · 题解

题目传送门 ::::info[题意]{open} 给定 n 个互不相同的数字，定义两个数字能否通过交换两个数位使它们变的相同叫做互通。你需要求出合并所有能互通的数字后，群组数量和最大群组大小。 :::: ::::success[思路]{open} 仔细观察文中的标签将两个群合并，不难联想到并查集。

Q：由于数据范围很小，可以枚举数字并合并，那如何求出 P(x,y) 呢？

A：首先，我们先将长度小的数补充前导 0。然后发现，当有且仅有一个满足 x_i \ne y_i, x_j\ne y_j, x_i = y_j, x_j = y_i 的数对 (i,j)，P(i,j) 才成立。

代码很好写，时间复杂度为 O(n^2len)。 :::: ::::success[代码]

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int a[1000005], c[1000005], v[10][10], t[10] = {0, 1, 2, 3, 4, 5, 6};
string s;
map<char, int>mp;
signed main(){
    cin >> s;
    int n = s.size(), sum = 0, ans = 1e18; //一定要开大！我就是在这被坑到只剩26分的。
    for(int i = 0; i < n; i++){
        if(mp.count(s[i]) == 0){
            mp[s[i]] = sum;
            sum++;
        }
        a[i] = mp[s[i]];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < sum; j++)v[j][a[i]] += c[j];
        c[a[i]]++;
    }
    do{
        int cnt = 0;
        for(int i = 0; i < sum; i++){
            for(int j = 0; j < sum; j++){
                if(t[i] > t[j])cnt += v[i][j];
            }
        }
        ans = min(ans, cnt);
    }while(next_permutation(t, t + sum));
    cout << ans;
    return 0;
}

::::