「GFOI Round 2」Colors

0
15011418730 LV 7 @ 2025-8-24 23:06:04
自动搬运

查看原文

来自洛谷，原作者为

缪凌锴_Mathew
希↑望→计↓划↑可→以↑成↓功↓ | 离错真机

搬运于2025-08-24 23:06:04，当前版本为作者最后更新于2024-11-17 13:33:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

场上胡了一堆结论过了，证明一下这些结论。

下面我们只考虑 $n>5$ 的情况， $n\le 5$ corner case 太多了直接跑暴力。

接下来认为删除后球会自动往前补位（即只考虑红球，蓝球不重要）。

这样一次操作必定为操作 $i-1,i,i+1$ 这三个位置。

发现删除 $i,i+1$ 和删除三个位置中任意两个没有区别，于是操作是对称的。

结论 $1$ ： $5\le i\le n-4$ ， $i$ 为奇数，最后一定能剩下权值 $p_i$ 。
考虑 $p_{i-1}>p_i$ 的情况， $p_{i-1}<p_i$ 是对称的。

$\exists j<i-1,p_j>p_i$ ，那么不断操作 $1,2,3$ 这三个位置，选择 $p'_1\gets\max(p_1,p_2,p_3)$ 。

操作直到球 $i$ 到达 $3$ 的位置，也就是把 $1\sim i-2$ 的球合成一个最大值。

因为 $\exists j<i-1,p_j>p_i$ ，合出来的 $p'_1>p'_3=p_i$ ，又 $p'_2=p_{i-1}>p'_3=p_i$ ，此时操作 $1,2,3$ 这三个球，选择 $p'_1\gets\min(p_1,p_2,p_3)$ ，这样 $p'_1=p_i$ 。

$\forall j<i-1,p_j<p_i$ ，操作 $i-3,i-2,i-1$ ，选择 $p'_{i-3}\gets \min(p_{i-3},p_{i-2},p_{i-1})$ 。

这样去掉了 $p_{i-1}$ ， $p_i$ 是前缀最大，直接不断选择 $\max$ 操作即可把 $i$ 移动至 $1$ 。

即不断操作 $1,2,3$ ，选择 $p'_1\gets\max(p_1,p_2,p_3)$ 。

以上证明了可以删掉 $1\sim i-1$ ，对称，同理可以删掉 $i+1\sim n$ 。
结论 $2$ ： $1\le i\le n$ ， $i$ 为偶数，最后不能剩下权值 $p_i$ 当且仅当 $p_i$ 两侧权值范围无交。

权值范围无交意思是 $\max\limits_{j<i}p_j<p_i<\min\limits_{j>i}p_j$ 或者 $\min\limits_{j<i}p_j>p_i>\max\limits_{j>i}p_j$ 。

考虑 $p_{i+1}>p_i$ 的情况， $p_{i+1}<p_i$ 是对称的。

若 $\exists j<i-1,p_j>p_i$ ，那么不断操作 $1,2,3$ 这三个位置，选择 $p'_1\gets\max(p_1,p_2,p_3)$ 。

操作直到球 $i$ 到达 $2$ 的位置，也就是把 $1\sim i-2$ 的球合成一个最大值。

因为 $\exists j<i-1,p_j>p_i$ ，合出来的 $p'_1>p'_2=p_i$ ，又 $p'_3=p_{i+1}>p'_2=p_i$ ，此时操作 $1,2,3$ 这三个球，选择 $p'_1\gets\min(p_1,p_2,p_3)$ ，这样 $p'_1=p_i$ 。

又根据结论 $1$ ，可以删掉 $i+2\sim n$ ，这样最终剩下 $p_i$ 。

对称地，还有可能 $p_{i-1}>p_i$ ， $\exists j>i+1,p_j>p_i$ 。

剩下的情况就是 $\max\limits_{j<i}p_j<p_i<\min\limits_{j>i}p_j$ 或者 $\min\limits_{j<i}p_j>p_i>\max\limits_{j>i}p_j$ 。

这些情况无论怎么操作，必定会操作 $i-1,i,i+1$ ，这时 $p_i$ 是中位数，不能保留。

接下来就只用考虑 $p_3$ 和 $p_{n-2}$ 能不能保留，两种情况对称，只考虑 $p_3$ 行不行。
$p_3$ 不是 $p_1,p_2,p_3$ 的中位数，删去 $p_1,p_2$ ，根据结论 $1$ ，可以删掉 $4\sim n$ ，剩下 $p_3$ 。

$p_3$ 是 $p_1,p_2,p_3$ 的中位数，不妨设 $p_1>p_3>p_2$ 。（ $p_1<p_3<p_2$ 是对称的）

操作 $1,2,3$ 或者 $3,4,5$ 肯定无用，只有可能操作 $2,3,4$ 。

只有 $p_2<p_3,p_4<p_3$ 才能操作 $2,3,4$ ，于是需要一个 $<p_3$ 的 $p_4$ 。

找到第一个 $i>3,p_i<p_4$ 的 $i$ ，找不到无解。

$i$ 是奇数，第一个 $j>i,p_j>p_3$ 的 $i$ ，找不到无解。

取 min 合成 $p_4\sim p_i$ 为 $p'_4<p_3$ 。

取 max 合成 $p_{i+1}\sim p_n$ 为 $p'_5>p_3$ 。

$p_2>p_3<p'_4$ ，取 min 删去 $p_2$ 和 $p'_4$ 。

$p_1>p_3<p'_5$ ，取 min 删去 $p_1$ 和 $p'_5$ 。

剩下 $p_3$ ，必定有解。

$i$ 是偶数，第一个 $j+1>i,p_j>p_3$ 的 $i$ ，找不到无解。

取 min 合成 $p_4\sim p_{i+1}$ 为 $p'_4<p_3$ 。

取 max 合成 $p_{i+2}\sim p_n$ 为 $p'_5>p_3$ 。

同理，必定有解。
代码实现模拟上述过程即可，时间复杂度 $O(n)$ 。
```
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
const int N=1e6;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
int n;
int a[MAXN];
bool ans[MAXN];
int suf_max[MAXN],suf_min[MAXN];
bool f[32];
void dfs(int s){
	if(f[s]){
		return ;
	}
	f[s]=true;
	if(s==(s&-s)){
		return;
	}
	for(int i=1;i<n-1;i++)
	{
		if(~s&(1<<i)){
			continue;
		}
		int j=i-1,k=i+1;
		while(~j&&~s&(1<<j))
		{
			j--;
		}
		while(k^n&&~s&(1<<k))
		{
			k++;
		}
		if(~j&&k^n){
			int p=a[i+1]+a[j+1]+a[k+1]-max({a[i+1],a[j+1],a[k+1]})-min({a[i+1],a[j+1],a[k+1]});
			if(a[i+1]==p){
				dfs(s^(1<<i)^(1<<j));
				dfs(s^(1<<i)^(1<<k));
			}
			if(a[j+1]==p){
				dfs(s^(1<<j)^(1<<i));
				dfs(s^(1<<j)^(1<<k));
			}
			if(a[k+1]==p){
				dfs(s^(1<<k)^(1<<i));
				dfs(s^(1<<k)^(1<<j));
			}
		}
	}
}
inline void work(){
	if(a[1]<a[3]&&a[2]>a[3]){
		ans[a[3]]=false;
		for(int i=4;i<=n;i++)
		{
			if(a[i]>a[3]){
				for(int j=i+1+(i&1);j<=n;j++)
				{
					if(a[j]<a[3]){
						ans[a[3]]=true;
						break;
					}
				}
				break;
			}
		}
	}
	if(a[1]>a[3]&&a[2]<a[3]){
		ans[a[3]]=false;
		for(int i=4;i<=n;i++)
		{
			if(a[i]<a[3]){
				for(int j=i+1+(i&1);j<=n;j++)
				{
					if(a[j]>a[3]){
						ans[a[3]]=true;
						break;
					}
				}
				break;
			}
		}
	}
}
inline void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	if(n<=5){
		memset(f,false,sizeof(f));
		dfs((1<<n)-1);
		for(int i=1;i<=n;i++)
		{
			ans[a[i]]=f[1<<(i-1)];
		}
		for(int i=1;i<=n;i++)
		{
			putchar(ans[i]+'0');
		}
		putchar('\n');
		return ;
	}
	memset(ans,true,sizeof(bool)*(n+1));
	suf_max[n]=a[n];
	suf_min[n]=a[n];
	for(int i=n-1;i;i--)
	{
		suf_max[i]=max(suf_max[i+1],a[i]);
		suf_min[i]=min(suf_min[i+1],a[i]);
	}
	int pre_max=a[1],pre_min=a[1];
	for(int i=1;i<=n;i++)
	{
		if(~i&1&&(pre_max<a[i]&&a[i]<suf_min[i+1]||pre_min>a[i]&&a[i]>suf_max[i+1])){
			ans[a[i]]=false;
		}
		pre_max=max(pre_max,a[i]);
		pre_min=min(pre_min,a[i]);
	}
	work();
	reverse(a+1,a+1+n);
	work();
	for(int i=1;i<=n;i++)
	{
		putchar(ans[i]+'0');
	}
	putchar('\n');
}
signed main(){
	#ifdef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
	#endif
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}
```