hdvsyu's blog

Posted on Edited on In

图着色问题是一个著名的NP完全问题。给定无向图 G = (V, E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？ 但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入格式：

输入在第一行给出3个整数V（0 < V <= 500）、E（>= 0）和K（0 < K <= V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（<= 20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。

输出格式：

对每种颜色分配方案，如果是图着色问题的一个解则输出“Yes”，否则输出“No”，每句占一行。

输入样例：

6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4

输出样例：

Yes
Yes
No
No

用邻接表表示图，每个顶点的邻接点可以很容易找到，这样就可以判断他们两个的颜色是否是一样。另一个问题时给出的颜色的个数必须是K个，多了少了都不行。 verify函数是验证图中的相邻顶点是否存在相同的颜色，即对颜色的判断。 color_num函数是有多少个不同的颜色个数。

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
#include <cstdio>
#include <vector>
#include <cstdlib>

using namespace std;

bool verify(vector<vector<int>> vertex, int *color, int v) {
    for (int i = 1; i <= v; i++) {
        for (int j = 0; j < vertex[i].size(); j++) {
            if (color[vertex[i][j]] == color[i]) {
                return false;
            }
        }
    }
    return true;
}

int color_num(int *color, int v) {
    color[0] = -1;
    qsort(color, v + 1, sizeof(*color), [](const void *a, const void *b) {
        int arg1 = *static_cast<const int *>(a);
        int arg2 = *static_cast<const int *>(b);

        if (arg1 < arg2) return -1;
        if (arg1 > arg2) return 1;
        return 0;
    });
    int i = 1, j = 2;
    while (j <= v) {
        if (color[j] != color[i]) color[++i] = color[j];
        j++;
    }
    return i;
}

int main() {
    int v = 0, e = 0, k = 0, v1 = 0, v2 = 0, n = 0;
    scanf("%d %d %d", &v, &e, &k);
    vector<vector<int> > vertex(v + 1); // 1 ~ v
    for (int i = 0; i < e; i++) {
        scanf("%d %d", &v1, &v2);
        vertex[v1].push_back(v2);
        vertex[v2].push_back(v1);
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int *color = new int[v + 1];
        for (int j = 1; j <= v; j++) scanf("%d", &color[j]);
        if (verify(vertex, color, v) && color_num(color, v) == k) printf("Yes\n");
        else printf("No\n");
        delete[] color;
    }
    return 0;
}

Posted on Edited on In

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

题目给出后序和中序，求确定的层序遍历。 getLevel中的while语句是找到根节点所在的位置，然后递归处理左子树和右子树。 变量l的作用是标记一个结点在树中的下标，找到根节点并把它存入一个指定的下标当中，最后输出的level就是层序遍历的结果。

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
#include <cstdio>
#include <cstring>

int *post, *in, *level;

void getLevel(int s, int e, int r, int l) {
    if (s > e) return;
    int i = s;
    while (i <= e && in[i] != post[r]) i++;
    getLevel(s, i - 1, r - e + i - 1, 2 * l + 1);
    getLevel(i + 1, e, r - 1, 2 * l + 2);
    level[l] = post[r];
}

int main() {
    int n = 0;
    scanf("%d", &n);
    post = new int[n], in = new int[n], level = new int[100000];
    for (int i = 0; i < n; i++) {
        scanf("%d", &post[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &in[i]);
    }
    memset(level, -1, 100000);
    getLevel(0, n - 1, n - 1, 0);
    printf("%d", level[0]);
    for (int i = 1; n > 1; i++) {
        if (level[i] != -1) {
            printf(" %d", level[i]);
            n--;
        }
    }
    delete[] level;
    delete[] in;
    delete[] post;
    return 0;
}

Posted on Edited on In

There is a kind of balanced binary search tree named red-black tree in the data structure. It has the following 5 properties: (1) Every node is either red or black. (2) The root is black. (3) Every leaf (NULL) is black. (4) If a node is red, then both its children are black. (5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. For example, the tree in Figure 1 is a red-black tree, while the ones in Figure 2 and 3 are not.

For each given binary search tree, you are supposed to tell if it is a legal red-black tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (<=30) which is the total number of cases. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the preorder traversal sequence of the tree. While all the keys in a tree are positive integers, we use negative signs to represent red nodes. All the numbers in a line are separated by a space. The sample input cases correspond to the trees shown in Figure 1, 2 and 3.

Output Specification:

For each test case, print in a line “Yes” if the given tree is a red-black tree, or “No” if not.

Sample Input:

3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17

Sample Output:

Yes
No
No

判断一个树是否满足红黑树的性质。 find函数每次找到右子树的根节点，然后把树划分为左右子树，递归处理问题。getH获取树的高度。 solve4判断是否满足（4）条件，solve5判断是否满足（5）条件。 代码如下：

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
#include <cstdio>
#include <vector>
#include <cstdlib>

using namespace std;

int find(vector<int> tree, int s, int e) {
    int i = s + 1;
    while (i <= e && abs(tree[s]) > abs(tree[i])) i++;
    return i;
}

bool solve4(vector<int> tree, int s, int e) {
    if (s > e) return true;
    int i = find(tree, s, e);
    if (tree[s] < 0) {
        if (s + 1 <= e && tree[s + 1] < 0) return false;
        if (i <= e && tree[i] < 0) return false;
    }
    return solve4(tree, s + 1, i - 1) && solve4(tree, i, e);
}

int getH(vector<int> tree, int s, int e) {
    if (s > e) return 1;
    int i = find(tree, s, e);
    int l = getH(tree, s + 1, i - 1);
    int r = getH(tree, i, e);
    return tree[s] > 0 ? max(l, r) + 1 : max(l, r);
}

bool solve5(vector<int> tree, int s, int e) {
    if (s > e) return true;
    int i = find(tree, s, e);
    int l = getH(tree, s + 1, i - 1);
    int r = getH(tree, i, e);
    if (l != r) return false;
    return solve5(tree, s + 1, i - 1) && solve5(tree, i, e);
}

bool isRBT(vector<int> tree, int n) {
    if (tree[0] < 0) return false;
    if (!solve4(tree, 0, n - 1)) return false;
    return solve5(tree, 0, n - 1);
}

int main() {
    int k = 0, n = 0;
    scanf("%d", &k);
    vector<int> tree;
    for (int i = 0; i < k; i++) {
        scanf("%d", &n);
        tree.resize(n);
        for (int j = 0; j < n; j++) {
            scanf("%d", &tree[j]);
        }
        if (isRBT(tree, n)) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

Posted on Edited on In

批改多选题是比较麻烦的事情，有很多不同的计分方法。有一种最常见的计分方法是：如果考生选择了部分正确选项，并且没有选择任何错误选项，则得到50%分数；如果考生选择了任何一个错误的选项，则不能得分。本题就请你写个程序帮助老师批改多选题，并且指出哪道题的哪个选项错的人最多。

输入格式：

输入在第一行给出两个正整数N（<=1000）和M（<=100），分别是学生人数和多选题的个数。随后M行，每行顺次给出一道题的满分值（不超过5的正整数）、选项个数（不少于2且不超过5的正整数）、正确选项个数（不超过选项个数的正整数）、所有正确选项。注意每题的选项从小写英文字母a开始顺次排列。各项间以1个空格分隔。最后N行，每行给出一个学生的答题情况，其每题答案格式为“(选中的选项个数 选项1 ……)”，按题目顺序给出。注意：题目保证学生的答题情况是合法的，即不存在选中的选项数超过实际选项数的情况。

输出格式：

按照输入的顺序给出每个学生的得分，每个分数占一行，输出小数点后1位。最后输出错得最多的题目选项的信息，格式为：“错误次数 题目编号（题目按照输入的顺序从1开始编号）-选项号”。如果有并列，则每行一个选项，按题目编号递增顺序输出；再并列则按选项号递增顺序输出。行首尾不得有多余空格。如果所有题目都没有人错，则在最后一行输出“Too simple”。

输入样例1：

3 4
3 4 2 a c
2 5 1 b
5 3 2 b c
1 5 4 a b d e
(2 a c) (3 b d e) (2 a c) (3 a b e)
(2 a c) (1 b) (2 a b) (4 a b d e)
(2 b d) (1 e) (1 c) (4 a b c d)

输出样例1：

3.5
6.0
2.5
2 2-e
2 3-a
2 3-b

输入样例2：

2 2
3 4 2 a c
2 5 1 b
(2 a c) (1 b)
(2 a c) (1 b)

输出样例2：

5.0
5.0
Too simple

错误是指错选或者漏选。 我用异或运算来判断一个选项和正确选项是否匹配，如果是匹配的，那么异或的结果应当是0；如果不匹配，那么这个选项就是存在错选或者漏选的情况的。例：设a为00001，b为00010，c为00100，d为01000，e为10000，如果给定的正确答案是ac，即10001，那么如果给出的选项也是10001，异或的结果就是0；如果给出的选项是a或者ab，即00001或00011，异或之后不为0，就是错选和漏选的。 通过异或操作的结果，再用与运算就可以把错选和漏选的选项找出来，具体的看代码。 full_socre表示一道题满分的分值；true_opt表示正确的选项，存储的是正确选项二进制的值，二进制有hash给出分别是1,2,4,8,16；fre是错误的次数。 代码如下：

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
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int n = 0, m = 0, opt_num = 0, true_opt_num = 0, temp = 0, max_error_cnt = 0;
    int hash[] = {1, 2, 4, 8, 16}, opt[1010][110] = {0};
    char c;
    scanf("%d %d", &n, &m);
    vector<int> full_score(m), true_opt(m);
    vector<vector<int> > fre(m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &full_score[i], &opt_num, &true_opt_num);
        for (int j = 0; j < true_opt_num; j++) {
            scanf(" %c", &c);
            true_opt[i] += hash[c - 'a'];
        }
        fre[i].resize(5);
    }
    for (int i = 0; i < n; i++) {
        double grade = 0;
        for (int j = 0; j < m; j++) {
            getchar();
            getchar(); // '('
            scanf("%d", &temp);
            for (int k = 0; k < temp; k++) {
                scanf(" %c", &c);
                opt[i][j] += hash[c - 'a'];
            }
            getchar(); // ')'
            int el = opt[i][j] ^true_opt[j];
            if (el) {
                if ((opt[i][j] | true_opt[j]) == true_opt[j]) {
                    grade += full_score[j] * 1.0 / 2;
                }
                if (el) {
                    if (el & hash[0]) fre[j][0]++; // a
                    if (el & hash[1]) fre[j][1]++; // b
                    if (el & hash[2]) fre[j][2]++; // c
                    if (el & hash[3]) fre[j][3]++; // d
                    if (el & hash[4]) fre[j][4]++; // e
                }
            } else
                grade += full_score[j];
        }
        printf("%.1f\n", grade);
    }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < 5; j++)
            max_error_cnt = max_error_cnt > fre[i][j] ? max_error_cnt : fre[i][j];

    if (max_error_cnt == 0) {
        printf("Too simple\n");
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < fre[i].size(); j++) {
                if (max_error_cnt == fre[i][j]) {
                    printf("%d %d-%c\n", max_error_cnt, i + 1, 'a' + j);
                }
            }
        }
    }
    return 0;
}

Posted on Edited on In

地球人习惯使用十进制数，并且默认一个数字的每一位都是十进制的。而在PAT星人开挂的世界里，每个数字的每一位都是不同进制的，这种神奇的数字称为“PAT数”。每个PAT星人都必须熟记各位数字的进制表，例如“……0527”就表示最低位是7进制数、第2位是2进制数、第3位是5进制数、第4位是10进制数，等等。每一位的进制d或者是0（表示十进制）、或者是[2，9]区间内的整数。理论上这个进制表应该包含无穷多位数字，但从实际应用出发，PAT星人通常只需要记住前20位就够用了，以后各位默认为10进制。 在这样的数字系统中，即使是简单的加法运算也变得不简单。例如对应进制表“0527”，该如何计算“6203+415”呢？我们得首先计算最低位：3+5=8；因为最低位是7进制的，所以我们得到1和1个进位。第2位是：0+1+1（进位）=2；因为此位是2进制的，所以我们得到0和1个进位。第3位是：2+4+1（进位）=7；因为此位是5进制的，所以我们得到2和1个进位。第4位是：6+1（进位）=7；因为此位是10进制的，所以我们就得到7。最后我们得到：6203+415=7201。

输入格式：

输入首先在第一行给出一个N位的进制表（0 < N <=20），以回车结束。 随后两行，每行给出一个不超过N位的正的PAT数。

输出格式：

在一行中输出两个PAT数之和。

输入样例：

30527
06203
415

输出样例：

7201

从最后一位向前遍历，把两个位置的数字相加，并求出进位值。把每一个结果存进一个双端队列当中，最后输出双端队列的时候，把前排的零先去掉。 long的最长是19位，题目最长可能是20 位，所以用字符串的方式进行处理。 注意结果为0的情况和long long 溢出的情况。 我处理的方式比较复杂。代码如下：

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 <cstring>
#include <stack>
#include <deque>

using namespace std;

int main() {
    char radix[30], a[30], b[30];
    scanf("%s %s %s", radix, a, b);
    int ai = strlen(a) - 1, bi = strlen(b) - 1, carry = 0, ri = strlen(radix) - 1;
    deque<int> ans;
    while (ai >= 0 || bi >= 0) {
        int temp = radix[ri] - '0';
        if (temp == 0) temp = 10;
        if (ai >= 0 && bi >= 0) {
            ans.push_back((a[ai] - '0' + b[bi] - '0' + carry) % temp);
            carry = (a[ai] - '0' + b[bi] - '0' + carry) / temp;
            ai--;
            bi--;
            ri--;
        } else if (ai >= 0) {
            ans.push_back((a[ai] - '0' + carry) % temp);
            carry = (a[ai] - '0' + carry) / temp;
            ai--;
            ri--;
        } else if (bi >= 0) {
            ans.push_back((b[bi] - '0' + carry) % temp);
            carry = (b[bi] - '0' + carry) / temp;
            bi--;
            ri--;
        } else {
            break;
        }
    }
    if (carry != 0) {
        int temp = radix[ri] - '0';
        if (temp == 0) temp = 10;
        ans.push_back(carry % temp);
    }
    while (ans.size() != 0 && ans.back() == 0) {
        ans.pop_back();
    }
    if (ans.size() == 0) printf("0");
    else {
        while (ans.size() != 0) {
            printf("%d", ans.back());
            ans.pop_back();
        }
    }
    return 0;
}

Posted on Edited on In

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而[0, K]区间内的元素都排在大于K的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K为10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出：第1个结点的地址；结点总个数，即正整数N (<= 105)；以及正整数K (<=1000)。结点的地址是5位非负整数，NULL地址用-1表示。 接下来有N行，每行格式为： Address Data Next 其中_Address_是结点地址；_Data_是该结点保存的数据，为[-105, 105]区间内的整数；_Next_是下一结点的地址。题目保证给出的链表不为空。

输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

输出样例：

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

和甲级里面的一道题目是一样的。 把链表分成三个部分，小于的一部分，大于0小于等于k的一部分，大于k的一部分。 和前面集体LinkList的处理方式相同，采用5位数的数组来定位数组的地址。

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
#include <cstdio>
#include <vector>

using namespace std;

struct node {
    int first, value, next;
};

vector<node> neg, lesser, greater;

void spit(node *nodes, int first, int k) {
    while (first != -1) {
        if (nodes[first].value < 0) {
            neg.push_back(nodes[first]);
        } else if (nodes[first].value <= k) {
            lesser.push_back(nodes[first]);
        } else {
            greater.push_back(nodes[first]);
        }
        first = nodes[first].next;
    }
}

vector<node> ans;

void merge() {
    ans = neg;
    for (int i = 0; i < lesser.size(); i++) {
        ans.push_back(lesser[i]);
    }
    for (int i = 0; i < greater.size(); i++) {
        ans.push_back(greater[i]);
    }
}

void printAns() {
    int i = 0;
    for (; i < ans.size() - 1; i++) {
        printf("%05d %d %05d\n", ans[i].first, ans[i].value, ans[i + 1].first);
    }
    printf("%05d %d -1\n", ans[i].first, ans[i].value);
}

int main() {
    int first = 0, n = 0, k = 0, temp = 0;
    scanf("%d %d %d", &first, &n, &k);
    node nodes[100000];
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        scanf("%d %d", &nodes[temp].value, &nodes[temp].next);
        nodes[temp].first = temp;
    }
    spit(nodes, first, k);
    merge();
    printAns();

    return 0;
}

Posted on Edited on In

下图是上海某校的新学期开学寄语：天将降大任于斯人也，必先删其微博，卸其QQ，封其电脑，夺其手机，收其ipad，断其wifi，使其百无聊赖，然后，净面、理发、整衣，然后思过、读书、锻炼、明智、开悟、精进。而后必成大器也！

本题要求你写个程序帮助这所学校的老师检查所有学生的物品，以助其成大器。

输入格式：

输入第一行给出两个正整数N（<= 1000）和M（<= 6），分别是学生人数和需要被查缴的物品种类数。第二行给出M个需要被查缴的物品编号，其中编号为4位数字。随后N行，每行给出一位学生的姓名缩写（由1-4个大写英文字母组成）、个人物品数量K（0 <= K <= 10）、以及K个物品的编号。

输出格式：

顺次检查每个学生携带的物品，如果有需要被查缴的物品存在，则按以下格式输出该生的信息和其需要被查缴的物品的信息（注意行末不得有多余空格）：

姓名缩写: 物品编号1 物品编号2 ……

最后一行输出存在问题的学生的总人数和被查缴物品的总数。

输入样例：

4 2
2333 6666
CYLL 3 1234 2345 3456
U 4 9966 6666 8888 6666
GG 2 2333 7777
JJ 3 0012 6666 2333

输出样例：

U: 6666 6666
GG: 2333
JJ: 6666 2333
3 5

循环判断，用一个flag标记是否输出了姓名

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 <algorithm>

using namespace std;

int main() {
    int n = 0, m = 0, temp = 0, k = 0, snum = 0, fnum = 0; // snm is student num, fum is forbid num
    scanf("%d %d", &n, &m);
    bool *forbid = new bool[10000];
    fill(forbid, forbid + 10000, false);
    for (int i = 0; i < m; i++) {
        scanf("%d", &temp);
        forbid[temp] = true;
    }
    for (int i = 0; i < n; i++) {
        char name[10];
        bool flag = false; // is print name?
        scanf("%s %d", name, &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &temp);
            if (forbid[temp]) {
                if (!flag) {
                    printf("%s:", name);
                    flag = true;
                }
                printf(" %04d", temp);
                fnum++;
            }
        }
        if (flag) {
            printf("\n");
            snum++;
        }
    }
    printf("%d %d\n", snum, fnum);
    return 0;
}

Posted on Edited on In

常言道“小赌怡情”。这是一个很简单的小游戏：首先由计算机给出第一个整数；然后玩家下注赌第二个整数将会比第一个数大还是小；玩家下注t个筹码后，计算机给出第二个数。若玩家猜对了，则系统奖励玩家t个筹码；否则扣除玩家t个筹码。 注意：玩家下注的筹码数不能超过自己帐户上拥有的筹码数。当玩家输光了全部筹码后，游戏就结束。 #### 输入格式： 输入在第一行给出2个正整数T和K（<=100），分别是系统在初始状态下赠送给玩家的筹码数、以及需要处理的游戏次数。随后K行，每行对应一次游戏，顺序给出4个数字： n1 b t n2 其中n1和n2是计算机先后给出的两个[0, 9]内的整数，保证两个数字不相等。b为0表示玩家赌“小”，为1表示玩家赌“大”。t表示玩家下注的筹码数，保证在整型范围内。

输出格式：

对每一次游戏，根据下列情况对应输出（其中t是玩家下注量，x是玩家当前持有的筹码量）：

  • 玩家赢，输出“Win t! Total = x.”；
  • 玩家输，输出“Lose t. Total = x.”；
  • 玩家下注超过持有的筹码量，输出“Not enough tokens. Total = x.”；
  • 玩家输光后，输出“Game Over.”并结束程序。

输入样例1：

100 4
8 0 100 2
3 1 50 1
5 1 200 6
7 0 200 8

输出样例1：

Win 100! Total = 200.
Lose 50. Total = 150.
Not enough tokens. Total = 150.
Not enough tokens. Total = 150.

输入样例2：

100 4
8 0 100 2
3 1 200 1
5 1 200 6
7 0 200 8

输出样例2：

Win 100! Total = 200.
Lose 200. Total = 0.
Game Over.

循环，判断。 【注意】看题目描述中的给出的结果和样例输出中给出的结果格式是有差别的。

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
#include <cstdio>

using namespace std;

int main() {
    int T = 0, K = 0, n1 = 0, n2 = 0, b = 0, t = 0;
    scanf("%d %d", &T, &K);
    for (int i = 0; i < K; i++) {
        scanf("%d %d %d %d", &n1, &b, &t, &n2);
        if (T == 0) {
            printf("Game Over.\n");
            return 0;
        } else if (t > T) {
            printf("Not enough tokens.  Total = %d.\n", T);
        } else if (n2 > n1) {
            if (b == 1) {
                T += t;
                printf("Win %d!  Total = %d.\n", t, T);
            } else {
                T -= t;
                printf("Lose %d.  Total = %d.\n", t, T);
            }
        } else if (n2 < n1) {
            if (b == 1) {
                T -= t;
                printf("Lose %d.  Total = %d.\n", t, T);
            } else {
                T += t;
                printf("Win %d!  Total = %d.\n", t, T);
            }
        }
    }
    return 0;
}

Posted on Edited on In

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Now given a graph with several vertex sets, you are supposed to tell if each of them is a vertex cover or not.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 104), being the total numbers of vertices and the edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N-1) of the two ends of the edge. After the graph, a positive integer K (<= 100) is given, which is the number of queries. Then K lines of queries follow, each in the format: Nv v[1] v[2] … v[Nv] where Nv is the number of vertices in the set, and v[i]’s are the indices of the vertices.

Output Specification:

For each query, print in a line “Yes” if the set is a vertex cover, or “No” if not.

Sample Input:

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

Sample Output:

No
Yes
Yes
No
No

结点覆盖的意思是，给一组顶点，判断这组定点能否访问到图中所有的边。 对每一组给出的顶点，对一组定点中的每一个顶点访问它的邻接点，计算访问过的次数，同时把这个顶点标记为已经访问过的，最后得到的访问边的次数不等于题目的m，就是表示没有访问到所有的边。 用邻接矩阵会超内存，用邻接表处理也更方便一些。 代码如下：

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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> vertex;

int bfs(vector<int> v, int n) {
    bool *visit = new bool[n];
    fill(visit, visit + n, false);
    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        vector<int> list = vertex[v[i]];
        visit[v[i]] = true;
        for (int j = 0; j < list.size(); j++) {
            if (!visit[list[j]]) {
                cnt++;
            }
        }
    }
    return cnt;
}

int main() {
    int n = 0, m = 0, a = 0, b = 0, k = 0;
    scanf("%d %d", &n, &m);
    vertex.resize(n);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        vertex[a].push_back(b);
        vertex[b].push_back(a);
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int nv = 0;
        scanf("%d", &nv);
        vector<int> v(nv);
        for (int j = 0; j < nv; j++) {
            scanf("%d", &v[j]);
        }
        if (bfs(v, n) == m) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

Posted on Edited on In

Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N (<= 105) which is the total number of nodes. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1. Then N lines follow, each describes a node in the format: Address Key Next where Address is the position of the node, Key is an integer of which absolute value is no more than 104, and Next is the position of the next node.

Output Specification:

For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

Sample Output:

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

给定一个链链表，把链表中结点的值的绝对值相等的结点移除，最后输出删除后的链表和删除了的链表。

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 <vector>
#include <set>

using namespace std;

struct node {
    int address, key, next;
};

int main() {
    int h = 0, n = 0;
    scanf("%d %d", &h, &n);
    vector<node> v(100000);
    for (int i = 0; i < n; i++) {
        node t;
        scanf("%d %d %d", &t.address, &t.key, &t.next);
        v[t.address] = t;
    }
    vector<node> rs, re; // result and remove
    set<int> s;
    for (int i = 0; i < n; i++) {
        node node = v[h];
        if (s.find(node.key) != s.end() || s.find(-node.key) != s.end()) {
            re.push_back(node);
        } else {
            rs.push_back(node);
            s.insert(node.key);
        }
        h = node.next;
        if (h == -1) {
            break;
        }
    }

    for (int i = 0; i < rs.size(); i++) {
        if (i == rs.size() - 1) printf("%05d %d -1\n", rs[i].address, rs[i].key);
        else printf("%05d %d %05d\n", rs[i].address, rs[i].key, rs[i + 1].address);
    }

    for (int i = 0; i < re.size(); i++) {
        if (i == re.size() - 1) printf("%05d %d -1\n", re[i].address, re[i].key);
        else printf("%05d %d %05d\n", re[i].address, re[i].key, re[i + 1].address);
    }
    return 0;
}
0%