《算法笔记》3.1小节——入门模拟->简单模拟

本节内容为较为简单的模拟题，没有涉及很多的算法，较为简单。题目怎么说，代码就怎么写。完全根据题目的描述来编代码。所以有时候阅读理解能力也很重要，入门模拟题完全考代码能力。

等我有空把 JAVA 代码补上。

问题 A: 剩下的树

题目

题目描述

有一个长度为整数 L（ 1 <= L <= 10000 ）的马路，可以想象成数轴上长度为 L 的一个线段，起点是坐标原点，在每个整数坐标点有一棵树，即在 0，1，2，…，L 共 L+1 个位置上有 L+1 棵树。
现在要移走一些树，移走的树的区间用一对数字表示，如 100 200 表示移走从 100 到 200 之间（包括端点）所有的树。
可能有 M（1 <= M <= 100）个区间，区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。

输入

两个整数 L（1 <= L <= 10000）和 M（ 1<= M <= 100）。
接下来有 M 组整数，每组有一对数字。

输出

可能有多组输入数据，对于每组输入数据，输出一个数，表示移走所有区间的树之后剩下的树的个数。

样例输入

4 2
1 2
0 2
11 2
1 5
4 7
0 0

样例输出

2
5

题解

思路

一开始没看懂题目，其实是未指定输入的数量，但是输入0 0作为结束。

分析题目，输入多次l m，每次的输入中：

• 树的个数l + 1，用数组tree[l + 1]表示，并且初始化为1（有树为1，没有为0）
• 根据输入的区间将相应的位置设置为0（tree[start]-tree[end]包含边界）
• 统计剩余树的个数（1的个数）

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    int l, m;
    // 读入每次的 l, m
    while (scanf("%d %d", &l, &m) != EOF)
    {
        if (l == 0 && m == 0)
            break;
        int *tree_num = new int[l + 1];
        // 赋初值为 1
        // fill(first, last, value);
        fill(tree_num, tree_num + l + 1, 1);
        int start, end;
        // 有树：1  无树：0
        while (m--)
        {
            scanf("%d %d", &start, &end);
            for (int i = start; i <= end; i++)
            {
                tree_num[i] = 0;
            }
        }
        // 计算剩余树的个数（ 1 的个数）
        int trees = 0;
        for (int i = 0; i <= l + 1; i++)
        {
            if (tree_num[i] == 1)
            {
                trees++;
            }
        }
        printf("%d\n", trees);
    }

    system("pause");
    return 0;
}

问题 B: A+B

题目

题目描述

给定两个整数 A 和 B，其表示形式是：从个位开始，每三位数用逗号 “,” 隔开。
现在请计算 A+B 的结果，并以正常形式输出。

输入

输入包含多组数据数据，每组数据占一行，由两个整数A和B组成（ $-10^9<A,B<10^9$ ）。

输出

请计算 A+B 的结果，并以正常形式输出，每组数据占一行。

样例输入

-234,567,890 123,456,789
1,234 2,345,678

样例输出

-111111101
2346912

题解

思路

这题纠结了很久啊，在思考哪个方案更好（字符串形式读入还是以多个整数读入），其实不用想那么多，想到的方法就是最好的方法。那么：

• 以字符数组的形式读取，需要将字符数组转换为long long整型。
• 输出结果。

未通过的一点Output Limit Exceeded: 输出超过限制，你的输出比正确答案长了两倍.，因为while()循环的条件写成了scanf("%s %s", A, B)没有判断!=EOF，实在是大忌。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

// char[] 数组转化为 long long 整型
void sToNum(char s[], long long &n)
{
    // r为阶数
    int i = strlen(s), r = 0;
    while (i >= 0)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            n += (s[i] - '0') * pow(10, r++);
        }
        i--;
    }
    // 判断负数
    if (s[0] == '-')
    {
        n = -n;
    }
}

int main()
{
    char A[15], B[15];
    while (scanf("%s %s", A, B) != EOF)
    {
        long long nA = 0, nB = 0;
        sToNum(A, nA), sToNum(B, nB);
        printf("%lld\n", nA + nB);
    }

    system("pause");
    return 0;
}

问题 C: 特殊乘法

题目

题目描述

写个算法，对 2 个小于 1000000000 的输入，求结果。特殊乘法举例：123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5

输入

两个小于 1000000000 的数

输出

输入可能有多组数据，对于每一组数据，输出 Input 中的两个数按照题目要求的方法进行运算后得到的结果。

样例输入

24 65
42 66666
3 67

样例输出

66
180
39

题解

思路

还是用char[]读入数据，然后计算的时候做下处理就好。比较常规的题目，思路不难。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    char a[15], b[15];
    while (scanf("%s %s", a, b) != EOF)
    {
        int len1 = strlen(a), len2 = strlen(b);
        long long res = 0;
        // 双重循环计算
        for (int i = 0; i < len1; i++)
        {
            for (int j = 0; j < len2; j++)
            {
                res += (a[i] - '0') * (b[j] - '0');
            }
        }
        printf("%ld\n", res);
    }

    system("pause");
    return 0;
}

问题 D: 比较奇偶数个数

题目

题目描述

第一行输入一个数，为 n，第二行输入 n 个数，这 n 个数中，如果偶数比奇数多，输出 NO，否则输出 YES。

输入

输入有多组数据。
每组输入 n，然后输入 n 个整数（ 1<= n <= 1000）。

输出

如果偶数比奇数多，输出 NO，否则输出 YES。

样例输入

1
67 
7
0 69 24 78 58 62 64 

样例输出

YES
NO

题解

思路

未限定数量，那么while(scanf(表达式) != EOF)，在判断一下计算输出即可。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    int ouNum = 0, jiNum = 0, n, x;
    while (scanf("%d", &n) != EOF)
    {
        while (n--)
        {
            scanf("%d", &x);
            // 根据奇数、偶数增加相应的值
            x % 2 == 0 ? ouNum++ : jiNum++;
        }
        ouNum > jiNum ? printf("NO\n") : printf("YES\n");
    }

    system("pause");
    return 0;
}

问题 E: Shortest Distance (20)

英文题，orz。😭

题目

题目描述

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

翻译：

很简单的任务：给出了一个有 N 个出口的高速公路，形成一个简单的环路，你应该给出任何一对出口之间的最短距离。

输入

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances $D_1$ $D_2$ … $D_N$, where $D_i$ is the distance between the i-th and the (i+1)-st exits, and $D_N$ is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107.

翻译：

每个输入文件包含一个测试用例。对于每种情况，第一行包含整数 N（ 3 <= N <= 105 ），后跟 N 个整数 $D_1$ $D_2$ … $D_N$，其中 $D_i$ 是第 i 个和（i + 1）出口之间的距离，$D_N$ 位于第 N 和第 1 个出口之间。行中的所有数字都由空格分隔。第二行给出了正整数M（ M <= 104），其中 M 行随后，每个线条包含一对出口号，规定出口是从 1 到 N 编号。保证总往返距离不超过107。

输出

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

翻译：

对于每个测试用例，打印在 M 行中的结果，每个结果包含相应给定对出口之间的最短距离。

样例输入

5 1 2 4 14 9
3
1 3
2 5
4 1

样例输出

3
10
7

题解

思路

首先需要先把英文的题目看懂：

题目的意思是：

第一行输入：第一个数表示有 N 条路，并在之后给出 N 个数表示N条道的路径长度，这些路会形成一个环。

第二行的输入：需要计算 M 次给定两个节点之间的最短距离。

接下来的 M 行就是两个节点的序号。

那么其实是求一个最短路的问题，当然简单模拟一下就好了，不是逆时针走就是顺时针走，二者取一。

如果start > end需要交换一下，效果是一样的。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    int n, m, start, end;
    scanf("%d", &n);
    int *a = new int[n];
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    scanf("%d", &m);
    while (m--)
    {
        scanf("%d %d", &start, &end);
        int temp = 0;
        // 需要交换一下
        if (start > end)
        {
            swap(start, end);
        }
        for (int i = start - 1; i < end - 1; i++)
        {
            temp += a[i];
        }
        temp > sum - temp ? printf("%d\n", sum - temp) : printf("%d\n", temp);
    }

    system("pause");
    return 0;
}

问题 F: A+B和C (15)

题目

题目描述

给定区间 $[-2^{31},\ 2^{31}]$ 内的 3 个整数 A 、B 和 C，请判断 A+B 是否大于 C。

输入

输入第 1 行给出正整数 T （<=10），是测试用例的个数。随后给出 T 组测试用例，每组占一行，顺序给出 A、B 和 C。整数间以空格分隔。

输出

对每组测试用例，在一行中输出“Case #X: true”如果 A + B > C，否则输出“Case #X: false”，其中 X 是测试用例的编号（从 1 开始）。

样例输入

4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647

样例输出

Case #1: false
Case #2: true
Case #3: true
Case #4: false

题解

思路

因为数据范围 $[-2^{31},\ 2^{31}]$ ，所以要使用long long。（ $10^9$ 用int）。读取输出long long记得是%lld。别的就很简单了。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    long long A, B, C;
    int n, i = 1;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%lld %lld %lld", &A, &B, &C);
        A + B > C ? printf("Case #%d: true\n", i++) : printf("Case #%d: false\n", i++);
    }
    

    system("pause");
    return 0;
}

问题 G: 数字分类 (20)

题目

题目描述

给定一系列正整数，请按要求对数字进行分类，并输出以下 5 个数字：

$A_1$ = 能被 5 整除的数字中所有偶数的和；

$A_2$ = 将被 5 除后余 1 的数字按给出顺序进行交错求和，即计算 $n_1-n_2+n_3-n_4...$；

$A_3$ = 被 5 除后余 2 的数字的个数；

$A_4$ = 被 5 除后余 3 的数字的平均数，精确到小数点后 1 位；

$A_5$ = 被 5 除后余 4 的数字中最大数字。

输入

每个输入包含 1 个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N，随后给出 N 个不超过 1000 的待分类的正整数。数字间以空格分隔。

输出

对给定的 N 个正整数，按题目要求计算 $A_1$ ~ $A_5$ 并在一行中顺序输出。数字间以空格分隔，但行末不得有多余空格。

若其中某一类数字不存在，则在相应位置输出“N”。

样例输入

13 1 2 3 4 5 6 7 8 9 10 20 16 18
8 1 2 4 5 6 7 9 16

样例输出

30 11 2 9.7 9
N 11 2 N 9

题解

思路

这题也不难，就是根据题意来，需要注意的地方就是 A2 不可以用和 == 0 判断，因为和可能为 0 ，orz。因此需要额外一个变量计数。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    int n;
    // 读取第一个数：个数
    while (scanf("%d", &n) != EOF)
    {

        int x, sign = 1, na4 = 0, na2 = 0, a[5] = {0, 0, 0, 0, INT16_MIN};
        while (n--)
        {
            scanf("%d", &x);
            switch (x % 5)
            {
            case 0:
                if (x % 2 == 0)
                {
                    a[0] += x;
                }
                break;
            case 1:
                a[1] += x * sign;
                sign *= -1;
                na2++;
                break;
            case 2:
                a[2]++;
                break;
            case 3:
                a[3] += x;
                na4++;
                break;
            case 4:
                if (x > a[4])
                {
                    a[4] = x;
                }
                break;
            default:
                break;
            }
        }
        a[0] == 0 ? printf("N") : printf("%d", a[0]);
        na2 == 0 ? printf(" N") : printf(" %d", a[1]);
        a[2] == 0 ? printf(" N") : printf(" %d", a[2]);
        a[3] == 0 ? printf(" N") : printf(" %.1f", a[3] * 1.0 / na4);
        a[4] == INT16_MIN ? printf(" N\n") : printf(" %d\n", a[4]);
    }

    system("pause");
    return 0;
}

问题 H: 部分A+B (15)

题目

题目描述

正整数 A 的 “$D_A$（为 1 位整数）部分” 定义为由 A 中所有 $D_A$ 组成的新整数 $P_A$。例如：给定 A = 3862767，$D_A$ = 6，则 A 的 “6 部分” $P_A$ 是 66，因为 A 中有 2 个 6。

现给定 A、$D_A$、B、$D_B$，请编写程序计算 $P_A + P_B$。

输入

输入在一行中依次给出A、$D_A$、B、$D_B$，中间以空格分隔，其中0 < A, B < 1010。

输出

在一行中输出 $P_A + P_B$ 的值。

样例输入

3862767 6 13530293 3
3862767 1 13530293 8

样例输出

399
0

题解

思路

这题也不难，直接干，pa = pa * 10 + x;这个蛮好用的。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    char a[15], b[15];
    char da, db;
    while (scanf("%s %c %s %c", a, &da, b, &db) != EOF)
    {
        long long pa = 0, pb = 0;
        int lenA = strlen(a), lenB = strlen(b);
        for (int i = 0; i < lenA; i++)
        {
            if (a[i] == da)
            {
                pa = pa * 10 + (a[i] - '0');
            }
        }
        for (int i = 0; i < lenB; i++)
        {
            if (b[i] == db)
            {
                pb = pb * 10 + (b[i] - '0');
            }
        }
        printf("%lld\n", pa + pb);
    }

    system("pause");
    return 0;
}

问题 I: 锤子剪刀布 (20)

题目

题目描述

大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势，胜负规则如图所示：

现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。

输入

输入第1行给出正整数 N（<=105），即双方交锋的次数。随后 N 行，每行给出一次交锋的信息，即甲、乙双方同时给出的的手势。C 代表“锤子”、J代表“剪刀”、B 代表“布”，第 1 个字母代表甲方，第 2 个代表乙方，中间有 1 个空格。

输出

输出第 1、2 行分别给出甲、乙的胜、平、负次数，数字间以 1 个空格分隔。第 3 行给出两个字母，分别代表甲、乙获胜次数最多的手势，中间有 1 个空格。如果解不唯一，则输出按字母序最小的解。

样例输入

10
C J
J B
C B
B B
B C
C C
C B
J B
B C
J J

样例输出

5 3 2
2 3 5
B B

题解

思路

之前其实做过，思路应该是差不多。小技巧就是数组序为B、C、J。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    // af[0]：布(B)，af[1]：石头(C)，af[2]：剪刀（J）
    char figure[] = {'B', 'C', 'J'};
    int aWin = 0, bWin = 0, equal = 0, af[3] = {0}, bf[3] = {0};
    while (n--)
    {
        char a, b;
        char temp;
        scanf("%c", &temp);
        scanf("%c %c", &a, &b);
        if (a == b)
        {
            equal++;
        }
        else if (a == 'J' && b == 'C')
        {
            bWin++;
            bf[1]++;
        }
        else if (a == 'J' && b == 'B')
        {
            aWin++;
            af[2]++;
        }
        else if (a == 'C' && b == 'J')
        {
            aWin++;
            af[1]++;
        }
        else if (a == 'C' && b == 'B')
        {
            bWin++;
            bf[0]++;
        }
        else if (a == 'B' && b == 'C')
        {
            aWin++;
            af[0]++;
        }
        else if (a == 'B' && b == 'J')
        {
            bWin++;
            bf[2]++;
        }
    }
    printf("%d %d %d\n", aWin, equal, bWin);
    printf("%d %d %d\n", bWin, equal, aWin);
    int temp1 = af[1] > af[0] ? 1 : 0;
    int temp2 = bf[1] > bf[0] ? 1 : 0;
    printf("%c %c\n", figure[af[2] > af[temp1] ? 2 : temp1], figure[bf[2] > bf[temp2] ? 2 : temp2]);

    system("pause");
    return 0;
}