自动搬运

查看原文

来自洛谷，原作者为

	Wy_x ༼ つ ◕_◕ ༽つ 或者，赢下所有！

搬运于2025-08-24 22:40:46，当前版本为作者最后更新于2022-10-24 19:41:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

更好的阅读体验？

如果你看出来方法了，那这道题就是一道裸的全排序题。

思路：

• 因为数据范围是 $1 \leq n \leq 10$，可以放心使用时间复杂度为 $O(n!)$ 的全排列函数。题目由小到大编号，应选择 next_permutation。

• ans 应该从 $0$ 开始计数。

• 每进行一次全排列后就判断全排列的结果是否和给出的字符串 $S$ 相同，两种情况：

1. 如果相同，则退出循环，输出现在 ans 的值。
2. 否则，ans 加一，同时继续全排列当前结果，直到条件 $1$ 成立。

• 关于 next_permutation：不懂请移步这里，根据需要自学。

代码：

#include<bits/stdc++.h>
using namespace std;
string a;
char c[100];
int ans=0;
// 1 ≤ n ≤ 10
//放心使用时间复杂度 O(n!) 的全排列函数
//不会超时 
int main()
{
	cin>>a;
	int l=a.size();
	for(int i=0;i<l;i++)  c[i]='a'+i;
	//因为 a 的长度 == 字符种类，进行初始化 
	//全排列我习惯字符数组，string 的我不会 
	while(true)
	{
		bool flag=1;
		for(int i=0;i<l;i++)
		{
			//判断两个字符串是否相等
			if(a[i]!=c[i])//不相等
			{
				flag=0;//标记
				break;//退出循环
			}
		}
		if(flag) break;
		//如果没有被标记过,就退出循环输出答案
		ans++;
		//注意 ans 要从 0 开始计数，
		//所以加法操作要在 break 后
		next_permutation(c,c+l);
		//求下一个全排列
	}
	cout<<ans;
	//输出编号
	return 0;
}