当前位置: 代码迷 >> 综合 >> 杭电ACM基础题(2114、2115、2123、2131、2132、2133、2135、2136、2137、2138)
  详细解决方案

杭电ACM基础题(2114、2115、2123、2131、2132、2133、2135、2136、2137、2138)

热度:44   发布时间:2023-12-29 06:13:45.0

文章目录

    • 2114、Calculate S(n)
    • 2115、I Love This Game[利用结构排序]
    • 2123、An easy problem[输出n*n矩阵]
    • 2131、Probability
    • 2132、An easy problem[递归给出]
    • 2133、What day is it[计算给定日期是星期几]
    • 2135、Rolling table[对矩阵进行旋转]
    • 2136、Largest prime factor[最大素因数所在位置--素数筛法]
    • 2137、circumgyrate the string[将字符串进行旋转]
    • 2138、How many prime numbers[有多少个质数]

2114、Calculate S(n)

Calculate S(n).
S(n)=13+23 +33 +…+n3 .
Input
Each line will contain one integer N(1 < n < 1000000000). Process to end of file.
Output
For each case, output the last four dights of S(N) in one line.
Sample Input

1
2

Sample Output

0001
0009

Code:
方法一:会超时

//计算 S(n)=1^3+2^3 +3^3 +......+n^3,输出最后四位数
//此方法会超时
#include<iostream>
using namespace std;
int main(){
    int n;while(cin>>n){
    int sum=0;for(int i=1;i<=n;i++){
    sum+=i*i*i;sum=sum%10000;//输出最后四位数 }if(sum<10){
    cout<<"000"<<sum<<endl;}else if(sum<100){
    cout<<"00"<<sum<<endl;}else if(sum<1000){
    cout<<"0"<<sum<<endl;}else{
    cout<<sum<<endl;}}return 0; 
} 

方法二、
利用公式

//计算 S(n)=1^3+2^3 +3^3 +......+n^3,输出最后四位数
//立方和公式S(n)=(n*(n+1)/2)^2; 
#include<iostream>
using namespace std;
int main(){
    __int64 n;while(cin>>n){
    __int64 sum;//n也应为__int64类型sum=((n*(n+1)/2%10000)*(n*(n+1)/2%10000))%10000; if(sum<10){
    cout<<"000"<<sum<<endl;}else if(sum<100){
    cout<<"00"<<sum<<endl;}else if(sum<1000){
    cout<<"0"<<sum<<endl;}else{
    cout<<sum<<endl;}}return 0; 
} 

2115、I Love This Game[利用结构排序]

Do you like playing basketball ? If you are , you may know the NBA Skills Challenge . It is the content of the basketball skills . It include several parts , such as passing , shooting , and so on. After completion of the content , the player who takes the shortest time will be the winner . Now give you their names and the time of finishing the competition , your task is to give out the rank of them ; please output their name and the rank, if they have the same time , the rank of them will be the same ,but you should output their names in lexicographic order.You may assume the names of the players are unique.

Is it a very simple problem for you? Please accept it in ten minutes.
Input
This problem contains multiple test cases! Ease test case contain a n(1<=n<=10) shows the number of players,then n lines will be given. Each line will contain the name of player and the time(mm:ss) of their finish.The end of the input will be indicated by an integer value of zero.
Output
The output format is shown as sample below.
Please output the rank of all players, the output format is shown as sample below;
Output a blank line between two cases.
Sample Input

10
Iverson 17:19
Bryant 07:03
Nash 09:33
Wade 07:03
Davies 11:13
Carter 14:28
Jordan 29:34
James 20:48
Parker 24:49
Kidd 26:46
0

Sample Output

Case #1
Bryant 1
Wade 1
Nash 3
Davies 4
Carter 5
Iverson 6
James 7
Parker 8
Kidd 9
Jordan 10

Code

/* 题目:给出n名队员的名字和他们所用的时间,输出他们各自的等级 思路:利用结构体,将姓名和时间存储在结构体数组中,并对其按要求进行排序 */ 
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
struct player{
    char name[20];int time;
}play[10];bool comp(player p1,player p2){
    if(p1.time==p2.time){
    return strcmp(p1.name,p2.name)<0;  //strcmp()参数const char*,或者char* }else{
    return p1.time<p2.time;}
}int main(){
    int n,count=0;while(cin>>n){
    if(n==0) return 0;count++;char c[6];for(int i=0;i<n;i++){
    cin>>play[i].name>>c;play[i].time=((c[0]-'0')*10+(c[1]-'0'))*60+(c[3]-'0')*10+(c[4]-'0');}sort(play,play+n,comp);//输出 if(count==1)cout<<"Case #"<<count<<endl;else{
    cout<<endl;cout<<"Case #"<<count<<endl;}int rank;for(int i=0;i<n;i++){
    rank=i+1;if(i==0){
    cout<<play[i].name<<" "<<rank<<endl;}else if(play[i].time==play[i-1].time){
    rank=i;cout<<play[i].name<<" "<<rank<<endl;}else{
    cout<<play[i].name<<" "<<rank<<endl;}}}
} 

2123、An easy problem[输出n*n矩阵]

In this problem you need to make a multiply table of N * N ,just like the sample out. The element in the ith row and jth column should be the product(乘积) of i and j.
Input
The first line of input is an integer C which indicate the number of test cases.

Then C test cases follow.Each test case contains an integer N (1<=N<=9) in a line which mentioned above.
Output
For each test case, print out the multiply table.
Sample Input

2
1
4

Sample Output

1
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16

Code:

//输入n,输出n*n的矩阵,其中第i行第j列的元素值为i*j;
#include<iostream>
using namespace std;
int main(){
    int t,n,a[9][9];cin>>t;while(t--){
    cin>>n;for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    a[i][j]=(i+1)*(j+1);}}for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    if(j==0)cout<<a[i][j];elsecout<<" "<<a[i][j];}cout<<endl;}}return 0;
} 

2131、Probability

Mickey is interested in probability recently. One day , he played a game which is about probability with mini.First mickey gives a letter and a word to mini.Then mini calculate the probability that the letter appears in the word.For example,give you the letter “a” and the word “apple”. the probability of this case is 0.20000.
Input
The input contains several test cases. Each test case consists of a letter and a word.The length of the word is no longer than 200.
Output
For each test case, print the probability rounded to five digits after the decimal point.
Sample Input

a apple
c Candy
a banana

Sample Output

0.20000
0.20000
0.50000

Code:

//分析:事实上就是计算给定字符在给定单词中所占的比例,如'a' apple---0.20000
#include<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
int main(){
    char c,word[201];while(cin>>c>>word){
    int len=strlen(word);int num=0;for(int i=0;i<len;i++){
    if(word[i]==c||word[i]+32==c||c+32==word[i]){
    //大小写 num++;}}double prob=(double)num/(double)len;cout<<setiosflags(ios::fixed)<<setprecision(5)<<prob<<endl;}return 0;
}

2132、An easy problem[递归给出]

We once did a lot of recursional problem . I think some of them is easy for you and some if hard for you.
Now there is a very easy problem . I think you can AC it.
We can define sum(n) as follow:
if i can be divided exactly by 3 sum(i) = sum(i-1) + iii;else sum(i) = sum(i-1) + i;
Is it very easy ? Please begin to program to AC it…-_-
Input
The input file contains multilple cases.
Every cases contain only ont line, every line contains a integer n (n<=100000).
when n is a negative indicate the end of file.
Output
output the result sum(n).
Sample Input

1
2
3
-1

Sample Output

1
3
30

Code

/* 给出n,如果n能够被3整除,则sum(n)=sum(n-1)+n*n*n;否则,sum(n)=sum(n-1)+n; sum(0)=0; 思路:递归应该会超时 选用打表法 */ 
#include<iostream>
using namespace std;
__int64 num[100000]={
    0};
int main(){
    int n;for(__int64 i=1;i<=100000;i++){
    if(i%3==0){
    num[i]=num[i-1]+i*i*i;}else{
    num[i]=num[i-1]+i;}}while(cin>>n){
    if(n<0) return 0;cout<<num[n]<<endl;}return 0;
}

2133、What day is it[计算给定日期是星期几]

Today is Saturday, 17th Nov,2007. Now, if i tell you a date, can you tell me what day it is ?
Input
There are multiply cases.
One line is one case.
There are three integers, year(0<year<10000), month(0<=month<13), day(0<=day<32).
Output
Output one line.
if the date is illegal, you should output “illegal”. Or, you should output what day it is.
Sample Input

2007 11 17

Sample Output

Saturday

Code
注意细节

//给定某年某月某日,计算出该天是星期几
//公元元年(0000年)1月1日是星期1 
//思路:统计输入的年份距离公元元年经过了多少天,一周七天,除以7的余数即为周几 
#include<iostream>
using namespace std;//判断是闰年还是平年
int isLeap(int year){
    if((year%4==0&&year%100!=0)||year%400==0){
    return 1;}else{
    return 0;}
} int main(){
    int year,month,day;//闰年各个月份的天数 int m1[12]={
    31,29,31,30,31,30,31,31,30,31,30,31};//平年各个月份的天数 int m2[12]={
    31,28,31,30,31,30,31,31,30,31,30,31};while(cin>>year>>month>>day){
    //输入数据不合规范 if(year<=0||year>=10000||month<0||month>=13||day<0||day>=32){
    cout<<"illegal"<<endl;continue;}else if(month==0||day==0){
    cout<<"illegal"<<endl;continue;}//闰年2月不能有超过28天 else if(isLeap(year)==0&&month==2&&day==29||(isLeap(year)==0&&month==2&&day>29)){
    cout<<"illegal"<<endl;continue;} //4月6月9月11月都为30天 else if((month==4||month==6||month==9||month==11)&&day==31){
    cout<<"illegal"<<endl;continue;}//2月不超过29天 else if(month==2&&day>=30){
    cout<<"illegal"<<endl;continue;}                           int sum=0;if(isLeap(year)==0){
    for(int i=0;i<month-1;i++){
    sum=sum+m2[i];}sum=sum+day;}else if(isLeap(year)==1){
    for(int i=0;i<month-1;i++){
    sum=sum+m1[i];}sum=sum+day;}for(int i=1;i<year;i++){
    if(isLeap(i)==0){
    sum=sum+365;}else{
    sum=sum+366;}}char week[8][10]={
    "Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};cout<<week[sum%7]<<endl;}
} 

2135、Rolling table[对矩阵进行旋转]

After the 32nd ACM/ICPC regional contest, Wiskey is beginning to prepare for CET-6. He has an English words table and read it every morning.
One day, Wiskey’s chum wants to play a joke on him. He rolling the table, and tell Wiskey how many time he rotated. Rotate 90 degrees clockwise or count-clockwise each time.
The table has nn grids. Your task is tell Wiskey the final status of the table.
Input
Each line will contain two number.
The first is postive integer n (0 < n <= 10).
The seconed is signed 32-bit integer m.
if m is postive, it represent rotate clockwise m times, else it represent rotate count-clockwise -m times.
Following n lines. Every line contain n characters.
Output
Output the n
n grids of the final status.
Sample Input

3 2
123
456
789
3 -1
123
456
789

Sample Output

987
654
321
369
258
147

Code
题目:有n*n个矩阵格子,每行包括n个字符;如果m大于0表示顺时针转m次,如果m小于0表示逆时针转m次。
输入n和m以及最初格子中的值,输出旋转之后的状态。

/* 有n*n个矩阵格子,每行包括n个字符;如果m大于0表示顺时针转m次,如果m小于0表示逆时针转m次。 输入n和m以及最初格子中的值,输出旋转之后的状态。 思路:找每次旋转的规律 */ 
#include<iostream>
using namespace std;
int main(){
    int n,m;//n(0,10] m旋转次数char a[11][11],b[11][11];while(cin>>n>>m){
    //输入原始字符 for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    cin>>a[i][j];}}m=m%4;//顺时针旋转360或逆时针旋转360if(m==0){
    for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    cout<<a[i][j];}cout<<endl;}}//顺时针旋转90度或逆时针旋转270度 else if(m==1||m==-3){
    for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    b[i][j]=a[n-1-j][i];}}//输出for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    cout<<b[i][j];}cout<<endl;} }//顺时针旋转180度和逆时针旋转180度 else if(m==2||m==-2){
    for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    b[i][j]=a[n-1-i][n-1-j];}}for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    cout<<b[i][j];}cout<<endl;} }//顺时针旋转270度和逆时针旋转90度 else if(m==3||m==-1){
    for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    b[i][j]=a[j][n-1-i];}}for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    cout<<b[i][j];}cout<<endl;}  }} return 0;
} 

2136、Largest prime factor[最大素因数所在位置–素数筛法]

Everybody knows any number can be combined by the prime number.
Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.
Specially, LPF(1) = 0.
Input
Each line will contain one integer n(0 < n < 1000000).
Output
Output the LPF(n).
Sample Input

1
2
3
4
5

Sample Output

0
1
2
1
3

Code

/*给出一个数n,求n的最大素因数在素数表中的位置,n的范围为(0,1000000) 思路1:找出n的最大素因数,然后查找其在素数表中的位置,会导致超时 思路2:素数筛选法--声明一个数组,利用这个数组来表示对应的下标数字是不是素数 本题中,可以通过将将某一素数的倍数都赋值为该素数所在的位置,从而确定最大素因数所在位置 */
#include<iostream>
using namespace std;
int LPF[1000001]={
    0};
int main(){
    int n,position=0;LPF[1]=0;for(int i=2;i<=1000000;i++){
    if(LPF[i]==0){
    //i为素数 position++;for(int j=i;j<1000000;j+=i){
    LPF[j]=position;//将所有是i的倍数的整数, 数组的值暂时为position }}}while(scanf("%d",&n)!=EOF){
    printf("%d\n",LPF[n]);// cout<<LPF[n]<<endl;}return 0;
} 

2137、circumgyrate the string[将字符串进行旋转]

Give you a string, just circumgyrate. The number N means you just circumgyrate the string N times, and each time you circumgyrate the string for 45 degree anticlockwise.
Input
In each case there is string and a integer N. And the length of the string is always odd, so the center of the string will not be changed, and the string is always horizontal at the beginning. The length of the string will not exceed 80, so we can see the complete result on the screen.
Output
For each case, print the circumgrated string.
Sample Input

asdfass 7

Sample Output

asdfass

Code

/*将一个字符串围绕一个字符串的中心字符进行逆时针旋转N次,输出旋转之后的值 旋转之后的规律可通过画图看出 WA好多次: (1)注意n可以为负数 (2) 输出字符之后不再有空格 (3)用cin cout会超时,用scanf和printf */ 
#include<iostream>
#include<cstring>
using namespace std;
int main(){
    char a[100];int n;while(scanf("%s %d",a,&n)!=EOF){
    int len=strlen(a);//n为负数表示是顺时针旋转 if(n<0){
    n=n%8+8;} n=n%8;//逆时针旋转45度 if(n==1){
    for(int i=0;i<len;i++){
    for(int j=0;j<len-i-1;j++){
    printf(" ");}printf("%c\n",a[len-i-1]);}}//逆时针旋转90度 else if(n==2){
    for(int i=len-1;i>=0;i--){
    for(int j=0;j<len/2;j++){
    cout<<" ";} printf("%c\n",a[i]);}} //逆时针旋转135度else if(n==3){
    for(int i=0;i<len;i++){
    for(int k=0;k<i;k++){
    printf(" ");}printf("%c",a[len-i-1]);/* for(int j=0;j<len-1-i;j++){printf(" ");}*/printf("\n");} }//逆时针旋转180度else if(n==4){
    for(int i=len-1;i>=0;i--){
    printf("%c",a[i]);}printf("\n");}//逆时针旋转225度else if(n==5){
    for(int i=0;i<len;i++){
    for(int j=0;j<len-1-i;j++){
    printf(" ");}printf("%c",a[i]);/* for(int k=0;k<i;k++){printf(" ");}*/printf("\n");}} //逆时针旋转270度else if(n==6){
    for(int i=0;i<len;i++){
    for(int j=0;j<len/2;j++){
    cout<<" ";}        printf("%c\n",a[i]);}} //逆时针旋转315度else if(n==7){
    for(int i=0;i<len;i++){
    for(int k=0;k<i;k++){
                printf(" ");}        printf("%c",a[i]);/* for(int j=0;j<len-1-i;j++){ printf(" ");}*/printf("\n");}} //逆时针旋转360度else if(n==0){
    printf("%s\n",a);} }return 0;
} 

2138、How many prime numbers[有多少个质数]

Give you a lot of positive integers, just to find out how many prime numbers there are.
Input
There are a lot of cases. In each case, there is an integer N representing the number of integers to find. Each integer won’t exceed 32-bit signed integer, and each of them won’t be less than 2.
Output
For each case, print the number of prime numbers you have found out.
Sample Input

3
2 3 4

Sample Output

2

Code

//输入n个数字,统计这n个数字中有多少质数
#include<iostream>
#include<cmath>
using namespace std; //判断一个数是不是质数
bool isPrime(int a){
    int k=sqrt(a);for(int i=2;i<=k;i++){
    if(a%i==0)return false; }return true;
} 
int main(){
    __int64 n,a;while(cin>>n){
    __int64 count=0;for(int i=0;i<n;i++){
    cin>>a;if(isPrime(a)==true){
    count++;}}cout<<count<<endl;}return 0;
}