at_agc006_d 题解

没思路，先打表，用以下程序打表。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10000;
int a[N],b[N];
inline int mid(int x,int y,int z){if(x>y)swap(x,y);if(x>z)swap(x,z);if(y>z)swap(y,z);return y;}
signed main()
{
	int n;
	mt19937 rd(__builtin_ia32_rdtsc());
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=i;
	shuffle(a+1,a+1+n,rd);
	for(int i=1;i<=n;i++)cerr<<a[i]<<' ';
	cerr<<'\n';
	for(int i=2;i*2<=n+1;i++)
	{
		for(int j=1;j<i;j++)cerr<<"  ";
		for(int j=i;j+i-1<=n;j++)
			b[j]=mid(a[j-1],a[j],a[j+1]),cerr<<b[j]<<' ';
		cerr<<'\n';
		memcpy(a,b,sizeof(int)*n);
	}
}

只发现了一个特点，大多塔顶的数在塔中间都出现不止一次，比如下面这组，5 出现了很多次。

CPP

9 2 6 4 8 5 3 7 1
  6 4 6 5 5 5 3
    6 5 5 5 5
      5 5 5
        5

但还是不会做，考虑其他方向。每次操作求的是中位数，与数字之间大小关系有关，想到二分或者三分。先猜个结论，大小越接近塔顶的数消失的时间越晚，这样可以三分求出答案。再打一些表发现结论不成立，将塔中间的数的控制范围映射到塔底，对于控制的区间不相交的数很难互相产生影响，所以不能三分。

考虑二分塔顶的数，每次 check 塔顶的数是否大于等于当前二分的数。check 时只需要考虑数与当前二分的数的大小关系，自然想到 01 二分，只需要判断塔顶的数是 0 还是 1 即可。但不会判断，再次打表，用以下程序。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10000;
int a[N],b[N];
inline int mid(int x,int y,int z){if(x>y)swap(x,y);if(x>z)swap(x,z);if(y>z)swap(y,z);return y;}
signed main()
{
	int n;
	mt19937 rd(__builtin_ia32_rdtsc());
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=rd()&1;
	for(int i=1;i<=n;i++)cerr<<a[i]<<' ';
	cerr<<'\n';
	for(int i=2;i*2<=n+1;i++)
	{
		for(int j=1;j<i;j++)cerr<<"  ";
		for(int j=i;j+i-1<=n;j++)
			b[j]=mid(a[j-1],a[j],a[j+1]),cerr<<b[j]<<' ';
		cerr<<'\n';
		memcpy(a,b,sizeof(int)*n);
	}
}

获得以下表。

CPP

1 0 1 1 0 0 1 1 0
  1 1 1 0 0 1 1
    1 1 0 0 1
      1 0 0
        0

发现相邻的两个相同数（不是边界）不会消失，并且会向周围非相同数的位置扩散，也很好证明，枚举六个数的每种情况即可。

于是找到能最先扩散到中间的数即可，也就是离中间最近的两个相同数（没有相同数的情况手模一下再特判）。

最后代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+100;
int n,a[N];
bool b[N];
inline bool check()
{
	for(int i=1;i*2<=n;i++)
	{
		if(b[n/2+1+i]==b[n/2+1+i-1])return b[n/2+1+i];
		if(b[n/2+1-i]==b[n/2+1-i+1])return b[n/2+1-i];
	}
	return b[1];
}
signed main()
{
	cin>>n;n<<=1;n--;
	for(int i=1;i<=n;i++)cin>>a[i];
	int l=1,r=n,mid,ans=0;
	while(l<=r)
	{
		mid=(l+r)>>1;
		for(int i=1;i<=n;i++)b[i]=a[i]>=mid;
		if(check())ans=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<ans;
}

文章操作

相关推荐

评论

at_agc006_d 题解