专栏文章

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

EExFish
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0y8lt
此快照首次捕获于
2025/12/01 18:46
3 个月前
此快照最后确认于
2025/12/01 18:46
3 个月前
查看原文
哦赛时就差一点过了，使用 n3n^3 冲过部分 n=1000n=1000 的点，脏脏 7070 分。（预计 4040）然后我们考虑转化问题。你会发现无论树的结构怎么变叶子的相对顺序都不会变，所以考虑一个转化为线段合并问题，到这里就可以直接 n3n^3 区间 DP。设 fi,jf_{i,j} 为合并这个区间后合并的数值。最后显然需要剩余一个 00。然后考虑一个合并的本质，也就是我们类似并查集一样指定一个 fafa。因为转移的原因所以最后线段上的一定是一段区间的最小值。所以删去最大值只要是合法的就可以直接删，因为合法时可以直接被并到左右两侧。然后一个链表可以简单通过。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...