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

#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;
}