Shuwen's blog

生活 & 学习

0%

团体程序设计天梯赛-练习集

发表于 更新于 分类于

链接：团体程序设计天梯赛-练习集

L1-006 连续因子

序列最长长度

因为n的取值范围：

image-20210319111256733

又因为最长序列为2×3×。。。n，也就是n的阶乘。

计算n的最长序列

发现13!>n最大值，12!<n的最大值，，，，又因为1不算，，，也就是2×3×…13也就是最长为12位。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//
// Created by YCNN on 2021-03-19.
//
#include <iostream>
#include <cmath>
using namespace std;
int main(){
    long long ans = 1;
    for (int i = 2; i <= 13 ; ++i) {
        ans *= i;
    }
    cout<<ans<<endl;

    long long pow2 = pow(2,31);
    cout<<pow2<<endl;
    return 0;
}
1
2
3
//结果
13!:6227020800
n的最大值:2147483648

思路

枚举所有的

  1. 首先长度最长为12，从12开始减（依次枚举所有长度len的乘积【从2开始，，，】）
  2. 判断能否被n整除，如果可以的话，因为是从最大开始，这次就是最大值。

int取值范围

最大值：2^31-1

所以本次，，，n可以取int，但是ans可能超过int最大值，所以需要long long

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n;
    cin>>n;
    long long ans;
    int max = sqrt(n);
    for (int len = 12; len >= 1 ; --len) {//最大长度为12，依次暴力所有的的长度情况
        for (int start = 2; start <= max; ++start) {
            ans = 1;
            for (int i = start; i < start + len; ++i) {
                ans *= i;
            }
            if(n % ans == 0){//如果是合法的
                cout<<len<<endl<<start;
                for (int j = start+1; j < start+len; ++j) {
                    cout<<"*"<<j;
                }
                return 0;
            }
        }
    }
    cout<<1<<endl<<n<<endl;//如果是质数，，，因为最大也只是sqrt(n)，所以上面出不来结果，，，就手动加上来
    return 0;
}

其实是比较简单的题，，，但是上次做的时候，没有时间，紧张，就没有认真看下去，结果，，，校赛就出了一道类似的，苦苦。

L1-007 念数字

涉及字符串，，，使用java比较easy，，，

主要就是用map来存储，输入直接用字符串，，，

java版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package exercise;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Ex_7 {
	public static void main(String[] args) {
		Map<Character,String> hashmap = new HashMap<>();
		hashmap.put('0', "ling");
		hashmap.put('1', "yi");
		hashmap.put('2', "er");
		hashmap.put('3', "san");
		hashmap.put('4', "si");
		hashmap.put('5', "wu");
		hashmap.put('6', "liu");
		hashmap.put('7', "qi");
		hashmap.put('8', "ba");
		hashmap.put('9', "jiu");
		
		
		Scanner scan = new Scanner(System.in);
		String s  = scan.next();
		char[] arr = s.toCharArray();
		if(s.length()==1) {
			System.out.println(hashmap.get(arr[0]));
			return ;
		}
		

		if(hashmap.containsKey(arr[0])) {
			System.out.print(hashmap.get(arr[0])+" ");
		}else {
			System.out.print("fu ");
		}
		String ans="";
		for (int i = 1; i < arr.length; i++) {
			if(hashmap.containsKey(arr[i])) {
				ans += hashmap.get(arr[i])+" ";
			}
		}
		ans = ans.substring(0,ans.length()-1);
		System.out.println(ans);
		
	}
}

c++版本

思路总体一样的

但看起来更简洁，，，如果会写的话，，，TAT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//
// Created by YCNN on 2021-03-19.
//

#include <iostream>
#include <map>
using namespace std;
int main() {
    map<char,string> mmap;
    mmap['-'] = "fu";
    mmap['0'] = "ling";
    mmap['1'] = "yi";
    mmap['2'] = "er";
    mmap['3'] = "san";
    mmap['4'] = "si";
    mmap['5'] = "wu";
    mmap['6'] = "liu";
    mmap['7'] = "qi";
    mmap['8'] = "ba";
    mmap['9'] = "jiu";

    string s ;
    cin>>s;
    int i;
    for ( i = 0; i < s.length()-1; ++i) {
        cout<<mmap[s[i]]<<" ";
    }
    cout<<mmap[s[i]];

    return 0;
}

L1-008 求整数段和

easy

每个数字占5个字符宽度

使用格式化字符串 => 快乐

1
printf("%5d",i);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//
// Created by YCNN on 2021-03-19.
//


#include <iostream>
using  namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    int sum = 0;
    int len;
    for (int i = a,len=1; i <= b ; ++i,len++) {
        printf("%5d",i);
        sum += i;
        if(len % 5 ==0){
            cout<<endl;
            len = 0;
        }
    }
    if((b-a+1)%5==0){
        cout<<"Sum = "<<sum<<endl;
    } else{
        cout<<"\nSum = "<<sum<<endl;
    }

    return 0;
}

L1-009 N个数求和

首先计算分数加法公式：

img

然后计算结果分子分母的最大公约数，然后相除，得到最简分数

这里需要考虑的地方：

  1. 分母小于0 => 把符号换到分子上去
  2. 分子小于0，说明为0，为了方便后期的计算，将分母置为0，防止该数的影响

最后，根据能否整除，输出不同的结果。

scanf输入

这里使用scanf输入，，因为知道两个数字中间一定有一个/，可以简化，，，不用特意接受字符’/‘

最大公约数

固定格式：

1
2
3
4
//求最大公约数
int gcd(int a,int b){
    return b == 0 ? a : gcd(b,a % b);
}

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
//求最大公约数
int gcd(int a,int b){
    return b == 0 ? a : gcd(b,a % b);
}
void beauty(int &a1,int &b1){
    if(b1 < 0){
        a1 = -a1;
        b1 = -b1;
    }else if(a1 == 0){
        b1 = 1;
    }else{
        int simple = gcd(abs(a1),abs(b1));
        a1 /= simple;
        b1 /= simple;
    }
}
int main() {
    int n;
    cin>>n;
    int a1,b1,a2,b2;
    scanf("%d/%d",&a1,&b1);
    for (int i = 0; i < n-1; ++i) {
        scanf("%d/%d",&a2,&b2);
        a1 = a1 * b2 + a2 * b1;
        b1 = b1 * b2;
        beauty(a1,b1);
    }
    beauty(a1,b1);//如果只有一个式子，不会进入循环，，，但是输入可能不是最简的
    if(b1 == 1){
        cout<<a1<<endl;
    }else if(a1 < b1){
        cout<<a1<<"/"<<b1<<endl;
    }else{
        cout<<a1/b1<<" "<<a1 % b1<<"/"<<b1<<endl;
    }
    return 0;
}

L1-010 比较大小

只是对三个数排序，，，非常简单

sort

头文件

1
#include <algorithm>

使用

1
sort(arr,arr+3);//arr是数组名，3是arr的长度

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//
// Created by YCNN on 2021-03-19.
//

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int arr[3];
    cin>>arr[0]>>arr[1]>>arr[2];
    sort(arr,arr+3);
    cout<<arr[0]<<"->"<<arr[1]<<"->"<<arr[2]<<endl;

    return 0;
}

L1-011 A-B

本来是用eclipse的replace做的，但是超时了，，，555

image-20210319201138492

正确的思路：

遍历第二个字符串，用长度为256（ascii表长度）的数组记录又那些出现过的字符，最后再对第一个字符串遍历，根据数组是否出现过，，，。这里数组的存储的index就是字符串的ascii码【这点比较interesting】

c++输入一行

1
getline(cin,a);

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//
// Created by YCNN on 2021-03-19.
//

#include <iostream>
#include <string>
using namespace std;
int main() {
    string a,b;
    int mark[256];
    getline(cin,a);
    getline(cin,b);
    for (int i = 0; i < b.length() ; ++i) {
        mark[b[i]] = 1;//直接将字符串的ascii码作为数组下表
    }
    for (int j = 0; j < a.length() ; ++j) {
        if(mark[a[j]] == 1){
            continue;
        }else{
            cout<<a[j];
        }
    }
    return 0;
}

L1-012 计算指数

pow（底数，幂次）的结果是double型的，，，，不知道为什么不能强转到int，，，

就输出是f了

1
2
3
4
5
6
7
8
9
10
11
12
13
//
// Created by YCNN on 2021-03-19.
//
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n;
    cin>>n;
    printf("2^%d = %.f",n,pow(2,n));

    return 0;
}
Q：如果阅读本文需要付费，你是否愿意为此支付1元？