ACM ICPC 2008–2009, NEERC, Northern Subregional Contest

Problem C. Class

题意:给定三个参数,n(学生人数),r(教室有几排座位),c(教室有几列座位),让你计算教室的饱和度(某一排或者某一列能坐下的最大的人数中的最小值),并输出其中一种入座方式。比如样例,n=16,r=4,c=6,则某一排最多可以坐6个人,某一列最多可以坐4个人,取最小值4即为教室饱和度。然后根据饱和度和总人数输出入座方式。

解题思路:假设上述情况中的某一列和某一排都为第0列和第0排,然后判断r,c的最小值与现有人数的一半(因为要在横竖两个方向上入座)的大小,取最小值即为饱和度。输出座位情况时先填充第0列和第0行,剩下的人数填充在其余位置。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<memory.h>
#include<algorithm>
using namespace std;
int a[120][120];
int main(){
    freopen("class.in","r",stdin);
    freopen("class.out","w",stdout);
    int n,r,c;
    while(scanf("%d%d%d",&n,&r,&c)!=EOF){
        int t=(n+1)/2;//总人数的一半
        memset(a,0,sizeof(a));
        int minx=min(r,c);
        int ans;
        if(t>minx){//取最小值即为饱和度
            ans=minx;
        }
        else{
            ans=t;
        }
        for(int i=0;i<ans;i++){
            a[i][0]=1;
            a[0][i]=1;
        }
        int k=n-(2*ans-1);//剩下的人数
        for(int i=0;i<r;i++){
            if(k==0){
                break;
            }
            for(int j=0;j<c;j++){
                if(k==0){
                    break;
                }
                if(a[i][j]==0){
                    a[i][j]=1;
                    k--;
                }
            }
        }
        cout<<ans<<endl;
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(a[i][j]==1){
                    cout<<"#";
                }
                else{
                    cout<<".";
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

Problem D. Deposits

题意:给定两个数列,数列a和数列b,问满足a[i]%b[j]==0(i=1,2,3……,n,j=1,2,3……m)的组合一共有多少对

解题思路:正难则反,如果用两重循环遍历a和b,并判断a[i]%b[j]==0则一定超时,所以采用倍数的方法,将出现在数列a和b中的数分别记录在booka和bookb数组中,然后遍历bookb数组,得到相应的倍数个数相加即可

#include<iostream>
#include<cstring>
#include<memory.h>
#include<cstdio>
using namespace std;
const int MAXN=1001000;
//标记数组记录数列中元素出现的次数
long long booka[MAXN],bookb[MAXN];
long long n,m,ans;
long long inx;
int main(){
    freopen("deposits.in","r",stdin);
    freopen("deposits.out","w",stdout);
    while(scanf("%d",&n)!=EOF){
        ans=0;
        memset(booka,0,sizeof(booka));
        memset(bookb,0,sizeof(bookb));
        for(int i=0;i<n;i++)
            scanf("%d",&inx),
            booka[inx]++;
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&inx);
            bookb[inx]++;
        }
        for(int i=0;i<MAXN;i++){
            if(bookb[i]!=0)//出现在数列b中
                for(int j=1;j*i<MAXN;j++)
                    ans+=bookb[i]*booka[i*j];
        }
        cout<<ans<<endl;
    }
}

Problem H. Holes

题意:有一种打字机在打印数字时会穿透纸张形成圆片,比如数字0,4,6,9会形成一个圆片,8会形成两个圆片,其余不会形成。问给定圆片数量,打印那个数字能得到这么多圆片(注意:打印的这个数字应尽量小)
解题思路:找规律,特判0和1,其余的如果是奇数则多打印一个4,偶数只打印8,这样才能最小。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main(){
    int h;
    freopen("holes.in","r",stdin);
    freopen("holes.out","w",stdout);
    while(~scanf("%d",&h)){
        if(h==0){
            cout<<1<<endl;
        }
        else if(h==1){
            cout<<0<<endl;
        }
        else{
            int temp=h/2;
            if(h%2==1){
                cout<<4;
            }
            for(int i=0;i<temp;i++){
                cout<<8;
            }
            cout<<endl;
        }
    }
    return 0;
}

 

标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注