题解：CF2124D Make a Palindrome

· · 题解

首先，由于只需要满足区间长度 len>=k 就可以一直把排名超过 k 的数字删除，而删除他们对答案不会有影响，因为即使最终他们参与回文，同时删除也不会改变回文性质。

但是注意：排名刚好为 k 的数均需保留。
因为其中只有一部分可以被删除，而我们不能直接知道是哪些。

接着我们考虑删除哪些位置。一个经典的做法是回文串从两头向中间匹配。我们碰到匹配成功的直接跳过，缩减 l,r 的范围。然后失败的时候，分成两种情况：

  1. 有一个指针处的数的排名为 k，那么直接删除它，并记录删除次数。
  2. 若两个指针处的数排名均不为 k，那么直接结束，无解。

最后判断一下删除次数是否合法即可。

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back
#define p_b push_back
#define fir first
#define sec second
#define gc getchar
#define ios ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
const int N=2e5+5,mod=1e9+7,inf=1e9;
int n,k,a[N],b[N];
int c[N];
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    int m=0;
    for(int i=1;i<=n;i++){
        int rk=lower_bound(b+1,b+n+1,a[i])-b;
        if(rk<=k)c[++m]=a[i];
    }
    int l=1,r=m,tt=m-k+1;
    while(1){
        //cout<<l<<' '<<r<<'\n';
        if(l>=r)break;
        if(c[l]!=c[r]){
            if(c[l]==b[k])l++,tt--;
            else if(c[r]==b[k])r--,tt--;
            else{cout<<"No\n";return;}
        }
        else l++,r--;
        if(tt<0){cout<<"No\n";return;}
    }cout<<"Yes\n";
}
signed main(){
    ios;int T;cin>>T;
    while(T--)solve();
}