10.17-构造题-鸽巢原理

· · 算法·理论

构造题

构造题就是有多种正确答案，任意输出一种情况即可的题，如题目中说："YES"、"Yes"、"yes"和"yEs"都会被判定为肯定答案

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

鸽巢原理

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

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

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

  2. 如果是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

程序：

#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

题意：

思路：

程序：

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