题解：CF2124D Make a Palindrome

rrr726 · 2026-11-11 09:06:54 · 题解

首先观察到一个性质，对于一个本来合法的回文串，如果你将其中不是前 k 小的数字全部删掉依然满足回文，或者反过来说，对于一个字符串来说，删掉其中的一些相同的数，对于整个合法回文串的约束肯定会减小，所以我们先把所有排名大于 k 的数字删除。

可是排名等于k的数字可能是一个不小的集合，考虑延伸上面的贪心，尽可能的多删除数字，换而言之，我们预定自己的答案回文串理论上长度应该是 k。

回过来观察回文串的性质，要么是两端向中间收缩，要么是从中间往两边扩展，考虑从两端向中间收缩。

std:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define cfalse cin.tie(0)->sync_with_stdio(0)
int n, k;
void solve(){
    vector<int>t;
    vector<int>dic;
    vector<int>b;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        dic.push_back(x);
        t.push_back(x);
    }
    sort(dic.begin(), dic.end());
    int x = dic[k - 1];
    for(int i = 0; i < n; i++){
        if(t[i] <= x) b.push_back(t[i]);
    }
    int l = 0, r = b.size() - 1, cnt = b.size();
    while(l <= r){
        while(b[l] != b[r] && b[r] == x){
            r--; cnt--;
        }
        while(b[l] != b[r] && b[l] == x){
            l++; cnt--;
        }
        if(b[l] == b[r]) l++, r--;
        else {cout << "NO" << endl; return;}
    }
    if(cnt >= k - 1) cout << "YES" << endl;
    else cout << "NO" << endl;
}
signed main(){
    cfalse;
    int T; cin >> T;
    while(T--) solve();
    return 0;
}