游游的字符重排

题意

游游定义一个字符串是“好串”，当且仅当该字符串相邻的字符不相等。例如”arcaea”是好串，而”food”不是好串。

游游拿到了一个字符串，她可以将该字符串的各个字符顺序随意打乱。她想知道一共可以生产多少种不同的好串？

输入：一个仅包含小写字母的字符串，长度不超过10。

输出：好串的数量。

题解

显然dfs可以做，但是枚举全排列更好写。比赛时就是因为不熟悉next_permutation()函数的返回值而出错改用了dfs。

暴力枚举原串的全排列，用do{}while(next_permutation(s.begin(),s.end()));枚举全排列暴力判断。

next_permutation()函数功能是输出所有比当前排列大的排列，顺序是从小到大。

返回值:若新排列按字典序大于旧者则为 true 。若抵达最后重排并重置范围为首个排列则为 false 。

prev_permutation()函数功能是输出所有比当前排列小的排列，顺序是从大到小。

所以枚举全排列应该先sort(s.begin(),s.end());

代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 0;

void solve() {
	string s;
	cin >> s;
	int n = s.size();
	int ans = 0;
	sort(s.begin(), s.end());
	do {
		bool f = 1;
		for(int i = 1; i < n; i++) {
			if(s[i] == s[i - 1]){
				 f = 0;
				 break;
			}
		}
		ans += f;
	}while(next_permutation(s.begin(),s.end()));
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	if (multi) cin >> T;
	while (T--) {
		solve();
	}
	
	return 0;
}