题解：AT_abc363_c [ABC363C] Avoid K Palindrome 2

Qfaiser · 2024-07-22 13:15:31 · 题解

题意

求将给定的字符串 s 的字符置换后得到的字符串中，不含有长度为 k 的回文子串的字符串的个数。

思路

数据范围太小了，直接暴力。每次生成全排列，枚举每个长度为 k 的子串，判断是否回文。

实现

这里为方便输入字符串时从 1 计数，为方便全排列，先排序，详情见代码。

code

#include <bits/stdc++.h>
using namespace std;
int n, k, cnt;
char s[15];
int main () {
    cin >> n >> k;
    for (int i=1; i<=n; i++)
        cin >> s[i];
    sort(s+1, s+n+1);
    do {
        bool ok=1;
        for (int i=1; i<=n-k+1; i++) {
            int len=i+k-1;
            bool f=1;
            for (int l=i, r=len; l<=len&&r>=0; l++, r--)
                if (s[l]!=s[r]) {
                    f=0;
                    break;
                }
            if (f) {
                ok=0;
                break;
            }
        }
        cnt+=ok; 
    } while (next_permutation(s+1, s+n+1));
    cout << cnt;
    return 0;
}