PAT模拟考题记录

[[toc]]

  • 小技巧
    1
    2
    3
    4
    5
    vector<int> in;

    int n;
    scanf("%d", &n);
    in.resize(n)

结构体初始化和运算符重载

1
2
3
4
5
6
7
8
struct node{
    int value;
    int cnt;
    node(int a, int b):value(a), cnt(b){};
    bool operator < (const node &a)const{
        return (cnt != a.cnt) ? cnt > a.cnt : value < a.value;
    }
};

注意，由于set初始就是从小道大排的，所以重载<与cmp类似， 但是priority_queue初始是优先级大的在前面，因此重载<会不一样。

8.23 题目

1112 Stucked Keyboard

思路：

1

注意：

1113 Integer Set Partition

比较简单，排个序就行，15分钟 25分。

思路：从小到大排序，取前面一半和后面一半，sum相减即可。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

int arr[N];
int main (int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    int remain = n % 2;
    int shang = n / 2;
    int sum1 = 0, sum2 = 0;
    sort(arr, arr + n);
    for (int i = 0; i < shang; i++) {
        sum1 += arr[i];
    }
    for (int i = shang; i < n; i++) {
        sum2 += arr[i];
    }
    int res = sum2 - sum1;
    printf("%d %d\n", remain, res);
    return 0;
}

注意：无。

1114 Family Property

思路：

1

注意：

1115 Counting Nodes in a Binary Search Tree

第一次做18分，但是思路太乱了，用静态节点，不熟悉，后面复习了下。下次记得写newNode函数。

思路：二叉搜索树的建立，并统计节点的layer，记录最低和第二低的层。

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
#include <cstdio>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1010;

struct node {
    int data;
    int lchild = -1;
    int rchild = -1;
}Node[N];

int Index = 0;
int newNode(int val){
    Node[Index].data = val;
    Node[Index].lchild = -1;
    Node[Index].rchild = -1;
    return Index++;
}

int layer[N];
int maxLayer;
void insert(int &root, int val, int lay){
    if (root == -1) {
        root = newNode(val);
        layer[lay] ++;
        if (lay > maxLayer) {
            maxLayer = lay;
        }
        return;
    }
    if (val <= Node[root].data) {
        insert(Node[root].lchild, val, lay + 1);
    }
    else {
        insert(Node[root].rchild, val, lay + 1);
    }
}

int main (int argc, char *argv[])
{
    fill(layer, layer + N, 0);
    int n;
    scanf("%d", &n);
    int value;
    scanf("%d", &value);
    int root = newNode(value);
    layer[0] = 1;
    for (int i = 0; i < n - 1; i++) {
        scanf("%d", &value);
        insert(root, value, 0);
    }
    int sum = layer[maxLayer - 1] + layer[maxLayer];
    printf("%d + %d = %d\n", layer[maxLayer], layer[maxLayer - 1], sum);
    return 0;
}

注意：每个节点的地址由编号Index递增。

8.24题目

1116 Come on!Let’s C

思路：一个简单的素数判断

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
#include <cstdio>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <map>
#include <math.h>
using namespace std;

map<int, string> m;
bool isPrime(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main (int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    int value;
    scanf("%d", &value);
    m[value] = "Mystery Award";
    for (int i = 2; i <= n; i++) {
        scanf("%d", &value);
        if (isPrime(i)) {
            m[value] = "Minion";             
        }
        else {
            m[value] = "Chocolate";
        }
    }
    int k;
    scanf("%d", &k);
    int query;
    for (int i = 0; i < k; i++) {
        scanf("%d", &query);
        if (m.find(query) == m.end()) {
            printf("%04d: ", query);
            cout << "Are you kidding?" << endl;
        }
        else {
            printf("%04d: ", query);
            cout << m[query] << endl;
            m[query] = "Checked";
        }
    }    
    return 0;
}

1117 Eddington Number

思路：建个数组排序即可，思路简单

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
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

bool cmp(int a, int b)
{
    return a > b;
}

int arr[N];
int main (int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    int value;
    for (int i = 1; i <= n; i++) {
        scanf("%d", arr + i);
    }
    sort(arr + 1, arr + n + 1, cmp);    
    int maxE = 0;
    for (int i = 1; i <= n; i++) {
        if (arr[i] > i) {
            maxE = i;
        }
        else {
            break;
        }
    }
    printf("%d\n", maxE);
    return 0;
}

1118 Birds in Forest

思路：并查集，将相同照片的鸟加入一个集合。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;

int father[N];
int isRoot[N];

int findFather(int a){
    if (a == father[a]) {
        return a;
    }
    int F = findFather(father[a]);
    father[a] = F;
    return F;
}

void Union(int a, int b){
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        father[faB] = faA;
    }
}

void init(){
    for (int i = 1; i <= N; i++) {
        father[i] = i;
    }
}

bool cmp(int a, int b){
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        return false;
    }
    return true;
}

int main (int argc, char *argv[])
{
    init();
    fill(isRoot, isRoot + N, 0);
    int n, k;
    scanf("%d", &n);
    int max = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        int b;
        int first;
        for (int j = 0; j < k; j++) {
            if (j == 0) {
                scanf("%d", &first);
                if (first > max) {
                    max = first;
                }
            }
            else {
                scanf("%d", &b);
                if (b > max) {
                    max = b;
                }
                Union(first, b);
            }
        }
    }
    for (int i = 1; i <= max; i++) {
        isRoot[findFather(i)]++;
    }
    int num = 0;
    for (int i = 1; i <= max; i++) {
        if (isRoot[i] != 0) {
            num++;
        }
    }
    printf("%d %d\n", num, max);
    int queryNum;
    scanf("%d", &queryNum);
    int query1, query2;
    for (int i = 0; i < queryNum; i++) {
        scanf("%d %d", &query1, &query2);
        if (cmp(query1, query2)) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }    
    return 0;
}

1119 Pre- and Post-order Traversals

思路:前序后序，找左右子树，不存在时，将所有节点当左子树。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstddef>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
const int N = 40;

int pre[N], post[N];
struct node {
    int data;
    node* lchild;
    node* rchild;
};

bool flag = false;
bool flag2 = true;
node* create(int preL, int preR, int postL ,int postR){
    flag = false;
    if (preL > preR) {
        return NULL;
    }
    node* root = new node;
    root->data = pre[preL];
    root->lchild = NULL;
    root->rchild = NULL;
    set<int> s1, s2;
    //寻找左右子树
    for (int i = 0; i < preR - preL -1; i++) {
        s1.insert(pre[preL + i + 1]);
        s2.insert(post[postL + i]);
        if (s1 == s2) {
            flag = true;
            break;
        }
    }
    if (flag) {
        int numLeft = s1.size();
        root->lchild = create(preL + 1, preL + numLeft, postL, postL + numLeft - 1);
        root->rchild = create(preL + numLeft + 1, preR, postL + numLeft, postR - 1);
    }
    else{
        if (preR != preL) {
            flag2 = false;
        }
        int numLeft = preR - preL;
        root->lchild = create(preL + 1, preL + numLeft, postL, postL + numLeft - 1);
        root->rchild = create(preL + numLeft + 1, preR, postL + numLeft, postR - 1);
    }
    return root;
}

int n;
int num = 1;
void inOrder(node* root){
    if (root == NULL) {
        return;
    }
    inOrder(root->lchild);
    printf("%d", root->data);
    if (num != n) {
        printf(" ");
        num++;
    }
    inOrder(root->rchild);
}

int main (int argc, char *argv[])
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", pre + i);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", post + i);
    }
    node* root = create(0, n - 1, 0, n - 1);
    if (flag2) {
        printf("Yes\n");
        inOrder(root);
        printf("\n");
    }
    else {
        printf("No\n");
        inOrder(root);
        printf("\n");
    }
    return 0;
}

8.25 题目

1120 Friend Numbers

思路：利用set可以避免重复和直接排序。

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
#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;

int cal(string str){
    int sum = 0;
    for (int i = 0; i < str.size(); i++) {
        sum += str[i] - '0';
    }
    return sum;
}

set<int> s;
int main (int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    string str; 
    for (int i = 0; i < n; i++) {
        cin >> str;
        s.insert(cal(str));
    }
    printf("%lu\n", s.size());
    int num = 0;
    for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
        printf("%d", *it);
        if (num != s.size() - 1) {
            num ++;
            printf(" ");
        }
    }
    return 0;
}

1121 Damn single

思路：也是利用set并使用erase去除重复的数据。

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
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
const int N = 500010;
const int M = 100010;

bool flag[N]; 
set<int> s;
int arr[N];
int main (int argc, char *argv[])
{
    fill(flag, flag + N, false);
    int n, m;
    int cp1, cp2;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &cp1, &cp2);
        arr[cp1] = cp2;
        arr[cp2] = cp1;
    }
    scanf("%d", &m);
    int person;
    for (int i = 0; i < m; i++) {
        scanf("%d", &person);
        if (flag[person]) {
            s.erase(s.find(arr[person]));
        }
        else {
            flag[person] = true;
            flag[arr[person]] = true;
            s.insert(person);
        }
    }
    printf("%lu\n", s.size());
    int num = 0;
    for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
        printf("%05d", *it);
        if (num < s.size() - 1) {
            num++;
            printf(" ");
        }
    }
    return 0;
}

1122 Humitonian Cycle

思路：用vis记录是否所有点都出现过，保证是回路。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 210;

vector<int> v[N];
bool vis[N] = {false};

int main (int argc, char *argv[])
{
    int n, m, k;
    int v1, v2;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &v1, &v2);
        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }
    int queryNum;
    scanf("%d", &k);
    int check;
    int start;
    for (int i = 0; i < k; i++) {
        bool flag = true;
        fill(vis, vis + N, false);
        scanf("%d", &queryNum);
        if (queryNum != n + 1) {
            flag = false;
        }
        scanf("%d", &start);
        int now = start;
        for (int i = 0; i < queryNum - 1; i++) {
            scanf("%d", &check);
            for (int j = 0; j < v[now].size(); j++) {
                if (v[now][j] == check) {
                    vis[check] = true;
                    break;
                }
            }
            now = check;
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i] == false) {
                flag = false;
            }
        }
        if (flag) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
    return 0;
}

1123 Is it a complete AVL tree

思路：AVL的模版要记牢，是否是完全二叉树只要判断子树前面是否有空就行，利用变量kong记录。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 210;

vector<int> v[N];
bool vis[N] = {false};

int main (int argc, char *argv[])
{
    int n, m, k;
    int v1, v2;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &v1, &v2);
        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }
    int queryNum;
    scanf("%d", &k);
    int check;
    int start;
    for (int i = 0; i < k; i++) {
        bool flag = true;
        fill(vis, vis + N, false);
        scanf("%d", &queryNum);
        if (queryNum != n + 1) {
            flag = false;
        }
        scanf("%d", &start);
        int now = start;
        for (int i = 0; i < queryNum - 1; i++) {
            scanf("%d", &check);
            for (int j = 0; j < v[now].size(); j++) {
                if (v[now][j] == check) {
                    vis[check] = true;
                    break;
                }
            }
            now = check;
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i] == false) {
                flag = false;
            }
        }
        if (flag) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
    return 0;
}

AVL中有些参数是node* &root,此时传入的地址也是实参，不是复制，有时会改变更节点的位置，因此&一定要加上。

8.26题目

1128 N Queens Puzzle

思路：只要判断是否在斜对角线上就行

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
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
const int N = 1010;
bool flag[N];

bool judge(vector<int> v){
    for (int i = 0; i < v.size(); i++) {
        for (int j = i + 1; j < v.size(); j++) {
            if (abs(j - i)  == abs(v[j] - v[i])) {
                return false;
            }
        }
    }
    return true;
}

vector<int> v;
int main (int argc, char *argv[])
{
    int k, n;
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        bool ans = true;
        scanf("%d", &n);
        v.resize(n);
        fill(flag, flag + n + 1, false);
        for (int j = 0; j < n; j++) {
            scanf("%d", &v[j]);
            if (flag[v[j]] == true) {
                ans = false;
            }
            flag[v[j]] = true;
        }
        if (ans && judge(v)) {
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}

注意：测试点一，可能出现在同一行的情况，要加条件判断, 是否所有数字都出现了。

1129 Recommedation System

思路：写的时候每次加入都去sort，有些答案超时了。方法1是自己写的，每次都去sort排序很浪费时间，但是想不到什么好的方法。方法二是柳神的，写的时候也用过set直接排序，不知道怎么两个排，set不支持sort，原来可以重载运算法，算是学到了。

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
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 50010;


int num[N];
bool vis[N];
vector<int> v;

bool cmp(int a, int b){
    if (num[a] != num[b]) {
        return num[a] > num[b];
    }
    else {
        return a < b;
    }
}

int main (int argc, char *argv[])
{
    int n, k;
    scanf("%d %d", &n, &k);
    fill(num, num + N, 0);
    fill(vis, vis + N, false);
    int query;
    scanf("%d", &query);
    num[query] ++;
    vis[query] = true;
    v.push_back(query);
    for (int i = 1; i < n; i++) {
        scanf("%d", &query);
        printf("%d:", query);
        for (int j = 0; j < v.size() && j < k; j++) {
            printf(" %d", v[j]);
        }
        printf("\n");
        num[query]++;
        if (vis[query] == false) {
            v.push_back(query);
            vis[query] = true;
        }
        sort(v.begin(), v.end(), cmp);
    }
    return 0;
}

方法二：set，重载，auto, 结构体初始化。

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
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
const int N = 50010;

int book[N];
struct node {
    int data;
    int num;
    node(int a, int b):data(a), num(b){};
    bool operator < (const node &a)const{
        return (num != a.num) ? num > a.num : data < a.data;
    }
};

set<node> s;
int main (int argc, char *argv[])
{
    int n, k;
    scanf("%d %d", &n, &k);
    int value;
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
        if (i != 0) {
            printf("%d:", value);
            int tempCnt = 0;
            for (auto it = s.begin(); tempCnt < k && it != s.end(); it++) {
                printf(" %d", it->data);
                tempCnt++;
            }
            printf("\n");
        }
        auto it = s.find(node(value, book[value]));
        if (it != s.end()) {
            s.erase(it);
        }
        book[value]++;
        s.insert(node(value, book[value]));
    }
    return 0;
}

注意：因为可能有重复的node因此要做erase。

1130 infix Expression

思路：用了静态数组节点，最难的应该是什么时候加括号，经过发现当一个节点有左子树或者有右子树的时候，且不为根节点时加。

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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int N = 30;

struct node {
    string data;
    int lchild;
    int rchild;
}Node[N];

int Index = 1;
void newNode(string str, int l, int r){
    Node[Index].data = str;
    Node[Index].lchild = l;
    Node[Index].rchild = r;
    Index++;
}
int k;
void inOrder(int root){
    if (root == -1) {
        return;
    }
    if(root != k && (Node[root].lchild !=-1 || Node[root].rchild != -1))
        cout << "(";
    inOrder(Node[root].lchild);
    cout << Node[root].data;
    inOrder(Node[root].rchild);
    if(root != k && (Node[root].lchild !=-1 || Node[root].rchild != -1))
        cout << ")";
}

bool vis[N];
int main (int argc, char *argv[])
{
    fill(vis, vis + N, false);
    int n;
    scanf("%d", &n);
    string str;
    int left, right;
    for (int i = 0; i < n; i++) {
        cin >> str >> left >> right;
        newNode(str, left, right);
        if (left != -1) {
            vis[left] = true;
        }
        if (right != -1) {
            vis[right] = true;
        }
    }
    for (k = 1; k <= n; k++) {
        if (vis[k] == false) {
            break;
        }
    }
    inOrder(k);
    return 0;
}

8.27 题目

1132 Cur Integer

思路：用string去截字符串即可，第一次做测试点二三报了浮点错误。了解到了浮点错误因为除零报错了。后面改了下代码，特判一下就行了。

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
#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

bool judge(string str){
    int len = str.length();
    string str1 = str.substr(0, len / 2);
    string str2 = str.substr(len / 2, len - len / 2);
    if ((stoi(str1) * stoi(str2)) == 0) {
        return false;
    }
    else if (stoi(str) % (stoi(str1) * stoi(str2)) == 0) {
        return true;
    }
    return false;
}

int main (int argc, char *argv[])
{
    int n;
    string str;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        cin >> str;
        if (judge(str)) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    return 0;
}

1133 Splitting A Linked List

思路：创建三个vector，遍历链表的时候，顺序将范围中的树加入到相应数组中，最后合并到一个数组即可。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

struct node {
    int add;
    int data;
    int next;
}Node[N];

int k;

vector<node> nv;
vector<node> lkv;
vector<node> gkv;
int main (int argc, char *argv[])
{
    int start, n;
    scanf("%d%d%d", &start, &n, &k);
    int add, data, next;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &add, &data, &next);
        Node[add].add = add;
        Node[add].data = data;
        Node[add].next = next;
    }
    int temp = start;
    while (temp != -1) {
        if (Node[temp].data < 0) {
            nv.push_back(Node[temp]);
        }
        else if (Node[temp].data <= k) {
            lkv.push_back(Node[temp]);
        }
        else {
            gkv.push_back(Node[temp]);
        }
        temp = Node[temp].next;
    }
    for (int i = 0; i < lkv.size(); i++) {
        nv.push_back(lkv[i]);
    }
    for (int i = 0; i < gkv.size(); i++) {
        nv.push_back(gkv[i]);
    }
    for (int i = 0; i < nv.size(); i++) {
        if (i == nv.size() - 1) {
            printf("%05d %d -1\n", nv[i].add, nv[i].data);
        }
        else {
            printf("%05d %d %05d\n", nv[i].add, nv[i].data, nv[i+1].add);
        }
    }
    return 0;
}

1134 Vertex Cover

思路：只要确保查询的节点中包含所有边就行了。用set存加入的边，当set.size == m,即可输出yes，反之输出no。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int N = 1e4 + 10;

vector<int> v[N];
int main (int argc, char *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    int v1, v2;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &v1, &v2);
        v[v1].push_back(i);
        v[v2].push_back(i);
    }
    int k;
    scanf("%d", &k);
    int queryNum;
    for (int i = 0; i < k; i++) {
        set<int> s;
        scanf("%d", &queryNum);
        int ve;
        for (int j = 0; j < queryNum; j++) {
            scanf("%d", &ve);
            for (int i = 0; i < v[ve].size(); i++) {
                s.insert(v[ve][i]);
            }
        }
        if (s.size() == m) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    return 0;
}

1135 Is it A Red-Black Tree

红黑树没学过，不了解，写不来。

赏

谢谢你请我吃糖果

支付宝

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

stay hungry,stay foolish<br>keep walking,keep thinking<br><br><br>数码爱好者<br>技术探寻者<br>生活领悟者<br>永远保持对新事物的热情<br><br><br>浙江工业大学的本科生<br>邮箱联系:201906062230@zjut.edu.cn<br>QQ:272181284