构造题

构造题就是有多种正确答案，任意输出一种情况即可的题，如题目中说：

"YES"、"Yes"、"yes"和"yEs"都会被判定为肯定答案

构造题多为思维题，比同级别的题目难一些

鸽巢原理

鸽巢原理常用于证明存在性

最简单的情况：n个箱子要放入n+1件物品

很明显如果每个箱子先放上一件东西的话就有一个箱子需要放上两件物品
如果是k个箱子放上n件物品

而如果平均放置的话就有一个箱子需要放上 $\lceil \frac{n}{k} \rceil$ 件物品

T1 A - Coloring

题意：

在n格格子中放入m种数，每种数必须填

a_i

个，且不能在连续k个格子中出现相同的数

思路：

注意到需要连续的k个数字互不相同，所以我们可以把k个不相同的数字看成一组,当然不可能每次都整除，总会多余一点

根据鸽巢原理可知k个箱子放上n件物品一个箱子最多只能放上

\lceil \frac{n}{k} \rceil

件物品，所以任意一个

a_i>\lceil \frac{n}{k} \rceil

就会出现连续k个格子内出现相同的数的情况，输出

NO

在有剩余时需统计

\lceil \frac{n}{k} \rceil

的数量，如果

\lceil \frac{n}{k} \rceil

的数量大于

(n-1) \mod k+1

则不成立，输出

NO

，否则输出

YES

程序：

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn(1e5+10);
int n,m,k;
void solve(){
	cin>>n>>m>>k;
	int ans=0;
	int sum=(n+k-1)/k;
	bool flag(false);
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		if(x==sum){
			ans++;
		}
		if(x>sum){
			flag=true;
		}
	}
	if(ans<=(n-1)%k+1&&!flag){
		cout<<"YES\n";
	}else{
		cout<<"NO\n";
	}
	return;
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

特别注意：

因为时多测，所以不能在未输入完时结束直接输出，这会使这次的输入继承到下一次输入中去引发一系列问题

T2 B - New Year's Problem

题意：

思路：

程序：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
int n,m;
int a[maxn];
bool check(int x){
	for(int i(1);i<=n;i++){
		bool flag(true);
		for(int j(1);j<=m;j++){
			if(a[(j-1)*n+i]>=x){
				flag=false;
			}
		}
		if(flag){
			return false;
		}
	}
	for(int i(1);i<=m;i++){
		int sum(0);
		for(int j(1);j<=n;j++){
			if(a[(i-1)*n+j]>=x){
				sum++;
			}
		}
		if(sum>1){
			return true;
		}
	}
	return false;
}
void solve(){
	cin>>m>>n;
	for(int i(1);i<=m;i++){
		for(int j(1);j<=n;j++){
			cin>>a[(i-1)*n+j];
		}
	}
	int l(0),r(1e9+7);
	while(l<r){
		int mid((l+r)/2);
		if(check(mid+1)){
			l=mid+1;
		}else{
			r=mid;
		}
	}
	cout<<l<<'\n';
	return;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

10.17-构造题-鸽巢原理

文章操作

构造题