To_Heart—题解——AT2165

• 2021 年 7 月 7 日
• 筆記

这是一篇解题报告

首先，看到标签，考虑二分答案。

我们二分答案（即塔顶的值），把大于或等于这个值的变为1，否则变为0。

很容易发现，如果塔顶的答案是1，那么就说明值可以更大，否则相反。

复制一波样例

   4
  454
 36454
1637452

因为答案是4，所以我们把3、4、5为答案的情况都拿出来观察一下

3:
   0
  000
 10000
1010001

5:
   1
  111
 10111
1010111

4:
   1
  101
 10101
1010101

很容易想到从左往右一直找，直到找到两个相同的值，并返回这个值。如果没有，那么就看第n项是0还是1，是0则可以，是1则不行

可是会被下面这种情况hack

   1
  011
 00110
0001100		

那么会不会是中间往两边的找到的第一组相等的值呢？

发现没有问题，but

   0
  010
 01010
0101010

    0
   010
  01010
 0101010
010101010

可以发现在找不到相同的相邻项时，层数不同，第n项的答案的影响不同。

然后可以发现如果是奇数层，那么塔顶的值就和塔底的第n项相同，否则就不同

然后就做完了qwq

代码如下(注释显示艰辛历程)

#include<bits/stdc++.h>
using namespace std;

int n;
int a[400005];
int b[400005];

bool Cheak(int  x){
	for(int i=1;i<=n*2-1;i++)
		b[i]=a[i]>=x;
	for(int i=1;i<n;i++){
		if(b[n-i]==b[n-i+1])
			return b[n-i+1];
		if(b[n+i]==b[n+i-1])
			return b[n+i-1];
	}
	if(n&1)
		return b[n];
	return !b[n];
}

int main(){
	cin>>n;
	for(int i=1;i<=n*2-1;i++)
		scanf("%d",&a[i]);
	int l=1,r=2*n-1;
	int ans=l;
	while(l<=r){
		int mid=(l+r)>>1;
		if(Cheak(mid))
			ans=mid,l=mid+1;
		else
			r=mid-1;
//		printf("%d %d\n",l,r);
	}
	printf("%d\n",ans);
	return 0;
}
/*
   4
  454
 36454
1637452

3:
   0
  000
 10000
1010001

5:
   1
  111
 10111
1010111

4:
   1
  101
 10101
1010101

   1
  011
 00110
0001100			qwq hack了 

中间往边？
   0
  100
 11001
1110011 

中间贡献最大 

如果没有相同？
   1
  101
 10101
1010101

   0
  010
 01010
0101010
 
看中间是否为1。 

不对qwq 

    0
   010
  01010
 0101010
010101010

层数变化会改变ans
F**k 
*/