题解 CF2047B

· · 题解

题意：

一个非常短的小写字母串，可以进行一次下标间的赋值操作，问如何得到最少的不同排列个数。

思路：

没有想到其它题解那样特别精妙的方法（主要是不会证），发现 n 极小，于是愉快地打一个暴力。

回顾一下多重集合的排列公式，设我们有 n 个元素，第 i 种元素出现了 k_i 次，排列数如下：

\dfrac{n!}{\prod k_i!}

直接枚举所有不同的赋值方法，开桶存字符串不同字符的个数，用上述公式计算，找到最小值即可。代码很丑且十分的暴力，但不用证明结论。

复杂度 O(n^3+n^2w)，w 为桶大小。

程序如下：

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int T,a[30];
char str[15];
int factorial(int x){
    int ret=1;
    for(int i=2;i<=x;i++)ret*=i;
    return ret;
}
int main(){
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d%s",&n,str+1);
        char ans[15];
        int mn=2e9;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                char tmp[15];
                for(int k=1;k<=n;k++)tmp[k]=str[k];
                tmp[j]=tmp[i];
                memset(a,0,sizeof(a));
                for(int k=1;k<=n;k++)a[tmp[k]-'a']++;
                int cur=factorial(n);
                for(int k=0;k<26;k++)cur/=factorial(a[k]);
                if(cur<mn){
                    mn=cur;
                    for(int k=1;k<=n;k++)ans[k]=tmp[k];
                }
            }
        }
        for(int i=1;i<=n;i++)printf("%c",ans[i]);
        puts("");
    }
    return 0;
}

THE END