本次训练共 12 题,本文附AC代码和题目链接。

nefu 8 二倍的问题

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,t,n,ans,a[20];
    while(cin>>t)
    {
        while(t--)
        {
            n=ans=0;
            while(cin>>a[n]&&a[n])n++;//输入数据a[0]~a[n-1]
            sort(a,a+n);
            for(i=0;i<n;i++)
            {
                for(j=i+1;j<n;j++)
                {if(a[j]==a[i]*2)ans++;}
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

nefu 105 统计

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,s,a,i;
    while(scanf("%d",&n)!=-1)
    {
        s=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a);
            if(a<60)s++;
        }
        printf("%d\n",s);
    }
    return 0;
}

nefu 193 字符串统计

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,n,s;
    char a[101];
    while(scanf("%d",&n)!=-1)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%s",&a);
            s=0;
            for(j=0;j<strlen(a);j++)
            {
                if(a[j]>='0'&&a[j]<='9')
                s++;
            }
            printf("%d\n",s);
        }
    }
    return 0;
}

nefu 572 密码箱

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,i;
    while(scanf("%d",&n)!=-1)
    {
        for(i=n+1;i<=999;i++)
            printf("%.3d\n",i);//%.3d输出007,012等含前缀0的三位数
    }
    return 0;
}

nefu 573 大乐透

写了6层循环,时间复杂度很大,这题数据小不超时,数据大就别想着暴力枚举了。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[50],k,i1,i2,i3,i4,i5,i6;
    while(scanf("%d",&k)!=-1)
    {
        if(k==0)break;
        for(i1=1;i1<=k;i1++)
        scanf("%d",&a[i1]);
        for(i1=1;i1<=k;i1++)
        {
            for(i2=i1+1;i2<=k;i2++)
            {
                for(i3=i2+1;i3<=k;i3++)
                {
                    for(i4=i3+1;i4<=k;i4++)
                    {
                        for(i5=i4+1;i5<=k;i5++)
                        {
                            for(i6=i5+1;i6<=k;i6++)
                            printf("%d %d %d %d %d %d\n",a[i1],a[i2],a[i3],a[i4],a[i5],a[i6]);
                        }
                    }
                }
            }
        }
    }
    return 0;
}

nefu 574 丑数

这题难点在于丑数的排序,即由最先4个最小的丑数乘以2、3、5、7产生之后的丑数,
关键是怎么产生之后的丑数,并且让之后产生的所有丑数按升序排列,详见注释。

#include <bits/stdc++.h>
#define min4(a,b,c,d) min(min(a,b),min(c,d))
using namespace std;
int n,p2,p3,p5,p7,a[5850];//定义min4(a,b,c,d),找四个数中的最小值
int main()
{
    a[1]=1;p2=p3=p5=p7=1;
    for(int i=2;i<=5842;i++)//打表5842个丑数
    {
        a[i]=min4(a[p2]*2,a[p3]*3,a[p5]*5,a[p7]*7);//a[p2]、a[p3]、a[p5]、a[p7]分别为*2、*3、*5、*7的次数
        if(a[i]%2==0)p2++;//如果选择的最小值a[i]是乘以了2,则*2的丑数下标位置后移一位
        if(a[i]%3==0)p3++;
        if(a[i]%5==0)p5++;
        if(a[i]%7==0)p7++;
    }
    while(cin>>n&&n)
        printf("%d\n",a[n]);
    return 0;
}

nefu 575 矩形

完全被覆盖的矩形,是指被其他所有矩形覆盖的矩形。

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x1,x2,y1,y2;
}p[1001];
int main()
{    
    int i,j,n;
    while(scanf("%d",&n)!=-1)
    {
        for(i=1;i<=n;i++)
        scanf("%d%d%d%d",&p[i].x1,&p[i].x2,&p[i].y1,&p[i].y2);
        int sum=0;
        for(i=1;i<=n;i++)
        {
            int s=0;
            for(j=1;j<=n;j++)
            {
                if(p[i].x1>=p[j].x1&&p[i].x2<=p[j].x2&&p[i].y1>=p[j].y1&&p[i].y2<=p[j].y2)
                    s++;
            }
            if(s==n)
                sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}

nefu 1639 抽奖

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[10010],i,x,n,s;
    while(scanf("%d",&n)!=-1)
    {
        int flag=0;
        for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
        scanf("%d",&x);
        for(i=1;i<=n;i++)
        {
            if(a[i]==x)
            {
                flag=1;
                printf("%d\n",i);
                break;
            }
        }
        if(flag==0)printf("0\n");
    }
    return 0;
}

nefu 1640 比身高

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[1001],i,j,n,s,lsum,rsum;
    while(scanf("%d",&n)!=-1)
    {
        for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
        s=0;
        for(i=1;i<=n;i++)
        {
            lsum=rsum=0;
            for(j=i-1;j>=1;j--)
            {
                if(a[j]>a[i])
                    lsum++;
            }
            for(j=i+1;j<=n;j++)
            {
                if(a[j]>a[i])
                    rsum++;
            }
            if(lsum==rsum)
                s++;
        }
        printf("%d\n",s);
    }
    return 0;
}

nefu 1642 楼层编号

#include <bits/stdc++.h>
using namespace std;
int m,t,i,ans;
bool judge(int n)//若这个房间存在,即这个房间编号不包含数字t,为true
{
    int d;
    while(n)
    {
        d=n%10;
        n=n/10;
        if(d==t)return 0;
    }
    return 1;
}
int main()
{
    cin>>m>>t;
    ans=0;
    for(i=1;i<=m;i++)
    {if(judge(i))ans++;}
    printf("%d\n",ans);
    return 0;
}

nefu 1643 比例简化

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int main()
{
    int a,b,i,j,l,ans1,ans2;
    double s1,s2,d,min;
    while(cin>>a>>b>>l)
    {
        min=10000;
        for(i=l;i>=1;i--)
        {
            for(j=l;j>=1;j--)
            {
                if(gcd(i,j)==1)
                {
                    s1=1.0*i/j;
                    s2=1.0*a/b;
                    if(s1>=s2)
                    {
                        d=s1-s2;
                        if(d<min)
                        {
                            min=d;
                            ans1=i;
                            ans2=j;
                        }
                    }
                }
            }
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

nefu 1644 奶牛碑文

这题实际上是要你统计每个O字母左边有多少个C字母(假设有c[i]个)以及右边有多少个W字母(假设有w[i]个),则这个O字母可以组成c[i]w[i]个cow单词,把所有O字母左右两边的c[i]w[i]累加即可。

#include <bits/stdc++.h>
using namespace std;
long long n,i,k1,k2,ans,c[100010],w[100010];
char str[100010];
int main()
{
    scanf("%lld%s",&n,str);
    k1=k2=ans=0;//k1,k2为临时计数变量
    for(i=0;i<n;i++)
    {
        if(str[i]=='C') k1++;
        c[i]=k1;
    }
    for(i=n-1;i>=0;i--)
    {
        if(str[i]=='W') k2++;
        w[i]=k2;
    }
    for(i=0;i<n;i++)
    {
        if(str[i]=='O')
        ans=ans+c[i]*w[i];
    }
    printf("%lld\n",ans);
    return 0;
}