【算法积累】本周VJ的大一算法题 (Begin: 2020-12-21)

淡淡的烟草味﹌ 2022-12-29 14:08 94阅读 0赞

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

> 其实这周的题还算比较简单，果然，如果叫“简单题”的题都不简单的话，叫“难题”的题也都不难嘛。

## A - 难 ##

有一口深度为  h i g h high high 米的水井，井底有一只青蛙，它每天白天能够沿井壁向上爬  u p up up 米，夜里则顺井壁向下滑  d o w n down down 米，若青蛙从某个早晨开始向外爬，对于任意指定的  h i g h high high、 u p up up 和  d o w n down down 值（均为自然数），计算青蛙多少天能够爬出井口？

**输入格式**  
输入  3 3 3 个正整数： h i g h high high、 u p up up 和  d o w n down down。

**输出格式**  
输出一个整数，表示天数。输出单独占一行。

**注意**：不能简单地认为每天上升的高度等于白天向上爬的距离减去夜间下滑的距离，因为若白天能爬出井口，则不必等到晚上。

**数据范围**  
 1 ≤ d o w n < u p < h i g h ≤ 1000 1≤down<up<high≤1000 1≤down<up<high≤1000

**Sample Input**

10 2 1

**Sample Output**

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

**解法**：模拟过程  
语言：C

#include <stdio.h>
    
    int main(void) { 
        int high, up, down;
        int day = 0;
        int cur = 0;
        scanf("%d%d%d", &high, &up, &down);
        while (cur < high) { 
            day++;
            cur += up;
            if (cur >= high) { 
                break;
            }
            cur -= down;
        }
        printf("%d\n", day);
        return 0;
    }

## B - 很难 ##

蒜头君手上有个长度为  n n n 的数组  A A A。由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问整数  x x x 是否在数组  A A A 中。

**输入格式**  
第一行输入两个整数  n n n 和  m m m，分别表示数组的长度和查询的次数。  
接下来一行有  n n n 个整数  a i a\_\{i\} ai。  
接下来  m m m 行，每行有  1 1 1 个整数  x x x，表示蒜头君询问的整数。

**输出格式**  
对于每次查询，如果可以找到，输出`YES`，否则输出`NO`。

**数据范围**  
 1 ≤ n , m ≤ 1 0 5 , 0 ≤ x ≤ 1 0 6 1≤n,m≤10^\{5\},0≤x≤10^\{6\} 1≤n,m≤105,0≤x≤106

**Sample Input**

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

**Sample Output**

NO
    YES
    NO
    YES
    NO

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

**解法1**：快速排序+二分查找  
语言：C

#include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 100000
    
    int cmp(const void* a, const void* b);
    int BinarySearch(int* nums, int numsSize, int x);
    
    int main(void) { 
        int n, m, x;
        int a[MAXSIZE];
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) { 
            scanf("%d", &a[i]);
        }
        qsort(a, n, sizeof(a[0]), cmp);
        for (int i = 0; i < m; i++) { 
            scanf("%d", &x);
            if (BinarySearch(a, n, x)) { 
                printf("YES\n");
            } else { 
                printf("NO\n");
            }
        }
        return 0;
    }
    
    int cmp(const void* a, const void* b) { 
        return * (int*)a - * (int*)b;
    }
    
    int BinarySearch(int* nums, int numsSize, int x) { 
        int left = 0;
        int right = numsSize - 1;
        while (left <= right) { 
            int mid = (left + right) / 2;
            if (nums[mid] == x) { 
                return 1;
            } else if (nums[mid] > x) { 
                right = mid - 1;
            } else { 
                left = mid + 1;
            }
        }
        return 0;
    }

**解法2**：散列  
语言：C

#include <stdio.h>
    #define MAXSIZE 1000000
    
    int nums[MAXSIZE];
    
    int main(void) { 
        int n, m, a, x;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) { 
            scanf("%d", &a);
            nums[a]++;
        }
        for (int i = 0; i < m; i++) { 
            scanf("%d", &x);
            if (nums[x] != 0) { 
                printf("YES\n");
            } else { 
                printf("NO\n");
            }
        }
        return 0;
    }

## C - 巨难 ##

蒜头君最近被要求参加一个数字游戏，要求他把看到的一系列整数（长度不一定，以  0 0 0 结束，最多不超过  100 100 100 个），记住了然后反着念出来（表示结束的数字  0 0 0 就不要念出来了）。  
这对蒜头君的那点记忆力来说实在是太难了，所以请你帮他编程解决这个问题。

**输入格式**  
一行内输入一系列整数（大小在  \[ 1 , 1 0 9 \] \[1,10^\{9\}\] \[1,109\] 之内），以  0 0 0 结束，用空格来分隔。

**输出格式**  
一行内倒着输出这一系列整数，以空格间隔。

**Sample Input**

3 5 7 1 11 111 999 0

**Sample Output**

999 111 11 1 7 5 3

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

**解法1**：单链表头插法  
语言：C

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node { 
        int data;
        struct node* next;
    } LNode, * LinkList;
    
    LinkList Create(void);
    
    int main(void) { 
        LinkList nums = Create();
        LinkList p = nums->next;
        while (p) { 
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
        return 0;
    }
    
    LinkList Create(void) { 
        LinkList head = (LinkList)malloc(sizeof(LNode));
        head->next = NULL;
        LNode* s;
        int num;
        scanf("%d", &num);
        while (num != 0) { 
            s = (LinkList)malloc(sizeof(LNode));
            s->data = num;
            s->next = head->next;
            head->next = s;
            scanf("%d", &num);
        }
        return head;
    }

**解法2**：数组  
语言：C

#include <stdio.h>
    #define MAXSIZE 100
    
    int main(void) { 
        int nums[MAXSIZE];
        int i = 0;
        int num;
        while (scanf("%d", &num) == 1 && num != 0) { 
            nums[i] = num;
            i++;
        }
        for (int j = i - 1; j >= 0; j--) { 
            printf("%d ", nums[j]);
        }
        printf("\n");
        return 0;
    }

## D - 超级无敌难 ##

在蒜国里流行着一种游戏。  
游戏规则为：在一堆球中，每个球上都有一个整数编号  i ( 0 ≤ i ≤ 1 0 9 ) i (0≤i≤10^\{9\}) i(0≤i≤109)，编号可重复，现在说一个随机整数  k ( 0 ≤ k ≤ 1 0 9 + 100 ) k (0≤k≤10^\{9\}+100) k(0≤k≤109\+100)，判断编号为  k k k 的球是否在这堆球中（存在为`YES`，否则为`NO`），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。

**输入格式**  
第一行有两个整数  m , n ( 0 ≤ m ≤ 1 0 6 , 0 ≤ n ≤ 1 0 6 ) m,n(0≤m≤10^\{6\},0≤n≤10^\{6\}) m,n(0≤m≤106,0≤n≤106)；  
 m m m 表示这堆球里有  m m m 个球， n n n 表示这个游戏进行  n n n 次。  
接下来输入  m + n m+n m\+n 个整数，前  m m m 个分别表示这  m m m 个球的编号  i i i，后  n n n 个分别表示每次游戏中的随机整数  k k k。

**输出格式**  
输出`YES`或`NO`。

**Sample Input**

6 4
    23 34 46 768 343 343
    2 4 23 343

**Sample Output**

NO
    NO
    YES
    YES

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

**解法**：快速排序+二分查找  
语言：C

#include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 1000100
    
    int numbers[MAXSIZE];
    int k[MAXSIZE];
    
    int cmp(const void* a, const void* b);
    
    int main(void) { 
        int m, n;
        scanf("%d%d", &m, &n);
        for (int i = 0; i < m; i++) { 
            scanf("%d", &numbers[i]);
        }
        qsort(numbers, m, sizeof(numbers[0]), cmp);
        for (int i = 0; i < n; i++) { 
            scanf("%d", &k[i]);
            int left = 0, right = m;
            int mid;
            int flag = 0;
            while (left <= right) { 
                mid = left + (right - left) / 2;
                if (numbers[mid] == k[i]) { 
                    flag = 1;
                    break;
                } else if (numbers[mid] > k[i]) { 
                    right = mid - 1;
                } else { 
                    left = mid + 1;
                }
            }
            printf("%s\n", flag ? "YES" : "NO");
        }
        return 0;
    }
    
    int cmp(const void* a, const void* b) { 
        return * (int*)a - * (int*)b;
    }

语言：C++

#include <bits/stdc++.h>
    #define MAXSIZE 1000005
    using namespace std;
    
    int numbers[MAXSIZE];
    int k[MAXSIZE];
    
    int main(void) { 
        int m, n;
        scanf("%d%d", &m, &n);
        for (int i = 0; i < m; i++) { 
            scanf("%d", &numbers[i]);
        }
        sort(numbers, numbers + m);
        for (int i = 0; i < n; i++) { 
            scanf("%d", &k[i]);
            int left = 0, right = m;
            int mid;
            bool flag = false;
            while (left <= right) { 
                mid = left + (right - left) / 2;
                if (numbers[mid] == k[i]) { 
                    flag = true;
                    break;
                } else if (numbers[mid] > k[i]) { 
                    right = mid - 1;
                } else { 
                    left = mid + 1;
                }
            }
            printf("%s\n", flag ? "YES" : "NO");
        }
        return 0;
    }

> 这道题用散列会内存超限 (MLE)。

## E - 英语阅读A ##

Alice, a student of grade 6, is thinking about an Olympian Math problem, but she feels so despair that she cries. And her classmate, Bob, has no idea about the problem. Thus he wants you to help him. The problem is:  
We denote  k ! k! k!:  
 k ! = 1 × 2 × ⋯ × ( k − 1 ) × k k!=1×2×⋯×(k−1)×k k!=1×2×⋯×(k−1)×k  
We denote  S S S:  
 S = 1 × 1 ! + 2 × 2 ! + ⋯ + ( n − 1 ) × ( n − 1 ) ! S=1×1!+2×2!+⋯+(n−1)×(n−1)! S=1×1!\+2×2!\+⋯\+(n−1)×(n−1)!  
Then  S S S modulo  n n n is \_\_\_\_\_\_\_\_\_\_  
You are given an integer  n n n.  
You have to calculate  S S S modulo  n n n.

**Input**  
The first line contains an integer  T ( T ≤ 1000 ) T (T≤1000) T(T≤1000), denoting the number of test cases.  
For each test case, there is a line which has an integer  n n n.  
It is guaranteed that  2 ≤ n ≤ 1 0 18 2≤n≤10^\{18\} 2≤n≤1018.

**Output**  
For each test case, print an integer  S S S modulo  n n n.

**Hint**  
The first test is:  S = 1 × 1 ! = 1 S=1×1!=1 S=1×1!=1, and  1 1 1 modulo  2 2 2 is  1 1 1.  
The second test is:  S = 1 × 1 ! + 2 × 2 ! = 5 S=1×1!+2×2!=5 S=1×1!\+2×2!=5, and  5 5 5 modulo  3 3 3 is  2 2 2.

**Sample Input**

2
    2
    3

**Sample Output**

1
    2

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

**解法**：数学  
由 S = 1 × 1 ! + 2 × 2 ! + ⋯ + ( n − 1 ) × ( n − 1 ) ! S=1×1!+2×2!+⋯+(n−1)×(n−1)! S=1×1!\+2×2!\+⋯\+(n−1)×(n−1)!可得  
 S = 2 ! − 1 ! + 3 ! − 2 ! + . . . + n ! − ( n − 1 ) ! S=2!-1!+3!-2!+...+n!-(n-1)! S=2!−1!\+3!−2!\+...\+n!−(n−1)!化简得 S = n ! − 1 S=n!-1 S=n!−1容易看出 S m o d    n = n − 1 S \\mod n=n-1 Smodn=n−1  
语言：C

#include <stdio.h>
    
    int main(void) { 
        int T;
        scanf("%d", &T);
        for (int i = 0; i < T; i++) { 
            long long int n;
            scanf("%lld", &n);
            printf("%lld\n", n - 1);
        }
        return 0;
    }

## F - 英语阅读B ##

Bob is a sorcerer. He lives in a cuboid room which has a length of  A A A, a width of  B B B and a height of  C C C, so we represent it as  A A A \*  B B B \*  C C C. One day, he finds that his room is filled with unknown dark energy. Bob wants to neutralize all the dark energy in his room with his light magic. He can summon a  1 1 1 \*  1 1 1 \*  2 2 2 cuboid at a time to neutralize dark energy. But the cuboid must be totally in dark energy to take effect. Can you foresee whether Bob can save his room or not?

**Input**  
Input has  T T T test cases.  T ≤ 100 T≤100 T≤100.  
For each line, there are three integers  A , B , C A,B,C A,B,C.  
 1 ≤ A , B , C ≤ 100 1≤A,B,C≤100 1≤A,B,C≤100

**Output**  
For each test case, if Bob can save his room, print `Yes`, otherwise print `No`.

**Sample Input**

1 1 2
    1 1 4 
    1 1 1

**Sample Output**

Yes
    Yes
    No

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

**解法**：判断 A A A \*  B B B \*  C C C的奇偶性  
语言：C

#include <stdio.h>
    
    int main(void) { 
        int A, B, C;
        while (scanf("%d%d%d", &A, &B, &C) != EOF) { 
            if (A * B * C % 2) { 
                printf("No\n");
            } else { 
                printf("Yes\n");
            }
        }
        return 0;
    }

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