第八届蓝桥杯C/C++A组省赛

蓝桥杯 C++ 编程 竞赛 所有文稿

8.包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)

输出
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。

拓展欧几里得：一定存在（x,y）使得ax+by=gcd(a,b)

本题题意需要满则x>=0,y>=0（即包子的笼数是非负的）;也就是说，如果gcd（a,b）的值为1，那么对于任意的数值方程两边只需要乘以一个整数 ，即可凑出。这时候取决a和b的取值凑不出的情况就对应是系数是负值的情况。 当max(a,b,....)…………^2能够凑出后，以后所有的都可以凑出。因此检验到1e4即可。

如果gcd(a,b）的值不为1，
那么一定有所有的gcd(a,b)的正整数倍的数值是能够凑出来的。同样也有无数个数值是凑不出的。

/*3.3 21:12-21:38 背包问题*/
/*3.20 20:47*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <string.h>
using namespace std;
const int maxn=110;
int a[maxn],dp[10010],n,m=150;
int gcd(int a, int b){//最大公因数
    return b == 0 ? a : gcd(b, a%b);
}
int main(){
    memset(dp,0,sizeof(dp));
    cin>>n;
    for(int i=0;i<n;i++) {cin>>a[i];}
/*用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数*/
    int g = a[0];
    for(int i = 1; i < n; i++){
        g = gcd(g, a[i]);
    }
    if (g==1){
        sort(a,a+n);
        dp[0]=1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j+a[i] < 100*100+5; j++){
                if(dp[j]) dp[j+a[i]] = 1;
            }
        }
        long long cnt=0;
        for(int i=1;i<10010;i++) if(dp[i]==0) cnt++;
        cout<<cnt<<endl;
    }
    else cout<<"INF"<<endl;
    return 0;
}

9.分巧克力

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数  
2. 大小相同  

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。

输出
输出切出的正方形巧克力最大可能的边长。

样例输入：
2 10
6 5
5 6

样例输出：
2

直接暴力，AC

/*21:30*/
/*21:48*/
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100000;
pair<int,int> a[maxn];
int main(){
    int n,k,len=0;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        a[i]=make_pair(x,y);
        if (x>len) len=x;
        if (y>len) len=y;
    }
    for(int c=len;c>=1;c--){
        int tot=0;
        bool found=false;
        for(int i=0;i<n;i++){
            if (a[i].first*a[i].second>c*c){
                int n1=a[i].first/c,n2=a[i].second/c;
                tot+=n1*n2;
            }
            if (tot>=k){
                cout<<c;
                system("pause");
                return 0;}
        }
    }
    system("pause");
    return 0;
}

更好的解题思路：用二分搜索化查找为判定的前提条件是答案具有单调性，很显然本题巧克力的边长具有单调性，故可以用二分搜索解法。

优化算法后：87分，最后一个案例未通过，debug中

/*21:56-22:15*/
/*20:02-20:38*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxn=100000;
int a[maxn][2];
int n,k,len=0;
bool find_len(int c){
    int tot=0;
    for(int i=0;i<n;i++){
        if (a[i][0]*a[i][1]>=c*c){
            int n1=a[i][0]/c,n2=a[i][1]/c;
            tot+=n1*n2;
        }
        if (tot>=k){
            return true;
        }
    }
    return false;
}
int main(){
    memset(a,0,sizeof(a));
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1];
        len=max(a[i][0],max(a[i][1],len));
    }
    int l=1,r=len;
    //cout<<endl<<r<<endl;
    while(l<r-1){
        int mid=l-(l-r)/2;
        if(find_len(mid)) l=mid;
        else r=mid-1;
        if(r-l==1){
            if (find_len(r)) cout<<r;
            else cout<<l;
            break;
            //printf("l=%d r=%d\n",l,r);
        }
    }
    system("pause");
    return 0;
}

需要注意：二分搜索中mid的加一减一问题，且输出为搜索结果-1

另外，二分搜索如果使用mid=(high+low)/2可能会出现数据溢出问题，改为用mid=low+(high-low)/2则不会有该问题

10.油漆问题

以下程序一个错误，两个超时，bug未知

/*19.3.5 12:40-13:00*/
#include <iostream>
#include <map>
using namespace std;
map<pair<int,int>,int> spa;
int main(){
    int n,tot=0;
    cin>>n;
    for(int i=0;i<n;i++) {
        pair<int,int> p1,p2;
        cin>>p1.first>>p1.second>>p2.first>>p2.second;
        int min_x=min(p1.first,p2.first);
        int min_y=min(p1.second,p2.second);
        int max_x=max(p1.first,p2.first);
        int max_y=max(p1.second,p2.second);
        for(int x=min_x+1;x<=max_x;x++){
            for(int y=min_y+1;y<=max_y;y++){
                if (!spa.count(make_pair(x,y))) {tot++;}
                spa[(make_pair(x,y))]=1;
            }
        }
    }
    cout<<spa.size();
    return 0;
}

改成用数组，注意面积数组用bool（听说测试数据有问题，应该是全通过的）

#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
int x_1[10010],x_2[10010],y_1[10010],y_2[10010];
bool  a[10010][10010];
int main(){
    memset(a,0,sizeof(a));
    memset(x_1,0,sizeof(x_1));
    memset(x_2,0,sizeof(x_2));
    memset(y_1,0,sizeof(y_1));
    memset(y_2,0,sizeof(y_2));
    long long n,tot=0;
    cin>>n;
    for(int i=0;i<n;i++) {
        scanf("%d%d%d%d",&x_1[i],&y_1[i],&x_2[i],&y_2[i]);
        if (x_2[i]<x_1[i]) {int t=x_2[i];x_2[i]=x_1[i];x_1[i]=t;}
        if (y_2[i]<y_1[i]){int t=y_2[i];y_2[i]=y_1[i];y_1[i]=t;}
    }
    for(int i=0;i<n;i++){
        for(int x=x_1[i];x<x_2[i];x++){
            for(int y=y_1[i];y<y_2[i];y++){             
                if (!a[x][y]) {tot++;a[x][y]=1;}
            }
        }
    }
    cout<<tot;
    return 0;
}

2019.3.22