首页 > 其他分享 >Atcoder [AGC006D] Median Pyramid Hard 题解 [ 紫 ] [ 二分 ] [ adhoc ]

Atcoder [AGC006D] Median Pyramid Hard 题解 [ 紫 ] [ 二分 ] [ adhoc ]

时间:2024-08-28 17:53:35浏览次数:8  
标签:二分 Atcoder Pyramid int 题解 01 区间 大于 check

Median Pyramid Hard:二分 trick 加上性质观察题。

trick

我们可以二分值域,然后把大于等于它的数标记成 \(1\),其他标记为 \(0\)(有些题需要标记成 \(-1\) ),然后根据这个来 check 方案是否可行,这通常通过判断某个数是否是 \(1\) 来实现。本质上其实就是 check 大于等于它的数能否成为答案(大于等于它的数为 \(1\))。常用于查找中位数、第 \(k\) 个数,以及大小关系只注重两种(比如只区分大于 \(7\) 和小于 \(7\) ,而大于 \(7\) 的数之间的大小无关的情况)。

这道题就是二分塔顶,check 大于等于它的数能不能成为塔顶,把大于等于它的数设为 \(1\),其他设为 \(0\) 。

观察性质

那么这题显然对应着“大小关系只注重两种”的用途,接下来考虑如何 check。

观察到一个位置下面的三个数只可能是这些情况:

0 0 0  => 0
0 0 1  => 0
0 1 0  => 0
0 1 1  => 1
1 0 0  => 0
1 0 1  => 1
1 1 0  => 1
1 1 1  => 1

然后我们手搓样例,继续观察:

sample1:
      1
    1 1 1
  0 1 1 1 0
0 0 1 1 0 1 0

sample2:
      1
    0 1 1
  0 1 0 1 1
0 1 0 1 0 1 1

可以观察到,当 \(1\) 或者 \(0\) 形成一段长度大于等于 \(2\) 的连续区间时,他们就能不断上升,直到塔顶。因为结果与这个区间的长度基本无关,所以我们只取最靠近中间的两个即可。

如果有一段区间既不是 \(1\) 的连续区间,也不是 \(0\) 的区间呢?那么它一定是 \(01\) 交替的区间。而 \(01\) 交替的区间又正好可以让某一段连续区间不断攀升(起到辅助作用)。因此,我们只要找到离中间最近的一段交替区间即可,它的数字就是塔顶的数字。

可以证明,一定没有一个 \(1\) 的连续区间和一个 \(0\) 的连续区间,使他们到中间的距离相等,例子如下:

1 1 1 * * * 0 0 0

此时星号里必须填入一个 \(01\) 交替,以 \(0\) 开头,以 \(1\) 结尾的串。但这显然不成立,因此没有这种情况。

还有一种特殊情况:所有 \(01\) 都是交替出现,找不到满足要求的 \(01\) 区间。很容易发现这种情况的答案就是最底层第一个数的数字(手动模拟一下就可以了)。那么特判一下就可以了。

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int a[200005],n,f[200005];
bool check(int p)
{
	for(int i=1;i<=2*n-1;i++)f[i]=(a[i]>=p);
	for(int i=0;i<=n-2;i++)
	{
		if(f[n-i]==f[n-i-1])return f[n-i];
		if(f[n+i]==f[n+i+1])return f[n+i];
	}
	return f[1];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=2*n-1;i++)cin>>a[i];
	int l=1,r=2*n-1,mid;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}

标签:二分,Atcoder,Pyramid,int,题解,01,区间,大于,check
From: https://www.cnblogs.com/zhr0102/p/18385258

相关文章

  • AtCoder Beginner Contest 368
    A-Cut题意签到题思路代码#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,k;scanf("%d%d",&n,&k);vector<int>v(n);for(inti=0;i<n;i++){scanf("%d",&v[i......
  • 文件排版 题解
    前言题目链接:HDU。题意简述给\(n\)个单词和一张图片排版。每个单词长度为\(a_i\)。图片占行不确定,但是占列始终为\([dw+1,dw+pw]\)。排版宽度为\(W\),高度无限制。要求单词间有长度为\(1\)的空格,单词不能超出宽度\(W\),不能覆盖在图片上,单词间相对顺序不能发生改变......
  • 题解 [ABC199F] Graph Smoothing(中文/English)
    本题解提供英文版,位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.设行向量:\[A^{(k)}=\begin{bmatrix}a_1^{(k)}&a_2^{(k)}&\cdots&a_n^{(k)}\end{bmatrix}\]表示\(k\)次操作后每个节点点权的期望。特别地,\(A^{(0)}\)表......
  • 递推配套P1192 & 题解:P1192 台阶问题
    我们现在考虑递推。现在的问题是,如何从前几个数据推导出下一个数据。我们现在先推导\(f(n)\)。设\(k=3\)。到\(n\)的方法就是到能一步到\(n\)的台阶的方法总和,所以我们可以推导出:\(f(n)=f(n-1)+f(n-2)+\dots+f(n-k)/f(1)\)。即为:\(f(n)=\sum_{i=......
  • LOJ #160. 树形背包 题解
    Description有\(N\)个物品,编号分别为\(1\ldotsN\)。物品\(i\)的重量为\(w_i\),价值为\(v_i\)。给出每个物品依赖于哪个物品。我们用\(d_i=j\(i>j>0)\)表示:如果要选取物品\(i\),就必须先选取物品\(j\)。另外,我们用\(d_i=0(i>0)\)表示:该物品不依赖于任何物品。......
  • CF1810G The Maximum Prefix 题解
    Description构造一个长度最多为\(n\)的数组\(a\),其每个元素均为\(1\)或\(-1\)。生成方式如下:选择任意整数\(k\in[1,n]\)作为\(a\)的长度。对于\(\foralli\in[1,k]\),有\(p_i\)的概率设\(a_i=1\),有\(1-p_i\)的概率设\(a_i=-1\)。在数列被生成后,计算\(s_i=a......
  • NOI2024 D1T3 口胡题解
    NOI2024D1T3口胡题解题目条件其实就是说对于点对\((a,b)\),从\(a\)到\(b\)的路径上至少要有一条从\(b\)指向\(a\)​的边。将初始状态记作\((T,S)\)​,其中\(T\)​是树,\(S\)​是二元组\((a,b)\)​的集合。注意到特殊性质A蕴含了:如果对于所有二元组\((a,b)\),\(a......
  • [COCI2012-2013#1] SNAGA 题解
    前言题目链接:洛谷。题意简述定义\(f(x)\)表示不能整除\(x\)的最小正整数。给出数字\(n\),每次\(n\getsf(n)\),当\(n=2\)时停止。定义\(g(n)\)为这一过程中的数字个数,例如\(g(6)=4\)。给定\(l,r\),求\(\sum\limits_{i=l}^rg(i)\)。\(3\leql\ltr......
  • 【题解】「CQOI2014」通配符匹配
    【题解】「CQOI2014」通配符匹配https://www.luogu.com.cn/problem/P3167令\(s\)为模式串,\(t\)为文本串。首先有一个显然的的dp是,\(f_{i,j}\)表示模式串的前\(i\)个和文本串的前\(j\)个是否匹配。显然\(O(n^2)\)是过不了的。Motivation:注意到题目限定了通配符......
  • CF645D - Robot Rapping Results Report 题解
    \[Problem\]有\(N\)个机器人,给出\(M\)组关系,表示两个机器人的能力关系,问至少需要前几组关系可以确定所有机器人的排名。\[Solution\]由于是求最少的前几组关系,而关系越少越难确定排名,关系越多越容易确定,不难发现本题满足单调性,考虑二分。那么给出关系要求总排名的题,就应该......