首页 > 其他分享 >CF1468H

CF1468H

时间:2022-10-17 22:22:55浏览次数:42  
标签:CF1468H return NO int void d% YES

首先判掉 \((n-m)\bmod (k-1)\ne0\) 的情况,显然是无解的。

考虑消去的最后一步,必然是以 \(b\) 中的某一元素为中位数进行的。

于是得到了一个必要条件:存在一个 \(b_i\),满足 \(a\) 中 \(b_i\) 的两侧都至少有 \(\frac{k}{2}\) 个不在 \(b\) 中的数。

构造说明这也是充分条件。

启发:可以考虑从最后一步入手,大胆猜想,小心求证。

Code:

#include <bits/stdc++.h>
using namespace std;
#define YES return printf("YES\n"), void()
#define NO return printf("NO\n"), void()
const int N = 200005;
int T;
int n, k, m;
int a[N];

void solve() {
	scanf("%d%d%d", &n, &k, &m);
	for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
	if ((n - m) % (k - 1)) NO;
	for (int i = 1; i <= m; ++i)
		if (a[i] - i >= (k - 1) / 2 && n - a[i] - (m - i) >= (k - 1) / 2) YES;
	NO;
}

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

标签:CF1468H,return,NO,int,void,d%,YES
From: https://www.cnblogs.com/Kobe303/p/16800951.html

相关文章