题解 CF2047B

题意：

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

思路：

没有想到其它题解那样特别精妙的方法（主要是不会证），发现

n

极小，于是愉快地打一个暴力。

回顾一下多重集合的排列公式，设我们有

n

个元素，第

i

种元素出现了

k_i

次，排列数如下：

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

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

复杂度

O(n^3+n^2w)

，

w

为桶大小。

程序如下：

CPP

#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

相关推荐

评论

题解 CF2047B