题解：P16871 [GKS 2022 #A] Palindrome Free Strings

Beacon_wolf · 2026-06-11 13:14:38 · 题解

如果一个字符串包含一个长度大于等于 5 的回文子串，那么它必然包含一个长度为 5 或长度为 6 的回文子串。

证明：如果有长度为 L > 6 的回文子串，我们总能通过不断剥离两端的字符，最终得到一个长度为 5 或 6的回文子串。

因此，我们只需要在生成字符串的过程中，确保没有任何一个连续的 5 个字符或 6 个字符构成回文即可。

由于 N \le 5 \times 10^4，字符集大小只有 2，且我们只需要关心当前位置前 5 个字符的状态，显然可以考虑状压 dp。

设 dp_{i,mask} 表示当前处理到第 i 个字符，且最后 5 个字符的二进制状态为 mask（0 \le mask < 32）时，该方案是否合法。

对于每个状态，我们检查一下是否存在长度为 5 或 6 的回文即可。

注意特判 n 小于 5，答案一定是可以的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1000010;
const int mod = 1e9 + 7;
bool dp[MAXN][32];
bool check(int mask,int n){
    for(int i = 0;i < n / 2;i++){
        if(((mask >> i) & 1) != ((mask >> n - i - 1) & 1)) return false; 
    }
    return true;
}
void solve(int id){
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n < 5){
        cout << "Case #" << id << ": POSSIBLE\n";
        return;
    }
    for(int i = 0;i < n;i++) for(int j = 0;j < 32;j++) dp[i][j] = false;
    if(s[0] == '0' || s[0] == '?') dp[0][0] = true;
    if(s[0] == '1' || s[0] == '?') dp[0][1] = true;
    for(int i = 1;i < n;i++){
        for(int j = 0;j < 32;j++){
            if(!dp[i - 1][j]) continue;
            for(int c = 0;c < 2;c++){
                if(s[i] == '0' && c == 1) continue;
                if(s[i] == '1' && c == 0) continue;
                int s6 = ((j << 1) | c) & 0b111111;
                int ns = s6 & 0b11111;
                if(i >= 4 && check(ns,5)) continue;
                if(i >= 5 && check(s6,6)) continue;
                dp[i][ns] = true;
            }
        }
    }
    bool ok = false;
    for(int i = 0;i < 32;i++){
        if(dp[n - 1][i]){
            ok = true;
            break;
        }
    }
    cout << "Case #" << id << ": ";
    if(ok) cout << "POSSIBLE\n";
    else cout << "IMPOSSIBLE\n";
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    int cnt = 0;
    while(t--){
        solve(++cnt);
    } 
    return 0;
}