CF1468H K and Medians 做题记录

给定奇数 $k$ 和长度分别为 $n,m$ 的序列 $a,b$，序列 $a$ 包含所有整数 $i$ 满足 $1\leq i\leq n$，$b$ 是给定的单调不减的序列。

现在你可以进行零次或若干次操作，每次操作选择序列 $a$ 的 $k$ 个整数，然后删除这 $k$ 个数里除了他们的中位数的其他 $(k-1)$ 个数。

求能否通过零次或若干次操作从序列 $a$ 的到序列 $b$。能就输出 YES，不能输出 NO。

$3\leq n\leq 2\times 10^5;3\leq k\leq n;1\leq m<n$，$1\leq b_1<b_2<...<b_m\leq n$。

遇到这种操作题，可以先考虑无解，然后想最后几次操作的情况，不要想太复杂。

首先若由于每次操作都会删掉 $k-1$ 个数，所以 $n-m\not\equiv 0\pmod{k-1}$ 一定无解。

考虑最后一次操作，不难发现，中位数一定是最后某个要留下的数，这个数左边和右边都要有 $\frac{k-1}{2}$ 个要删掉的数。除了这 $k-1$ 个要删掉的数，其它要删掉的数都可以乱删，由于 $n-m\equiv 0\pmod{k-1}$，所以可以让其它要删掉的数内部自己匹配。

那么只要找到某个最后要留下的数且这个数两边都至少有 $\frac{k-1}{2}$ 个要删除的数即有解，否则无解。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=200005;

int n,k,m;
int b[S],cnt[S];
int pre[S],suf[S];

inline void slove()
{
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	if((n-m)%(k-1)!=0) return void(puts("NO"));
	b[0]=0,b[m+1]=n+1;
	for(int i=1;i<=m+1;i++) cnt[i]=b[i]-b[i-1]-1;
	pre[0]=suf[m+2]=0;
	for(int i=1;i<=m+1;i++) pre[i]=pre[i-1]+cnt[i];
	for(int i=m+1;i>=1;i--) suf[i]=suf[i+1]+cnt[i];
	bool f=false;
	for(int i=1;i<=m;i++)
	{
		int lft=pre[i],rig=suf[i+1];
		if(lft>=(k-1)/2&&rig>=(k-1)/2) return void(puts("YES"));
	}
	puts("NO");
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}