2020软院算法组新生周练 - 第四周
高飞大佬与他的硬币
Problem Description
高飞学长在结束了一天的敲代码之后，想要出门去买一点东西，现在高飞学长有着1，2，5，10四种面值的硬币，高飞学长在想要带着最少的硬币数量去购买东西，并且商店老板不会找零，
因此高飞学长会事先拜托他的室友咕咕咕学长事先调查好他需要的物品的价格总和
假设高飞学长拥有的每种硬币数量无限，现在请你输出高飞学长最少需要的硬币数量
Input
输入一个整数，表示商品的价值总和n(0<=n<=1e6)Output
输出一个整数，表示最少使用的硬币数量Sample Input
12
Sample Output
2
标程
#include<stdio.h>
int main(void){
int n;
while(~scanf("%d",&n)){
int ans=0;
ans+=n/10;
ans+=n%10/5;
ans+=n%10%5/2;
ans+=n%10%5%2/1;
printf("%d\n",ans);
}
return 0;
}hanhan学长与他的神秘字符
Problem Description
hanhan学长在一次偶然的机会发现了一串神秘的字符，hanhan学长惊奇的发现这一串字符有一个特点，即正着读和反着读都是一样的，像aba或者是abba这种
现在给你一串字符，请你判断它是否为神秘字符
Input
多组输入,第一行输入一个数字n，表示字符串的长度，第二行为一个字符串(0<n><=20)Output
如果是神秘字符，请输出“Yes, it is” 否则，请输出“No, it's not”Sample Input
3
aba
Sample Output
Yes, it is
标程
#include<stdio.h>
int main(void){
int n;
while(~scanf("%d",&n)){
char s[25];
getchar();
int i,j;
for(i=1;i<=n;++i){
scanf("%c",&s[i]);
}
i=1,j=n;
while(i<=j){
if(s[i]!=s[j]) break;
i++,j--;
}
if(i>j) printf("Yes, it is\n");
else printf("No, it's not\n");
}
return 0;
}千言和高飞的甜蜜双排Ⅰ
Problem Description
千言和高飞经常一起打一款名为“农药”的游戏千言玩的最多的位置为法师，现在千言凑够了出一件装备的钱
千言可以选择两件装备，装备A可以增加百分之45的伤害，装备B可以固定增加200点伤害，
现在告诉你千言在出装备前可以造成的伤害，请你帮千言选择购买哪一件装备
Input
多组输入，一行一个整数（0<=n<=10000)
Output
输出“A”或者“B”表示收益最大的装备,如果收益相同，千言会选择“B”装备
Sample Input
500
Sample Output
A
标程
#include<stdio.h>
int main(void){
int n;
while(~scanf("%d",&n)){
double cnt;
cnt=n*0.45;
if(cnt>200)
printf("A\n");
else
printf("B\n");
}
return 0;
}千言与高飞的甜蜜双排Ⅱ
Problem Description
最近高飞沉迷打野，在高飞来中路帮千言gank的时候，千言需要告诉高飞对面中单的血量
现在给你一个数字，表示对面的血量，请你打印出对面的血条，具体请看输入与输出样例
Input
多组输入，一行一个整数n（0<=n<=30)Output
请按以下格式打印,当n=5时，输出：+-----+ | |5 +-----+
Sample Input
10
0
Sample Output
+----------+ | |10 +----------+ ++ ||0 ++
标程
#include<stdio.h>
int main(void){
int n;
while(~scanf("%d",&n)){
printf("+");
for(int i=0;i<n;++i)
printf("-");
printf("+\n");
printf("|");
for(int i=0;i<n;++i)
printf(" ");
printf("|%d\n",n);
printf("+");
for(int i=0;i<n;++i)
printf("-");
printf("+\n");
}
return 0;
}hanhan学长的水果篮子
Problem Description
hanhan学长奉旨出去买水果，一共购买了n个篮子的水果，数量序列分别是a1，a2，a3.....hanhan学长手里有无限个水果，但是他会偷偷的从一个篮子里拿一个水果或者放一个水果进去，这样的操作不超过k次
如果可以进行以上操作，则计算序列中最大元素和最小元素之间的最小可能差值，操作次数不超过k次
Input
多组输入第一行包括两个整数，n和k（2<=n<=100,1<=k<=5000)序列中的元素总数和可以执行最大次数
第二行包含n个数，表示序列a1，a2,a3....(1<=a1<=1000)
Output
一个整数，表示操作次数不超过k次，序列中最大元素和最小元素之间的最小可能差值Sample Input
4 5
3 1 7 5
3 10
100 100 100
10 9
4 5 5 7 5 4 5 2 4 3
Sample Output
2
0
1
标程
#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
int main(void){
int n,m;
int s[MAXN];
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;++i)
scanf("%d",&s[i]);
sort(s+1,s+n+1);
while(s[1]!=s[n]){
int mind=0,maxd=0;
for(int i=1;i<=n;++i)
if(s[i]==s[1])
mind++;
for(int i=1;i<=n;++i)
if(s[i]==s[n])
maxd++;
int d=min(mind,maxd);
if(m<d) break;
if(d==mind)
for(int i=1;i<mind+1;++i)
s[i]++;
else if(d==maxd)
for(int i=n;i>n-maxd;--i)
s[i]--;
m-=d;
}
printf("%d\n",s[n]-s[1]);
}
return 0;
}千言的数论
Problem Description
千言最近喜欢上了数论。 然而数论实在太复杂了，他只能研究一些简单的问题。 这天，他在研究正整数因子个数的时候，想到了一个“快速迭代”算法。设f(x)为x的因子个数，将f迭代下去，千言猜想任意正整数最终都会变成2。 例如:f(12)=6,f(6)=4,f(4)=3,f(3)=2; 他希望你帮他验证一下。他会给你一个正整数n，让你输出它在迭代过程中，第一次迭代成x的迭代次数。Input
一个正整数n(3<=n<=10^12)Output
一个正整数，为n迭代至2的次数。Sample Input
12
Sample Output
4
说明：
12的因子：1，2，3，4，6，12。共6个。
6的因子：1，2，3，6。共4个。
4的因子：1，2，4。共3个。
3的因子：1，3。共2个。
12 → 6 → 4 → 3 → 2 ， 故迭代了4次。
标程
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long dcp(long long x){
long long i,ans = 1;
for(i = 2; i * i <= x; i++){
if(x % i == 0){
long long temp = 0;
while(x % i == 0){
x /= i;
temp++;
}
ans *= (temp+1);
}
}
if(x > 1) ans *= 2;
return ans;
}
int main(void){
long long n,count=0;
while(~scanf("%lld",&n)){
count=0;
while(n!=2){
n=dcp(n);
count++;
}
printf("%d\n",count);
}
return 0;
}hanhan学长的数组越位
Problem Description
hanhan学长写了这样一个C/C++程序：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[5][5];
a[-1][8]=12345;
printf("%d %d",a[1][-2],a[0][3]);
return 0;
}
他发现程序可以正常运行，并且输出为：
12345 12345
在C/C++中，这种数组越位行为是Undefined Behaviour(UB)的，也就是程序未定义行为，但是在hanhan的编译器呢，对于这种情况，二维数组的内存是连续的。
也就是说对于二维数组int a[5][5]，在牛牛的电脑中是按照a[0][0],a[0][1],a[0][2],a[0][3],a[0][4],a[1][0]...a[1][4],a[2][0]...a[2][4],a[3][0]...a[4][4]
这样储存的。
hanhan所使用的编译器在寻址时是这样处理的，对于一个二维数组a[n][m]，若对a[x][y]这个数组元素进行操作，最终访问到的地址为：a的首地址+m*x+y。
所以在寻址时，无论是a[-1][8]还是a[1][-2]最终在牛牛的电脑上使用该编译器编译出的程序均未发生非法访问的行为，他们最终都表示a[0][3]这个数组元素。
本题有T组测试数据。
hanhan先声明了一个n*m的int 型数组，即int a[n][m];，这个数组被他声明成一个全局变量，所以数组的初值全为0，接下来他要进行p次赋值运算。
每次他都选择一个二维下标x,y，并且把a[x][y]赋值成val。
当然，hanhan不会老老实实按照C语言的规范来写代码。
如果这p次赋值操作中不存在数组越位行为，则先输出n行，每行m个数。表示操作后的二维数组，数字之间用一个空格隔开，行末没有多余空格。然后输出一行"Accepted"（不含引号），表示正常运行。
如果这p次赋值操作中虽然存在数组越位行为但是没有发生非法访问，则先输出n行，每行m个数。表示操作后的二维数组，数字之间用一个空格隔开，行末没有多余空格。然后输出一行"Undefined Behaviour"（不含引号），表示虽然能够运行，但是hanhan的代码不规范存在隐患。
如果这p次赋值操作中出现了至少一次数组越位并且导致非法访问的行为，请输出一行一个字符串"Runtime error"（不含引号）。
Input
第一行是一个正整数T(1≤T≤1000)表示测试样例的组数且保证∑n×m≤2×10^7且∑p≤2×10^7
。对于每组案例：
第一行是三个正整数n,m,p((1≤n,m≤1000,0≤p≤10000)表示hanhan在全局中声明了一个int型的a数组，即int a[n][m];，接下来牛牛准备进行p次赋值操作。
接下来p行，每行三个整数x,y,val(−1000000≤x,y,val≤1000000)表示进行一次赋值操作，即a[x][y]=val;。
Output
如果这p次赋值操作中不存在数组越位行为，则先输出n行，每行m个数。表示操作后的二维数组，数字之间用一个空格隔开，行末没有多余空格。然后输出一行"Accepted"（不含引号），表示正常运行。
如果这p次赋值操作中虽然存在数组越位行为但是没有发生非法访问，则先输出n行，每行m个数。表示操作后的二维数组，数字之间用一个空格隔开，行末没有多余空格。然后输出一行"Undefined Behaviour"（不含引号），表示虽然能够运行，但是hanhan的代码不规范，存在隐患。
如果这p次赋值操作中出现了至少一次数组越位并且导致非法访问的行为，请输出一行一个字符串"Runtime error"（不含引号）。
Sample Input
4
2 4 8
-1 4 1
1 -3 2
2 -6 3
0 3 4
-1 8 5
-2 13 6
-100 406 7
100 -393 8
5 5 1
-1 8 1234
10 10 1
5 -51 1
1 1 1
0 0 7
Sample Output
1 2 3 4
5 6 7 8
Undefined Behaviour
0 0 0 1234 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Undefined Behaviour
Runtime error
7
Accepted
标程
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int T;
cin>>T;
while(T--)
{
int n,m,p,flag1,flag2,flag3;
cin>>n>>m>>p;
flag1=flag2=flag3=0;
int a[n][m];
memset(a,0,sizeof(a));
while(p--)
{
int x,y,val;
cin>>x>>y>>val;
if(n*m>(m*x+y)&&(m*x+y>=0))
a[x][y]=val;
if(m*x+y<0||m*x+y>=n*m)
flag1=1;
if(x<0||y<0||x>=n||y>=m)
flag2=1;
if(flag1||flag2)
flag3=1;
}
if(!flag1)
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<a[i][j];
if(j!=m-1)
cout<<" ";
}
cout<<endl;
}
if(flag1)
cout<<"Runtime error"<<endl;
if(!flag1&&flag2)
cout<<"Undefined Behaviour"<<endl;
if(!flag3)
cout<<"Accepted"<<endl;
}
return 0;
}
这个题目并不难，难点在于读题，就算对二维数组不够了解，在题目中也写到了。
</n>
查看21道真题和解析