2019牛客暑期NOIP真题班普及组5-字符串处理

1. 乒乓球

来源：NOIP2003提高组 https://ac.nowcoder.com/acm/contest/231/A

算法知识点: 字符串处理，模拟

复杂度：

解题思路：

先将整个比赛情况读取进来，然后依次枚举在11分制和21分制下的比赛结果即可。

• 在11分制下，一局比赛结束的条件是：某一方达到11分，且分差达到2；
• 在21分制下，一局比赛结束的条件是：某一方达到21分，且分差达到2；

注意最后如果比分是0:0，也要输出。

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;


void work(string str, int score)
{
    int a = 0, b = 0;
    for (int i = 0; i < str.size() && str[i] != 'E'; i ++ )
    {
        if (str[i] == 'W') a ++ ;
        else b ++ ;

        if (max(a, b) >= score && abs(a - b) >= 2)
        {
            printf("%d:%d\n", a, b);
            a = b = 0;
        }
    }
    printf("%d:%d\n", a, b);
}


int main()
{
    string str, s;
    while (cin >> s) str += s;

    work(str, 11);
    puts("");
    work(str, 21);

    return 0;
}

2. ISBN号码

来源：NOIP2008提高组 https://ac.nowcoder.com/acm/contest/236/D

算法知识点: 字符串处理，模拟

复杂度：

解题思路：

按照题目中给定的规则，计算出识别码，再判断是否与给定的识别码相同：

• 如果相同，输出 "Right"；
• 如果不同，输出 正确的字符串。

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    string str;
    cin >> str;
    int sum = 0;
    for (int i = 0, j = 1; i + 1 < str.size(); i ++ )
        if (str[i] != '-')
        {
            sum += (str[i] - '0') * j;
            j ++ ;
        }
    sum %= 11;
    char c = 'X';
    if (sum < 10) c = '0' + sum;
    if (c == str.back()) puts("Right");
    else
    {
        str.back() = c;
        cout << str << endl;
    }

    return 0;
}

3. 立体图

来源：NOIP2008提高组 https://ac.nowcoder.com/acm/contest/236/A

算法知识点: 字符串处理，模拟，坐标变换

复杂度：

解题思路：

首先将一个小正方体的投影画出来：

char box[6][8] = {
    "..+---+",
    "./   /|",
    "+---+ |",
    "|   | +",
    "|   |/.",
    "+---+.."
};

然后为了正确处理遮挡关系，按照从下到上、从后到前、从左到右的顺序画每个小正方体即可。

接下来需要将三维坐标 投影到二维平面上，为了清楚，我们约定三维坐标系的方向如下所示：

投影到的二维平面的坐标系如下所示：

我们将三维坐标系中最靠左、前、下的点，和二维坐标系中左下角的点( 为左下角的点)对齐。

然后找规律可以发现二者的映射关系：左下角在 的小立方体，投影之后：

• 横坐标是
• 纵坐标是

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 500, M = 60;

int n, m;
char box[6][8] = {
    "..+---+",
    "./   /|",
    "+---+ |",
    "|   | +",
    "|   |/.",
    "+---+.."
};

char g[N][N];
int h[M][M];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> h[i][j];

    // i = 1, j = n - 1, k = 0: 499, 0
    // i = 1, j = n - 2, k = 0: 497, 2
    // i = 1, j = n - 1, k = 1: 499, 4
    // ...

    // i = 2, j = n - 1, k = 0: 496, 0
    // i = 2, j = n - 2, k = 0: 494, 2
    // ...

    // 499 - (i - 1) * 3 - j * 2
    // j * 2 + k * 4

    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            g[i][j] = '.';

    for (int i = 1; i <= 100; i ++ )
        for (int j = 0; j < n; j ++ )
            for (int k = 0; k < m; k ++ )
                if (h[j][k] >= i)
                {
                    int x = 499 - (i - 1) * 3 - (n - 1 - j) * 2;
                    int y = (n - 1 - j) * 2 + k * 4;

                    for (int a = 0; a < 6; a ++ )
                        for (int b = 0; b < 7; b ++ )
                            if (box[a][b] != '.')
                                g[x - 5 + a][y + b] = box[a][b];
                }

    int x = 0;
    for (int i = 0; ; i ++ )
    {
        bool flag = false;
        for (int j = 0; j < N; j ++ )
            if (g[i][j] != '.')
            {
                flag = true;
                break;
            }

        x = i;
        if (flag) break;
    }

    int y = N - 1;
    for (int i = N - 1; ; i -- )
    {
        bool flag = false;
        for (int j = 0; j < N; j ++ )
            if (g[j][i] != '.')
            {
                flag = true;
                break;
            }

        y = i;
        if (flag) break;
    }

    for (int i = x; i < N; i ++ )
    {
        for (int j = 0; j <= y; j ++ )
            cout << g[i][j];
        cout << endl;
    }

    return 0;
}

4. 多项式输出

来源：NOIP2009提高组 https://ac.nowcoder.com/acm/contest/237/D

算法知识点: 字符串处理，模拟

复杂度：

解题思路：

从前往后依次处理每一项，依次考虑符号、系数、x、x的次数：

• 如果系数是0，则直接continue；
• 如果不是第一个非零项，且系数是正的，则输出'+'；如果系数是负的，则无条件输出'-'；
• 如果系数的绝对值不是1，或者是常数项，则输出系数的绝对值；
• 如果次数不为0，则输出x
• 如果次数大于1，则输出次数

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    bool is_first = true;
    for (int i = n; i >= 0; i -- )
    {
        int a;
        cin >> a;

        if (!a) continue;

        if (!is_first && a > 0) printf("+");
        else if (a < 0) printf("-");
        if (abs(a) != 1 || !i) printf("%d", abs(a));
        if (i) printf("x");
        if (i > 1) printf("^%d", i);

        is_first = false;
    }

    return 0;
}

 
另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ