题解：AT_abc363_c [ABC363C] Avoid K Palindrome 2

· · 题解

对于求字符串的全排列，STL 库中有一个函数 next_permutation。

  1. 它的前两个参数分别是起始位置和终止位置。第三个参数是自定义的比较函数，不写自动按照字典序从小到大。

  2. 它可以求出比当前字典序大的下一个排列。

  3. 它的返回值是 bool 类型。如果有下一个排列，返回真；否则当前已经是字典序最大的排列，返回假。

所以，我们先按升序排序（字典序最小的排列），再用它求出全排列。由于数据范围很小，对于每一个排列，只需要暴力判断即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,k,ans=0;
string s;
bool check(string t){
    int len=t.size();
    //判断回文串
    bool flag=true;
    for(int i=0,j=len-1;i<=j;i++,j--){
        if(t[i]!=t[j]){
            flag=false;
            break;
        }
    }
    return flag;
}
int main(){
    cin>>n>>k>>s;
    sort(s.begin(),s.end());
    do{
        bool flag=false;
        //暴力枚举子串
        for(int i=0;i<n-k+1;i++){
            //substr在s中截取从i开始的k个字符
            if(check(s.substr(i,k))){
                flag=true;
                break;
            }
        }
        if(!flag)ans++;
    }while(next_permutation(s.begin(),s.end()));//全排列函数
    cout<<ans;
    return 0;
}