NJUCSE17

2017 问题求解二 期末考试

2018-07-12 by Fancy

请忽略玄学的代码高亮

1519 Problem A 简单搜索

输入升序排列的数组，查询某个元素的位置。（n<=1e5）

一个 lower_bound 或者 map 解决，但似乎老师说要手写二分。
　
听说卡 cin？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
int n, m, a[100000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 0, x; i < m; ++i) {
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (x <= a[mid]) r = mid;
            else l = mid + 1;
        }
        printf("%d\n", l);
    }
}

1079 Problem B Quicksort

手写快排。（n<=1e5）

人生第一次手写快排，幸亏看到了提示。
　
听说有人死于不会写随机数。但这题并不需要很严格的随机数，乱搞一下应该就过了。
法一：调用 cstdlib 库中的 rand()。
法二：调用 algorithm 库中的 std::random_shuffle() 直接打乱原数组。
法三：随便找个数列 $r_i = (a\times r_{i-1} + b)\bmod p$ 作为随机数。
法四：把数列中的左端点、中间点、三分点之类的作为 pivot。
注：前两个需要 std::srand(time(NULL))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
int n, a[100005];

void QuickSort(int l, int r) {
    if (l >= r) return;
    int x = rand() % (r - l + 1) + l, mid = l;
    std::swap(a[x], a[r]);

    for (int i = l, x = a[r]; i < r; ++i)
        if(a[i] < x) std::swap(a[i], a[mid++]);
    std::swap(a[mid], a[r]);

    QuickSort(l, mid - 1);
    QuickSort(mid + 1, r);
}
int main() {
    std::srand(time(NULL));
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        QuickSort(1, n);
        for (int i = 1; i <= n; ++i)
            printf("%d%c", a[i], i < n ? ' ' : '\n');
    }
}

1520 Problem C 二叉树计数

递归计算二叉树每个结点的子树结点个数。

树边不是 n-1 条吗 hhhhh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
const int N = 1000005;
int n, size[N], ch[N][2];
int Dfs(int x) {
    size[x] = 1;
    if (ch[x][0]) size[x] += Dfs(ch[x][0]);
    if (ch[x][1]) size[x] += Dfs(ch[x][1]);
    return size[x];
}
int main() {
    scanf("%d", &n);
    int x, y;
    char opt[5];
    while (scanf("%d", &x)) {
        if (x == -1) break;
        scanf("%s%d", opt, &y);
        ch[x + 1][opt[0] == 'R'] = y + 1;
    }
    Dfs(1);
    for (int i = 1; i <= n; ++i)
        printf("%d : %d\n", i - 1, size[i]);
}

1214 Problem D Red-Black Tree-2

手写红黑树的插入。

伪代码够良心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <string>
struct node{
    node *p, *ch[2];
    std::string s;
    int col;
    int flag() {return p->ch[1] == this;}
    node(node *, std::string, int);
} *root, *null;
node::node(node *p, std::string s, int c) : p(p), s(s), col(c) {ch[0] = ch[1] = null;}
void Rotate(node *y) {
    node *x = y->p;
    int f = !y->flag();
    if (x == root) (root = y)->p = null;
    else (x->p->ch[x->flag()] = y)->p = x->p;
    (x->ch[!f] = y->ch[f])->p = x;
    (y->ch[f] = x)->p = y;
}
void FixUp(node *x) {
    for (; !x->p->col; x = x->p->p) {
        int f = x->p->flag();
        if (!x->p->p->ch[!f]->col) {
            x->p->col ^= 1;
            x->p->p->col ^= 1;
            x->p->p->ch[!f]->col ^= 1;
        } else {
            if (x->flag() != f) Rotate(x);
            else x = x->p;
            x->col ^= 1;
            x->p->col ^= 1;
            Rotate(x);
            break;
        }
    }
    root->col = 1;
}
void Insert(node *&x, node *p, std::string s) {
    if (x == null) FixUp(x = new node(p, s, 0));
    else Insert(x->ch[s >= x->s], x, s);
}
void Inorder(node *x) {
    std::cout << x->s << (x->col ? ":black" : ":red") << std::endl;
    if (x->ch[0] != null) Inorder(x->ch[0]);
    if (x->ch[1] != null) Inorder(x->ch[1]);
}
int Find(node *x, std::string s) {
    if (s == x->s || x == null) return 0;
    return Find(x->ch[s >= x->s], s) + 1;
}
int main() {
    root = null = new node(0, std::string(""), 1);
    null->p = null->ch[0] = null->ch[1] = null;
    int n, m;
    std::cin >> n >> m;
    for (std::string s; n; --n)
        std::cin >> s, Insert(root, null, s);
    Inorder(root);
    for (std::string s; m; --m)
        std::cin >> s, std::cout << Find(root, s) << std::endl;
}
Tags: 编程
← 全日制本科学生发展测评表测评细则 9月班会活动选项 →