专栏文章

P11282 题解

llmh_qwq
P11282题解参与者 4已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@mir4nm3g
此快照首次捕获于
2025/12/04 15:41
3 个月前
此快照最后确认于
2025/12/04 15:41
3 个月前
查看原文
一些题外话：赛时 20min 把这题秒了，加上 1A 共耗时 33min。坏消息是报名太晚，痛失首杀。最后 Div1 rk7，一分钱没拿到。
题目中把操作方式写得很抽象，实际上它等价于：每次选择排列中连续的三个数，将它们删除，并在原位放上它们的最小值或者最大值。
对排列 pp 中每一个数单独处理。假设我们目前在处理位置 xx 上的数，则令数列 ai{a_i} 为：
ai={0pi<px1pi=px2pi>pxa_i=\begin{cases}0&p_i<p_x\\1&p_i=p_x\\2&p_i>p_x\end{cases}
那么显然原先的操作可以直接套用到现在的序列上，我们的目标是最后剩下的数是原序列中唯一的那个 11。此时，这个 11 只能和两个 00 或者两个 22 操作。

Part 1：x≡0(mod2)x\equiv0\pmod 2

现在考虑一个只有 00 和 22 的长度为奇数的序列，对它操作可以得到什么结果。
注意到对三个 00 进行一次操作只能变成 00，对三个 22 进行一次操作只能变成 22，但是如果三个数中同时有 00 和 22，就可以变成任意一个。
这样我们发现，只要这个序列中有 00，就一定存在一种操作方法使得这个序列变成 00。22 同理。
如果 x≡0(mod2)x\equiv 0\pmod 2，那么它两边的数列长度都为奇数。只要两边都能变成 00 或都能变成 22，那么就有解。
否则，只可能是一边全是 00，另一边全是 22。这样的话，出现对 0,1,20,1,2 进行操作就废了。然而，每次操作会减少 22 个数，而左边（不妨这样假设）00 的个数和右边 22 的个数都是奇数，因此无法在不进行 0,1,20,1,2 的操作且不把 11 搞没的前提下去掉所有的 00，因而无解。
维护前后缀最大最小值即可，时间复杂度 O(n)O(n)。

Part 2：x≡1(mod2)x\equiv 1\pmod 2

下证明：长度大于 22 且长度为偶数的由 00 和 22 组成的数列可以通过操作变成两个相等的数。
假设数列第一个数为 00，由之前对奇数长度数列性质的推导，只要后面有 00，就可以把去掉第一个数的部分变成 00。否则，后面全部都是 22，但数列长度大于 22，那么此时对去掉最后一个数的部分操作使其变成 22，就会剩下两个相同的数。
所以，如果 x≠3x\ne 3 且 x≠n−2x\ne n-2，那么它两段的序列长度要么是 00，要么 >2>2，可以变成两个相同的数然后和中间的 11 操作把它留下来。
下只考虑 x=3x=3 的情况。x=n−2x=n-2 同理。
不妨假设 n≥7n\ge 7，此时 xx 右边的序列长度 >2>2。n=3n=3 和 n=5n=5 的情况是类似的，最后会给出结论。
如果 (a1,a2,a3)=(0,0,1)(a_1,a_2,a_3)=(0,0,1) 或 (2,2,1)(2,2,1)，那么把序列后半部分变成两个相同的数，显然有解。
否则，不妨设 (a1,a2,a3)=(0,2,1)(a_1,a_2,a_3)=(0,2,1)。显然我们不能对 a1,a2,a3a_1,a_2,a_3 进行操作，所以必定有一次操作是对 2,1,22,1,2 进行，此时 a4=2a_4=2。之后我们肯定还有一次对 0,1,00,1,0 进行的操作。
也就是说，我们必须从后面凑出一个 22 和一个 00。假设 p≤n+1p\le n+1 为最小的使得 max⁡i=4pai=2\max_{i=4}^p{a_i}=2 的偶数（令 an+1=2a_{n+1}=2），那么 a4∼apa_4\sim a_p 的子序列长度为奇数，显然可以凑出一个 22。（这里 p=n+1p=n+1 是个 corner case，不过不要紧，后面会把这种情况排除掉）
同时，由于 pp 是最小的满足条件的偶数，所以把 a4∼ap−2a_4\sim a_{p-2} 合并凑不出 22，把 a4∼ap+2a_4\sim a_{p+2} 合并不优。现在，我们还需要在 ap+1∼ana_{p+1}\sim a_n 中凑出一个 00。这个判断是简单的。
由此，我们解决了 n≥7n\ge 7 的情况。
当 n=3n=3 或 n=5n=5，x=3x=3 时，有如下结论：
n=3n=3 时，有解当且仅当 (a1,a2,a3)=(0,0,1)(a_1,a_2,a_3)=(0,0,1) 或 (2,2,1)(2,2,1)。
n=5n=5 时，有解当且仅当 (a1=a2∧a4=a5)∨(a1=a5∧a2=a4)(a_1=a_2\wedge a_4=a_5)\vee (a_1=a_5\wedge a_2=a_4)。
证明显然。
由此，我们在 O(n)O(n) 的时间复杂度内解决了问题。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1000007;
ll T,n,p[N],premn[N],premx[N],sufmn[N],sufmx[N],ans[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for (int i=1;i<=n;++i){cin>>p[i];ans[i]=1;}
		premn[0]=sufmn[n+1]=1e9;premx[0]=sufmx[n+1]=0;
		for (int i=1;i<=n;++i){
			premn[i]=min(premn[i-1],p[i]);
			premx[i]=max(premx[i-1],p[i]);
		}
		for (int i=n;i;--i){
			sufmn[i]=min(sufmn[i+1],p[i]);
			sufmx[i]=max(sufmx[i+1],p[i]);
		}
		for (int i=2;i<=n;i+=2) if ((premx[i-1]<p[i]&&p[i]<sufmn[i+1])||(sufmx[i+1]<p[i]&&p[i]<premn[i-1])) ans[p[i]]=0;
		if (p[1]<p[3]&&p[2]>p[3]){
			ans[p[3]]=0;
			ll pos=4;
			while(pos<n&&p[pos]<p[3]&&p[pos-1]<=p[3]) pos+=2;
			if (pos<n){
				for (int i=pos+1;i<=n;++i) ans[p[3]]|=(p[i]<p[3]);
			}
		}
		if (p[1]>p[3]&&p[2]<p[3]){
			ans[p[3]]=0;
			ll pos=4;
			while(pos<n&&p[pos]>p[3]&&p[pos-1]>=p[3]) pos+=2;
			if (pos<n){
				for (int i=pos+1;i<=n;++i) ans[p[3]]|=(p[i]>p[3]);
			}
		}
		if (p[n]<p[n-2]&&p[n-1]>p[n-2]){
			ans[p[n-2]]=0;
			ll pos=n-3;
			while(pos>0&&p[pos]<p[n-2]&&p[pos+1]<=p[n-2]) pos-=2;
			if (pos>0){
				for (int i=1;i<pos;++i) ans[p[n-2]]|=(p[i]<p[n-2]);
			}
		}
		if (p[n]>p[n-2]&&p[n-1]<p[n-2]){
			ans[p[n-2]]=0;
			ll pos=n-3;
			while(pos>0&&p[pos]>p[n-2]&&p[pos+1]>=p[n-2]) pos-=2;
			if (pos>0){
				for (int i=1;i<pos;++i) ans[p[n-2]]|=(p[i]>p[n-2]);
			}
		}
		for (int i=1;i<=n;++i) cout<<ans[i];cout<<'\n';
	}
	return 0;
}

评论

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

正在加载评论...