题解CF2047B

cly312 · 2024-12-05 21:50:29 · 题解

先思考对于一个字符串，它的排列数是多少。

对于一个每个字符都不同的字符串，很明显它的排列数是 n!。

如果现在有 k 个相同的字符，那么这 k 个字符交换位置之后对结果没有影响，这几个字符交换的方案数就是 k!。

那么对于一个字符串，它的排列数为 \frac{n!}{\prod_i^n a_i}，其中 a_i 为每个字符出现的次数。

数据范围是 1\le n\le 10，每次枚举两个 i,j 计算排列数取最小值即可。

代码：

//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define OK puts("OK")
using namespace std;
int n;
int jc(int k){
    int ans=1;
    for(int i=k;i>=1;i--) ans*=i;
    return ans;
}
int query(string s){
    int ans=jc(n);
    vector<int> cnt(26,0);
    for(auto c:s) cnt[c-'a']++;
    for(int i=0;i<26;i++) ans/=jc(cnt[i]);
    return ans;
}
void solve(){
    string s;
    cin>>n>>s;
    string ans;
    int now=INT_MAX;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            string tmp=s;
            tmp[i]=tmp[j];
            int _=query(tmp);
            if(_<now) ans=tmp,now=_;
        }
    }
    cout<<ans<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}