【算法积累】随便写写给大一布置的算法题 (Begin: 2020-12-06)

傷城~ 2022-12-27 07:40 119阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]

> 弱弱吐槽一下这周题目的名称起得真的是很随性……  
> 最后一题虽然叫“简单题”，但是一点都不简单！！！目前我是还没做出来T^T……

## A - 没错，又是我大数 ##

求两个大的正整数相减的差。

**输入格式**  
共  2 2 2 行，第  1 1 1 行是被减数  a a a ，第2行是减数  b b b  ( a > b ) (a>b) (a>b)。每个大整数不超过  200 200 200 位，不会有多余的前导零。

**输出格式**  
一行，即所求的差。

**Sample Input**

9999999999999999999999999999999999999
    9999999999999

**Sample Output**

9999999999999999999999990000000000000

--------------------

感觉这题没什么可说的，和上周做过的大整数加法原理类似，只不过加法需要考虑的是向前“进位”，减法需要考虑的是向前“借位”。  
语言：C

#include <stdio.h>
    #include <string.h>
    #define MAXSIZE 200
    
    int main(void) { 
        char a[MAXSIZE], b[MAXSIZE];
        int a_[MAXSIZE], b_[MAXSIZE];
        int ans[MAXSIZE];
        memset(a_, 0, sizeof(a_));
        memset(b_, 0, sizeof(b_));
        memset(ans, 0, sizeof(ans));
        gets(a);
        gets(b);
        int len_a = strlen(a);
        int len_b = strlen(b);
        int len_max = len_a > len_b ? len_a : len_b;
        int k = 0;
        for (int i = len_a - 1; i >= 0; i--) { 
            a_[k++] = a[i] - '0';
        }
        k = 0;
        for (int i = len_b - 1; i >= 0; i--) { 
            b_[k++] = b[i] - '0';
        }
        for (int i = 0; i < len_max; i++) { 
            if (a_[i] < b_[i]) { 
                a_[i] += 10;
                a_[i + 1] -= 1;
            }
            ans[i] = a_[i] - b_[i];
        }
        for (int i = 199; i >= 0; i--) { 
            if (ans[i] != 0) { 
                for (int j = i; j >= 0; j--) { 
                    printf("%d", ans[j]);
                }
                break;
            }
            if (i == 0) { 
                printf("0");
            }
        }
        printf("\n");
        return 0;
    }

## B - 水题 ##

花椰妹当上了某学校程序设计竞赛队的教练。现在她要将集训队内的  n n n 名学生两两组队。每位学生有一个能力值，只有能力值相同的两人才能组队。  
当然这些学生也可以通过做题来提升自己的能力值。每位学生每做一道题提升一点能力值。  
花椰妹想知道，这些学生最少还要做几道题才能都组上队。

**输入格式**  
输入的第一行包含一个整数  n n n  ( 2 ≤ n ≤ 100 ) (2≤n≤100) (2≤n≤100)，并且保证是偶数。  
输入的第二行包括  n n n 个整数，为每个学生的能力值  a i a\_\{i\} ai  ( 2 ≤ a i ≤ 100 ) (2≤a\_\{i\}≤100) (2≤ai≤100)。

**输出格式**  
输出只有一个整数——这些学生至少还要做多少道题。

**Sample Input**

6
    5 10 2 3 14 5

**Sample Output**

**Sample Input**

2
    1 100

**Sample Output**

--------------------

也是很简单的一道题，将数组整体排序之后，对数组下标范围为  1 1 1 到  n n n 的元素进行步长为  2 2 2 的遍历，将`a[i] - a[i - 1]`的值累加到结果变量`ans`中。这样，遍历结束后得到的结果即为最终结果。  
语言：C

#include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 100
    
    int cmp(const void* x, const void* y);
    
    int main(void) { 
        int n;
        int a[MAXSIZE];
        int ans = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) { 
            scanf("%d", &a[i]);
        }
        qsort(a, n, sizeof(a[0]), cmp);
        for (int i = 1; i < n; i += 2) { 
            ans += a[i] - a[i - 1];
        }
        printf("%d\n", ans);
        return 0;
    }
    
    int cmp(const void* x, const void* y) { 
        return * (int*)x - * (int*)y;
    }

## C - 淼题 ##

世界上有许多宗教，你感兴趣的是你学校里的同学信仰多少种宗教。你的学校有  n n n 名学生  ( 0 < n ≤ 50000 ) (0<n≤50000) (0<n≤50000)，你不太可能询问每个人的宗教信仰，因为他们不太愿意透露。但是当你同时找到  2 2 2 名学生，他们却愿意告诉你他们是否信仰同一宗教，你可以通过很多这样的询问估算学校里的宗教数目的上限。你可以认为每名学生只会信仰最多一种宗教。

**输入格式**  
输入包括多组数据。每组数据的第一行包括  n n n 和  m m m， 0 ≤ m ≤ n 0≤m≤n 0≤m≤n  ( n − 1 ) / 2 (n−1)/2 (n−1)/2，其后  m m m 行每行包括两个数字  i i i 和  j j j，表示学生  i i i 和学生  j j j 信仰同一宗教，学生被标号为  1 1 1 至  n n n。  
输入以一行  n = m = 0 n=m=0 n=m=0 作为结束。

**输出格式**  
对于每组数据，先输出它的编号（从  1 1 1 开始），接着输出学生信仰的不同宗教的数目上限。

**Sample Input**

10 9
    1 2
    1 3
    1 4
    1 5
    1 6
    1 7
    1 8
    1 9
    1 10
    10 4
    2 3
    4 5
    4 8
    5 8
    0 0

**Sample Output**

Case 1: 1
    Case 2: 7

--------------------

写这题算是复习了一下上周学过的并查集，不过我第一次提交还是WA了……  
语言：C

#include <stdio.h>
    #define MAXSIZE 50001
    
    int pre[MAXSIZE];
    int ans;
    
    int Find(int x);
    void Union(int x, int y);
    
    int main(void) { 
        int n, m;
        int Case = 0;
        while (++Case) { 
            scanf("%d %d", &n, &m);
            if (!n && !m) { 
                break;
            }
            ans = 0;
            for (int i = 1; i <= n; i++) { 
                pre[i] = i;
            }
            for (int i = 0; i < m; i++) { 
                int stu1, stu2;
                scanf("%d %d", &stu1, &stu2);
                Union(stu1, stu2);
            }
            for (int i = 1; i <= n; i++) { 
                if (pre[i] == i) { 
                    ans++;
                }
            }
            printf("Case %d: %d\n", Case, ans);
        }
        return 0;
    }
    
    int Find(int x) { 
        if (pre[x] != x) { 
            pre[x] = Find(pre[x]);
        }
        return pre[x];
    }
    
    void Union(int x, int y) { 
        int fx = Find(x);
        int fy = Find(y);
        if (fx != fy) { 
            pre[fx] = fy;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]: /images/20221120/bdace21a7beb4be6bdf640ddbbee0b93.png