【0】做题心得 - 2025 NOIP #68 - T1【链表】

ExFish · 2025-11-25 15:06:07 · 题解

哦赛时就差一点过了，使用 n^3 冲过部分 n=1000 的点，脏脏 70 分。（预计 40）然后我们考虑转化问题。你会发现无论树的结构怎么变叶子的相对顺序都不会变，所以考虑一个转化为线段合并问题，到这里就可以直接 n^3 区间 DP。设 f_{i,j} 为合并这个区间后合并的数值。最后显然需要剩余一个 0。然后考虑一个合并的本质，也就是我们类似并查集一样指定一个 fa。因为转移的原因所以最后线段上的一定是一段区间的最小值。所以删去最大值只要是合法的就可以直接删，因为合法时可以直接被并到左右两侧。然后一个链表可以简单通过。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=3e3+10;
int n,a[N],nxt[N],prv[N];
pair<int,int>c[N];
int main(){
    freopen("latency.in","r",stdin);
    freopen("latency.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i], prv[i]=i-1, nxt[i]=i+1,
            c[i].first=a[i],    c[i].second=i;
        sort(c+1,c+n+1,greater<pair<int,int>>());
        bool fl=1;
        for(int i=1;i<=n;i++){
            int di=c[i].second;
            if((prv[di]>=1&&prv[di]<=n&&abs(a[prv[di]]-a[di])<=1)||
               (nxt[di]>=1&&nxt[di]<=n&&abs(a[nxt[di]]-a[di])<=1)){
                nxt[prv[di]]=nxt[di];
                prv[nxt[di]]=prv[di];
                nxt[di]=prv[di]=0;
            }else if(c[i].first)fl=0;
        }
        cout<<(fl?"YES\n":"NO\n");
    }
    return 0;
}