XTU oj 作业05题解

字数统计: 2.1k字   |   阅读时长≈ 10分

XTU-oj-作业05

恭喜各位马上就能解锁较高难度oj题（手动狗头）

怀着紧张刺激的心情，我们开始本周的题解

A 平方数

这道题的解题思路比较简单，模拟一下寻找的过程就好，比如说集合A={2，3，4}，则只有4=2*2，也就是我们需要一个一个元素的试，从第一个元素‘2’开始，2×2 与 2 相比，然后2×2与3相比、2×2与4相比，找出相等的数量；然后第二个元素3…

代码注释里面有注意事项

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 <stdio.h>

int main(){

    __int64 a[1111];
    int n;
    while (scanf("%d", &n) != EOF && n != 0){
        for (int i = 0; i < n; i ++){
            scanf("%u", a+i);
        }
        int sum = 0;
        for (int i = 0; i < n; i ++){
            for (int j = 0; j < n; j ++){
                if (a[j] == a[i]*a[i])
                    sum ++;
            }
        }
        printf("%d\n", sum);
    }

    return 0;
}

B 整数分类

观察题目中的要求，发现是10^500，不用想，一般的定义肯定达不到这种要求，所以我们用数组存放。

代码注释里面有注意事项

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
/*
注意：sum可能需要多次求，比如：输入十进制61位的9，第一次sum = 549，第二次是18，还需要继续第三次9，故有了 （1）的循环条件
*/

# include <stdio.h>

int main(){
    char a[501];
    while(scanf("%s",a)){

        if(a[0]=='0')break;

        int sum=0;

        for( int i=0; a[i]!='\0'; i++){
            sum=sum+a[i]-'0';
        }

        while(sum>9){           // （1）
			int n = 0;
			while (sum){
				n += (sum % 10);
				sum /= 10;
			}
			sum = n;
        }

        printf("%d\n",sum);
    }
    return 0;
}

C 组合数

这道题有同学可能会想到的是运用Cn,m的公式去计算，如果没猜错的话，会超时。所以这边建议用杨辉三角的解题思路

1
2
3
4
5
6
7
1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
* * * * * *

观察可发现：（1）第一列和对角线上的元素都为1；
（2）除第一列和对角线上的元素之外，其他的元素的值均为前一行上的同列元素和前一列元素之和。

并且第n行就是：2^n的展开的数字（应该是中学的知识点，不再过多介绍）

所以我们根据杨辉三角去写代码，就可以避免计算Cn,m的时间

像这种将数据提前准备好，储存起来的思路叫做“打表”，这种方法会大大减小时间的使用，之后还会经常见到。

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
#include <stdio.h>
#include <string.h>

int main(){
	/* 计算杨辉三角 */
    int C[50][100];
    for ( int i = 0; i < 50; i ++){
        C[i][0] = 1;
        C[i][i] = 1;
    }
    for ( int i = 0; i < 34; i ++)
        for ( int j = 1; j < i; j ++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];

	/* 输入输出 */
    int n;
    while (scanf("%d", &n), n >= 0){

        printf("2^%d=",n);
        for ( int i = 0; i <= n; i ++ ){
            printf("%d", C[n][i]);
            if ( i != n)
                printf("+");
        }

        printf("\n");

    }

    return 0;
}

D 排序

这道题目考查对排序的理解，比较简单的有选择排序和冒泡排序这里推荐看一下这个博客八大排序算法（C语言实现）_2021dragon的博客-CSDN博客

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
47
48
49
#include <stdio.h>
#include <string.h>

int main(){

    int B[1111];

    int K;
    scanf("%d", &K);
    while ( K -- ){
        int N;
        scanf("%d", &N);

        char A;
        scanf(" %c\n", &A);

        for ( int i = 0; i < N; i ++)
            scanf("%d", B+i);

        /*排序操作*/
	    for (int i = 0; i < N; i ++){
	        for (int j = 0; j < N; j ++){
	            if (B[i] > B[j]){
	                int t = B[i];
	                B[i] = B[j];
	                B[j] = t;
	            }
	        }
	    }

	    /*输出操作*/
        if (A == 'D')
            for (int i = 0; i < N; i ++){
                printf("%d", B[i]);
                if (i != N-1)
                    printf(" ");
            }

        else 
            for (int i = N -1; i >= 0; i --){
                printf("%d", B[i]);
                if (i != 0)
                    printf(" ");
            }
        printf("\n");
    }

    return 0;
}

E 素数个数

看到这道题，正常思路，输入n,m那就从n~m这个范围一个一个数字的试看看这个数字k（n<=k<=m）是否是素数，如果是那么就计一个。这种思路我们分析一下，在(n,m)区间有m-n+1个数字，每个数字k计算是否是素数需要计算根号k次，那么就有Σk^1/2次，是非常消耗时间的，那如何减少时间复杂度。

这里介绍一个算法：（挨筛，也叫素数表法）关于素数计算的算法总结 | DotedWood’s blog

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
# include<stdio.h>
# define N 1000011


int t[N]={1,1}; // 标记是否是素数，0表示是素数，1表示不是素数
int g[N];  // 记录从0~i的素数个数

int main(){
    
    /*开始挨筛*/
    for(int i=2; i<1000; i++){
        if(!t[i]){
            for(int j=i*i; j<N; j=j+i){
                t[j]=1;
            }
        }
    }
    /*计算*/
    for(int i=2; i<N; i++){
        g[i]=g[i-1]+!t[i];
    }
    
    int a,b;
    int K;
    scanf("%d",&K);
    while(K>0){
        K--;
        scanf("%d%d",&a,&b);
        int h;
        if(a>b)
        {
            h=a;
            a=b;
            b=h;
        }
        printf("%d\n",g[b]-g[a-1]);
    }
    
    return 0;
}

F 日期

（小声bb：这道题，课本里面有一个相似的例题，有代码，看不懂的可以去看一眼课本）

根据我们的生活常识，每年的天数是不一样的，闰年：366天；平年：365天。这种区别与2月份的息息相关。

所以计算日期的时候就不得不考虑闰年和平年的区别了，闰年的计算：非整百年：能被4整除的为闰年。（如2004年就是闰年,2001年不是闰年）；整百年：能被400整除的是闰年。(如2000年是闰年，1900年不是闰年)

——科普结束

思路：将输入的当年当月份之前的所有天数（不包括输入的月份）相加，然后加上当月份的号。

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
# include <stdio.h>

int main(){
    int year,month,day;
    int m;
    int K;

    scanf("%d",&K);

    while(K>0){
        K--;
        int a[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}}; // 储存每个月份的天数（二维数组）

        scanf("%d-%d-%d",&year,&month,&day);
		
        // 判断是否是闰年，是m = 1；不是m = 0；
        if((year%4==0&&year%100!=0)||(year%400==0)){
            m=1;
        }
        else m=0;

        int alldays=0;
		// 将当月之前的所有天数相加
        for(int j=0; j<month-1; j++)
            alldays=alldays+a[m][j];
		// 加上当月的号
        alldays=alldays+day;
        
        printf("%d\n",alldays);
    }
    return 0;
}

G 三角形

代码注释里面有注意事项

这道题的思路就是找规律：

1
2
3
4
5
1   2   3   4   5
3   5   7   9
8  12   16
20  28
48

我们可以发现，从第二行开始，每一列的数都是她上一行和上一行右边一列之和，根据这个规律我们很轻松就能得到代码：

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
/*
注意：为防止溢出，每次都要%2013
*/

# include <stdio.h>

int main(){

    int N;
    int a[101][101]={0};

    while(scanf("%d",&N), N != 0){

        for(int i=0; i<N; i++){
            int n;
            scanf("%d",&n);
            a[0][i]=n;
        }

        for(int i=1; i<=N; i++){
            for(int j=0; j<N-i; j++){
                a[i][j]=(a[i-1][j]+a[i-1][j+1])%2013;
            }
        }

        int m=a[N-1][0]%2013;
        printf("%d\n",m);
    }

    return 0;
}

H 湘潭大学

思路：找出分别有多少个’X’,’T’,’U’，根据“短板效应”，能组成多少个XTU和’X’,’T’,’U’三个里面最少的个数的那一个。所以输出个数最少的个数，就是最终答案

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
# include <stdio.h>

int min(int x, int y, int z){
    int t;
    if( x>y ){
        t=y;
    }
    else{
        t=x;
    }
    if( t>z ){
        t=z;
    }
    else{
        t=t;
    }
    return t;
}

int main(){
    char a[1000];
    int K;
    scanf("%d",&K);
    int x1,x2,x3;
    while(K>0){
        K--;
        scanf("%s",a);
        x1=0;
        x2=0;
        x3=0;
        for( int i=0; a[i]!='\0'; i++){
            if(a[i]=='X'){
                x1++;
            }
            else if(a[i]=='T'){
                x2++;
            }
            else if(a[i]=='U'){
                x3++;
            }
        }
        printf("%d\n",min(x1,x2,x3));
    }
    return 0;
}

同学们，距离oj截至还有快两个月时间，一定要自己规划好计划！！！争取在截至之前刷完

革命尚未成功，同志仍需努力！

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

XTU 计算机小白一个
不定期在博客分享自己的学习笔记
如有不足，请各位大佬批评谅解