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

nefu 1649 说起矩阵,我就想起

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,k,i,j,a[205][205];
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        cin>>a[i][j];
    for(i=1;i<=n;i++)
        for(j=m+1;j<=m+k;j++)
        cin>>a[i][j];
    for(i=1;i<=m+k;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(j==n)printf("%d\n",a[j][i]);
            else printf("%d ",a[j][i]);
        }
    }
    return 0;
}

nefu 1652 中美合拍

0与任何数异或都等于那个数本身!
那么可以直接初始化ans=0,不需要开数组。

#include <bits/stdc++.h>
using namespace std;
bool judge(long long n)
{
    long long s=0;
    while(n)
    {if(n&1)s++;n=n/2;}
    if(s&1) return 1;
    return 0;
}
int main()
{
    long long ans,x,n;
    ios::sync_with_stdio(false);
    cin>>n;
    ans=0;
    while(n--)
    {
        cin>>x;
        if(judge(x))
        ans=ans^x;
    }
    printf("%lld\n",ans);
    return 0;
}

nefu 1651 文体两开花

这题先算出前几项找规律
假设输入i时答案为ans[i]
ans[1]=3=1×3
ans[2]=8=2×4
ans[3]=21=3×7
ans[4]=55=5×11
ans[i]就是两个类斐波那契数列的乘积!

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,i,a[11],b[11],ans[11];
    a[1]=1,a[2]=2,b[1]=3,b[2]=4,ans[1]=3,ans[2]=8;
    for(i=3;i<=10;i++)
    {
        a[i]=a[i-1]+a[i-2];
        b[i]=b[i-1]+b[i-2];
        ans[i]=a[i]*b[i];
    }
    cin>>t;
    while(t--)
    {
        cin>>n;
        printf("%d\n",ans[n]);
    }
    return 0;
}

nefu 1654 孙悟空耍赖皮(这题和nefu 1648是完全一样的代码)

#include <bits/stdc++.h>
using namespace std;
int n,k,i,l,r,m,s,ans,a[10010];
bool  judge(int m)
{
    s=0;
    for(i=1;i<=n;i++)
        s=s+a[i]/m;
    return s>=k;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>k)
    {

        for(i=1;i<=n;i++)
            cin>>a[i];
        l=0,r=10000000;
        while(l<=r)
        {
            m=l+(r-l)/2;
            if(judge(m))ans=m,l=m+1;
            else r=m-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

nefu 1653 gcd

#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,c,d,min;
    while(cin>>a>>b>>c>>d)
    {
        a=a+c;
        b=b+d;
        min=gcd(a,b);
        if(a==b)printf("1\n");
        else printf("%d/%d\n",a/min,b/min);
    }
    return 0;
}

nefu 1659 没必要的排序1

数据小直接sort。

#include <bits/stdc++.h>
using namespace std;
int n,k,i,ans,a[1001];
int main()
{
    cin>>n>>k;
    for(i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    ans=0;
    for(i=1;i<=k;i++)
        ans=ans+a[i];
    printf("%d\n",ans);
    return 0;
}

nefu 1650 没必要的排序2

这题是上面那题的数据加强版,sort过不了,要改进算法。

桶排序解决,从大到小统计每个数出现了几次。

为了便于理解代码,可以先举个简单的例子
例如100 100 99 99 99 88 88 88 88 77 77 66
100 有2个
99有3个
88 有4个
77有2个
66 有1个
如果要求以上数列中前4个最大的数的和,很简单吧?

看这题,从1e5到1,直到数的个数num大于等于k ,
如果用来计数的num大于k,再减去多加的值即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
const int maxk=1e5+10;
int t[maxk];// t[i] 为 i 这个数出现的次数
int main()
{
    ios::sync_with_stdio(false);
    int i,x,n,k,ans,num;
    cin>>n>>k;
    memset(t,0,sizeof(t));//计数之前初始化数组是个好习惯,这题只是单组输入,这行也可以省略
    for(i=1;i<=n;i++)
    {
        cin>>x;
        t[x]++;
    }
    num=ans=0;
    for(i=1e5;i>=1;i--)
    {
        if(t[i]>0)//如果有i这个数,那么i出现的次数t[i]>0,如果t[i]=0,没有这个数就不用再加上去了
        {
            ans=ans+t[i]*i;
            num=num+t[i];
        }
        if(num>=k)
        {
            ans=ans-(num-k)*i;//减去多加的值
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}