Codeforces Round #641 Div1.B Orac and Medians 中文题解
Caro23333
2020-04-30 00:22:49
### Orac and Medians 中文题解
记$B_i=\left\{\begin{aligned} 0,A_i<k\\1,A_i=k\\2,A_i>k\end{aligned} \right.$，于是问题转化成对$B$进行有限次操作使$B$中所有元素变成$1$。
下面证明，有解当且仅当 $\exists 1\le i\le n,\textrm{s.t.}B_i=1$ 且 $\exists 1\le i<j\le n,\mathrm{s.t.}j-i\le2,B_i>0,B_j>0$ 。
必要性是显然的：若 $\forall 1\le i\le n, B_i\neq 1$ ，无解；若任何两个非$0$的数之间至少有$2$个$0$，则任何一段区间的中位数均为$0$，无解。
下面考虑充分性。如果$B$中有两个相邻的元素均为$1$，则不断选择一个长度至少为$3$且恰有一个数不为$1$的区间执行操作，直到所有数都是$1$。容易证明这样的操作方案是存在的。
于是，如果存在一个区间 $[l,r]$ 使得 $r-l+1\ge2$ 且 ${B_l,B_{l+1},\dots,B_r}$ 的中位数是$1$，只需要先对 $[l,r]$ 执行一次操作，再使用上面的策略。
- 如果一个长为$3$的区间 $[i,i+2]$ 满足 $\{B_i,B_{i+1},B_{i+2}\}=\{0,1,2\}$ 或 $\{1,1,2\}$ 或 $\{0,1,1\}$ 或 $\{1,1,1\}$，那么只需要先对它执行一次操作即可。
- 如果 $[i,i+2]$ 满足$\{B_i,B_{i+1},B_{i+2}\}=\{1,2,2\}$ ，只需要对它的一个长为$2$的子区间执行一次操作即可。
- 如果任何一个长为$3$的区间都不满足上述条件，因为 $\exists 1\le i<j\le n,\mathrm{s.t.}j-i\le2,B_i>0,B_j>0$ ，故存在一个区间 $[i,i+2]$ 满足 $\{B_i,B_{i+1},B_{i+2}\}=\{0,2,2\}$ 或 $\{2,2,2\}$ ，于是先对$[i,i+2]$执行一次操作，再不断选择一个长度至少为$3$且恰有一个数不为$2$的区间执行操作，直到存在两个相邻的数，它们分别是$1$和$2$为止。对这两个相邻的数执行一次操作即可。
于是，充分性得证。故只需要检查$B$中是否有$1$以及是否存在两个数$i$和$j$，满足 $1\le j-i\le 2, B_i>0,B_j>0$ 即可，复杂度$O(n)$ 。
Problem and Tutorial by AKEE
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define x first
#define y second
#define mp make_pair
#define pb push_back
template <typename TYPE> inline void chkmax(TYPE &x,TYPE y){x<y?x=y:TYPE();}
template <typename TYPE> inline void chkmin(TYPE &x,TYPE y){y<x?x=y:TYPE();}
template <typename TYPE> void readint(TYPE &x)
{
x=0;int f=1;char c;
for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+c-'0';
x*=f;
}
const int MAXN=500005;
int n,k,a[MAXN];
bool solve()
{
readint(n),readint(k);
bool flag=0;
for(int i=1;i<=n;++i)
{
readint(a[i]);
if(a[i]<k)a[i]=0;
else if(a[i]>k)a[i]=2;
else a[i]=1;
if(a[i]==1)flag=1;
}
if(!flag)return 0;
if(n==1)return 1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n && j-i<=2;++j)
if(a[i] && a[j])return 1;
return 0;
}
int main()
{
int T;
readint(T);
while(T--)printf(solve()?"yes\n":"no\n");
return 0;
}
```