专栏文章

CF2085B Serval and Final MEX

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipt6vgd
此快照首次捕获于
2025/12/03 17:32
3 个月前
此快照最后确认于
2025/12/03 17:32
3 个月前
查看原文

题目传送门

思路

本蒟蒻将此题分为 55 种情况。

数组中不包含 00

此时将整个数组合并即可。
CPP
if(cnt==0)
{
  cout <<1<<'\n';
  cout <<1<<" "<<n<<'\n';
}

数组中包含 11 个 00

  1. 当 00 在下标为 11 的位置上时，此时将前两个数合并，最后将整个数组合并。
    CPP
    if(a[1]==0)
{
  cout <<2<<'\n';
  cout <<1<<" "<<2<<'\n';
  cout <<1<<" "<<n-1<<'\n';
}
  2. 当 00 在下标为 nn 的位置上时，此时将后两个数合并，最后将整个数组合并。
    CPP
    else if(a[n]==0)
{
  cout <<2<<'\n';
  cout <<n-1<<" "<<n<<'\n';
  cout <<1<<" "<<n-1<<'\n';
}
  3. 如果不符合上述条件，那么就先找出 00 的位置（将其设为 pp），之后将下标为 11 到 pp 的所有数合并，最后将整个数组合并。
    CPP
    else
{
  int p;
  for(int i=1;i<=n;i++)
  {
    if(a[i]==0)
    {
      p=i;
      break;
    }
  }
  cout <<2<<'\n';
  cout <<1<<" "<<p<<'\n';
  cout <<1<<" "<<n-p+1<<'\n';
}

数组中包含 22 个 00

  1. 当 00 在前两个位置上，此时将前两个数合并，最后将整个数组合并。
    CPP
    if(a[1]==0 && a[2]==0)
{
	cout <<2<<'\n';
	cout <<1<<" "<<2<<'\n';
	cout <<1<<" "<<n-1<<'\n';
}
  2. 当 00 在后两个位置上，此时将后两个数合并，最后将整个数组合并。
    CPP
    else if(a[n-1]==0 && a[n]==0)
{
	cout <<2<<'\n';
	cout <<n-1<<" "<<n<<'\n';
	cout <<1<<" "<<n-1<<'\n';
}
  3. 当 00 在下标为 11 和下标为 nn 的位置上时，此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。
    CPP
    else if(a[1]==0 && a[n]==0)
{
	cout <<3<<'\n';
	cout <<1<<" "<<2<<'\n';
	cout <<2<<" "<<n-1<<'\n';
	cout <<1<<" "<<2<<'\n';
}
  4. 当 00 在下标为 11 的位置上并且不在下标为 nn 的位置上时，此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。（实质上和上一种情况一样）。
  5. 当 00 不在下标为 11 的位置上并且在下标为 nn 的位置上时，此时先将后两个数合并，再将除了最后一个数之外的所有数合并，最后将剩下的两个数合并。
    CPP
    else if(a[1]!=0 && a[n]==0)
{
	cout <<3<<'\n';
	cout <<n-1<<" "<<n<<'\n';
	cout <<1<<" "<<n-2<<'\n';
	cout <<1<<" "<<2<<'\n';
}
  6. 如果不符合上述条件，那么就先找出第一个 00 的位置（将其设为 pp），然后先将下标为 11 到 pp 的所有数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。
    CPP
    else
{
	int p;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0)
		{
			p=i;
			break;
		}
	}
	cout <<3<<'\n';
	cout <<1<<" "<<p<<'\n';
	cout <<2<<" "<<n-p+1<<'\n';
	cout <<1<<" "<<2<<'\n';
}

数组中包含 nn 个 00

此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。
CPP
else if(cnt==n)
{
	cout <<3<<"\n";
	cout <<1<<" "<<2<<'\n';
	cout <<2<<" "<<n-1<<'\n';
	cout <<1<<" "<<2<<'\n'; 
}

数组中 00 的数量不符合上述四种情况

  1. 当 00 在下标为 11 和下标为 nn 的位置上时，此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。
    CPP
    if(a[1]==0 && a[n]==0)
{
	cout <<3<<'\n';
	cout <<1<<" "<<2<<'\n';
	cout <<2<<" "<<n-1<<'\n';
	cout <<1<<" "<<2<<'\n';
}
  2. 当 00 在下标为 11 的位置上并且不在下标为 nn 的位置上时，此时先将前两个数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。（实质上和上一种情况一样）。
  3. 当 00 不在下标为 11 的位置上并且在下标为 nn 的位置上时，此时先将后两个数合并，再将除了最后一个数之外的所有数合并，最后将剩下的两个数合并。
    CPP
    else if(a[1]!=0 && a[n]==0)
{
	cout <<3<<'\n';
	cout <<n-1<<" "<<n<<'\n';
	cout <<1<<" "<<n-2<<'\n';
	cout <<1<<" "<<2<<'\n';
}
  4. 如果不符合上述条件，那么就先找出第一个 00 的位置（将其设为 pp），然后先将下标为 11 到 pp 的所有数合并，再将除了第一个数之外的所有数合并，最后将剩下的两个数合并。
    CPP
    else
{
	int p;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0)
		{
			p=i;
			break;
		}
	}
	cout <<3<<'\n';
	cout <<1<<" "<<p<<'\n';
	cout <<2<<" "<<n-p+1<<'\n';
	cout <<1<<" "<<2<<'\n';
}

AC Code：

CPP
#include <bits/stdc++.h>
using namespace std;
const int N=5e3+4;
int a[N];
void solve()
{
	int n;
	cin >>n;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cin >>a[i];
		if(a[i]==0) cnt++;
	}
	if(cnt==0)
	{
		cout <<1<<'\n';
		cout <<1<<" "<<n<<'\n';
	}
	else if(cnt==1)
	{
		if(a[1]==0)
		{
			cout <<2<<'\n';
			cout <<1<<" "<<2<<'\n';
			cout <<1<<" "<<n-1<<'\n';
		}
		else if(a[n]==0)
		{
			cout <<2<<'\n';
			cout <<n-1<<" "<<n<<'\n';
			cout <<1<<" "<<n-1<<'\n';
		}
		else
		{
			int p;
			for(int i=1;i<=n;i++)
			{
				if(a[i]==0)
				{
					p=i;
					break;
				}
			}
			cout <<2<<'\n';
			cout <<1<<" "<<p<<'\n';
			cout <<1<<" "<<n-p+1<<'\n';
		}
	}
	else if(cnt==2)
	{
		if(a[1]==0 && a[2]==0)
		{
			cout <<2<<'\n';
			cout <<1<<" "<<2<<'\n';
			cout <<1<<" "<<n-1<<'\n';
		}
		else if(a[n-1]==0 && a[n]==0)
		{
			cout <<2<<'\n';
			cout <<n-1<<" "<<n<<'\n';
			cout <<1<<" "<<n-1<<'\n';
		}
		else if(a[1]==0 && a[n]==0)
		{
			cout <<3<<'\n';
			cout <<1<<" "<<2<<'\n';
			cout <<2<<" "<<n-1<<'\n';
			cout <<1<<" "<<2<<'\n';
		}
		else if(a[1]==0 && a[n]!=0)
		{
			cout <<3<<'\n';
			cout <<1<<" "<<2<<'\n';
			cout <<2<<" "<<n-1<<'\n';
			cout <<1<<" "<<2<<'\n';
		}
		else if(a[1]!=0 && a[n]==0)
		{
			cout <<3<<'\n';
			cout <<n-1<<" "<<n<<'\n';
			cout <<1<<" "<<n-2<<'\n';
			cout <<1<<" "<<2<<'\n';
		}
		else
		{
			int p;
			for(int i=1;i<=n;i++)
			{
				if(a[i]==0)
				{
					p=i;
					break;
				}
			}
			cout <<3<<'\n';
			cout <<1<<" "<<p<<'\n';
			cout <<2<<" "<<n-p+1<<'\n';
			cout <<1<<" "<<2<<'\n';
		}
	}
	else if(cnt==n)
	{
		cout <<3<<"\n";
		cout <<1<<" "<<2<<'\n';
		cout <<2<<" "<<n-1<<'\n';
		cout <<1<<" "<<2<<'\n'; 
	}
	else
	{
		if(a[1]==0 && a[n]==0)
		{
			cout <<3<<'\n';
			cout <<1<<" "<<2<<'\n';
			cout <<2<<" "<<n-1<<'\n';
			cout <<1<<" "<<2<<'\n';
		}
		else if(a[1]==0 && a[n]!=0)
		{
			cout <<3<<'\n';
			cout <<1<<" "<<2<<'\n';
			cout <<2<<" "<<n-1<<'\n';
			cout <<1<<" "<<2<<'\n';
		}
		else if(a[1]!=0 && a[n]==0)
		{
			cout <<3<<'\n';
			cout <<n-1<<" "<<n<<'\n';
			cout <<1<<" "<<n-2<<'\n';
			cout <<1<<" "<<2<<'\n';
		}
		else
		{
			int p;
			for(int i=1;i<=n;i++)
			{
				if(a[i]==0)
				{
					p=i;
					break;
				}
			}
			cout <<3<<'\n';
			cout <<1<<" "<<p<<'\n';
			cout <<2<<" "<<n-p+1<<'\n';
			cout <<1<<" "<<2<<'\n';
		}
		
	}
}
int main()
{
	int t;
	cin >>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

评论

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

正在加载评论...