大一寒假训练第一次考试（1 月 8 日上午）【更新完成】
本次训练共7题，本文附AC代码和题目链接。
#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;
}
#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;
}
