AT_abc363_c [ABC363C] Avoid K Palindrome 2 题解
donnieguo
·
·
题解
题意简述
给你一个长度为 N 的字符串 S 和一个正整数 K，要你求出满足以下要求的字符串有几个。
要求：
-
是 S 的全排列。
-
子串中没有长度为 K 的回文字符串。
本人赛时看到这题也被绕了一会儿，又是全排列又是子串的，所以给大家解释一下样例。
样例解释
3 2
aab
字符串 aab 的全排列有 aab，aba，baa 三个，其中 aab 和 baa 的子串中都有长度为 2 的回文串 aa，所以满足要求的只有 aba 一个字符串，答案为 1。
数据范围
~~别问我为什么不去交翻译，问就是想先写题解~~
## 思路
其实思路也挺简单的，就是先求出 $S$ 的每一个全排列，然后判断一下这个排列的所有长度为 $K$ 的子串中有没有回文串，如果没有就让答案加 $1$ 即可。
这里介绍一个 $\text{STL}$ 中的函数：`next_permutation`，它可以求出数组或字符串的全排列。
### `next_permutation` 使用方法 & 介绍
- 有三个参数，第一个和第二个分别是数组或字符串的起始的位置和结束的位置，第三个是自定义比较函数，不写会默认按字典序大小排序。（与 `sort` 相似）
- 它会求出比**当前排列的字典序大**的下一个排列。
这里要注意：由于下一个排列要比当前排列的字典序大，所以你应该先排序，否则无法找到所有的排列。
- 它的返回值是 `bool` 类型，如果有下一个满足要求的排列返回 `true`，否则返回 `false`。
- 需要 `<algorithm>` 库（当然如果你用万能头当我没说）。
例如我要输出一个数组的全排列：
```cpp
sort(a + 1, a + n + 1);
do
{
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
cout << '\n';
} while(next_permutation(a + 1, a + n + 1));
```
### 遍历子串优化
因为我在遍历字符串的子串的时候通常都是两重循环，第一层遍历起点，第二层遍历长度，所以我赛时也是这么遍历子串的，然后吃了两发 TLE QAQ……
后来想了一下，对于 $S$ 的每一个排列来说，因为只有长度为 $K$ 的子串才需要判断是否为回文，所以不需要第二层循环枚举长度。
~~赛时也是被自己的智慧震撼到了，这还要 T 两发……~~
## AC code
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int n, k, ans;
string s;
int main() {
cin >> n >> k >> s;
sort(s.begin(), s.end()); //排序
do {
bool flag = 1;
for (int i = 0; i < n - k + 1; i++) { // 防止越界
string tt = s.substr(i, k); // 长度就是K
bool hw = 1;
for (int l = 0; l < k / 2; l++) // 判断回文只用枚举到一半
if (tt[l] != tt[k - 1 - l]) {hw = 0; break;}
if (hw) {flag = 0; break;}
}
if (flag) ans++;
} while (next_permutation(s.begin(), s.end()));
cout << ans << '\n';
return 0;
}
```
总时间复杂度为 $\Theta(N! \; \times NK)$，因为 $N$ 的范围只有 $10$，而且 $K$ 不会比 $N$ 大，$2\text{s}$ 足以通过本题。
[AC记录](https://www.luogu.com.cn/record/167881551)
跑的还是很快的，只用了 $163 \; \text{ms}$。