NCST-暑期基础培训-第三周排位赛-题解

A-双链表

题目描述

学习完单链表之后，需要你来实现一个双链表，下面是双链表的主要功能：

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 k 个插入的数删除；
4. 在第 k 个插入的数左侧插入一个数；
5. 在第 k 个插入的数右侧插入一个数；

现在要对该链表进行 $M$ 次操作，进行完所有操作后，从左到右输出整个链表。

输入

第一行包括一个整数 $M$ ，表示操作次数，接下来 $M$ 行，每行包含一个操作命令，操作命令可能为以下几种:

1. L X ：表示在链表的最左端插入数 X
2. R X ：表示链表的最右端插入数 X
3. D K ：表示将第 K 个插入的数删除
4. IL K X ：表示在第 K  个插入的数左侧插入一个数X
5. IR K X ： 表示在第 K 个插入的数右侧插入一个数X

输出

将整个链表从左到右输出

样例输入

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

样例输出

8 7 7 3 2 9

提示

$1$ ≤ $M$ ≤ $10^5$

所有操作保证合法

Contest Problems - Online Judge System

思路

这题可以理解为链表的优化，我们都知道，链表的查询的时间复杂度是 $O(n)$ ，但是当我们需要做到高速插入删除的的同时能高速查询，我们可以想到一种数据结构，名为数组链表。我们可以用数组来储存我们链表节点的指针。这样我们查询一个节点的时候就可以做到高速查询，我们也可以基于链表的性质做到告诉插入和删除。而这题便是这样的一个数据结构。

C with STL代码

#include <iostream>
#include <list>

using namespace std;
list<int> que;
list<int>::iterator its[100005];
bool erased[100005];
int n, times = 1;

void work(string s) {
    if (s == "L") {
        int val;
        cin >> val;
        its[times++] = que.insert(que.begin(), val);
    } else if (s == "R") {
        int val;
        cin >> val;
        its[times++] = que.insert(que.end(), val);
    } else if (s == "D") {
        int val;
        cin >> val;
        if (not erased[val]) {
            que.erase(its[val]);
            erased[val] = true;
        }
    } else if (s == "IL") {
        int index, val;
        cin >> index >>  val;
        its[times++] = que.insert(its[index], val);
    } else if (s == "IR") {
        int index, val;
        cin >> index >>  val;
        its[times++] = que.insert(next(its[index]), val);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        string input;
        cin >> input;
        work(input);
    }
    for (auto val: que) {
        cout << val << ' ';
    }
    return 0;
}

B-池塘计数

问题描述

农夫乔治有一片 $N\times{M}$ 的土地

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，乔治想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入

第一行包含两个整数 N M

接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出

输出一个整数，表示池塘数目。

样例输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

样例输出

3

提示

1 ≤ N, M ≤ 1000

Contest Problems - Online Judge System

思路

这题是一类经典的搜索题，我也写过类似题目的题解，如洛谷P1162-填涂颜色-题解。这题也一样就是寻找“W”，然后填涂成“.”，当找不到“W”了，说明搜索结束了，代码如下

C with STL代码

#include <iostream>

using namespace std;
char mat[1000][1000];
int n, m, ans = 0, x = 0, y = 0,
        dx[]{1, 1, 1, -1, -1, -1, 0, 0},
        dy[]{1, 0, -1, -1, 0, 1, 1, -1};

char getch() {
    do {
        int c = getchar();
        if (c == '.' or c == 'W')
            return char(c);
    } while (true);
}

bool find() {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (mat[i][j] == 'W')
                return (x = i, y = j, true);
    return false;
}
void dfs(int X, int Y) {
    mat[X][Y] = '.';
    for (int i = 0; i < 8; ++i) {
        int px = X + dx[i], py = Y + dy[i];
        if (px >= 0 and py >= 0 and px < n and py < m
            and mat[px][py] == 'W')
            dfs(px, py);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            mat[i][j] = getch();
    while (find()) {
        dfs(x, y);
        ++ans;
    }
    printf("%d", ans);
    return 0;
}

C-整数

描述

给你两个实数 a ，b ，请问 a - b的绝对值是否为一整数？

输入

输入共一行两个实数 a b，输入保留到小数点后12位

输出

输出一行，如果二者差的的绝对值为整数，则输出 YES ，否则输出 NO

样例输入

114.123456789000  514.123456789000

样例输出

YES

提示

$0$ ≤ a ≤ $10^9$

$0$ ≤ b ≤ $10^9$

a b保留到小数点后12位

Contest Problems - Online Judge System

思路

这题不就是一纯粹的水题嘛？做不出来可以说是没学过C/C++了。 这题看上去是一个高精度减法题，但是其实就是一道简单的字符串分割和比较罢了。我们可以把小数点后的数字字符串取出，比较两个字符串是否相等即可。（因为不等，那肯定他们相减就不是整数了嘛）

C with STL代码

#include <iostream>
int main() {
    std::string s1, s2; std::cin >> s1 >> s2;
    std::cout << (s1.substr(s1.find('.')) == s2.substr(s2.find('.')) ? "YES" : "NO");
    return 0;
}

D-求m区间内的最小值

题目描述

一个含有 $n$ 项的数列，求出每一项前的 $m$ 个数到它这个区间内的最小值。若前面的数不足 $m$ 项则从第 $1$ 个数开始，若前面没有数则输出 $0$。

输入

第一行两个整数，分别表示 $n$ ，$m$ 。

第二行 $n$ 个正整数，为所给定的数列 $a_i$​

输出

$n$ 行，每行一个整数，第 $i$ 个数为序列中 $a_i$​ 之前 $m$ 个数的最小值

样例输入

6 2
7 8 1 4 3 2

样例输出

0
7
7
1
1
3 

提示

$1 ≤ m ≤ n ≤ 2\times{10^6}$

$1 ≤ ai ≤ 10^5$

Contest Problems - Online Judge System

思路

这题之前在第一次队内训练的时候就做过了，要是还不会做可以去翻翻视频啦！

这题就是单调队列的运用，需要注意的是，你需要使用快读快写来避免超时间。当然你用线段树，之类的应该也可以滴

#include <deque>
#include <iostream>

int read() {
    int data = 0, c = getchar();
    bool f = false;
    while (c < '0' or c > '9') {
        if (c == '-')
            f = true;
        c = getchar();
    }
    while (c >= '0' and c <= '9') {
        data = (data << 3) + (data << 1) + c - '0';
        c = getchar();
    }
    return f ? -data : data;
}
int main() {
    int n = read(), m = read();
    int arr[n + 1];
    for (int i = 1; i <= n; ++i)
        arr[i] = read();
    std::deque<int> q, ans;
    ans.emplace_back(0);
    for (int i = 1; i <= n; ++i) {
        while (not q.empty() and i - q.front() >= m)
            q.pop_front();
        while (not q.empty() and arr[q.back()] > arr[i])
            q.pop_back();
        q.emplace_back(i);
        ans.emplace_back(arr[q.front()]);
    }
    ans.pop_back();
    for (auto &i: ans)
        printf("%d\n", i);
    return 0;
}

E-字母

题目描述

有一个 8*8 的点格，在点格中存在一些字母，这些字母垂直写在一列中，现在请你输出这些字母

输入

一个8*8的字符数组，由 ‘.’ 和字母组成。其中这些字母只写在一列中。

输出

请你输出这些字母

样例输入

........
.n......
.c......
.s......
.t......
........
........
........

样例输出

ncst

Contest Problems - Online Judge System

思路

这题就是单纯的输入，遍历每一列，输出每一列的字母，数据也不会炸，放心实用。
如果不会可以再学习一下循环的应用

#include <iostream>
char mat[8][8];
char getch() {
    do {
        int c = getchar();
        if(c == '.' or ((c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z')))
            return char(c);
    }
    while(true);
}
int main() {
    for(auto &i : mat)
        for(auto &j : i)
            j = getch();
    for(int i = 0; i < 8; ++i)
        for(auto & j : mat)
            if(j[i] != '.')
                putchar(j[i]);
    return 0;
}