小鲸鱼的梦境
0%

『洛谷』模拟

发表于 分类于 ， Valine：
本文字数： 50k 阅读时长 ≈ 46 分钟

基础算法-模拟

模拟算法就是，题目要求什么你就做什么，主要考察数据结构方面的内容

P1003 [NOIP2011 提高组] 铺地毯

题目描述

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 \(n\) 张地毯，编号从 \(1\) 到 \(n\)。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入格式

输入共 \(n + 2\) 行。

第一行，一个整数 \(n\)，表示总共有 \(n\) 张地毯。

接下来的 \(n\) 行中，第 \(i+1\) 行表示编号 \(i\) 的地毯的信息，包含四个整数 \(a ,b ,g ,k\)，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 \((a, b)\) 以及地毯在 \(x\) 轴和 \(y\) 轴方向的长度。

第 \(n + 2\) 行包含两个整数 \(x\) 和 \(y\)，表示所求的地面的点的坐标 \((x, y)\)。

输出格式

输出共 \(1\) 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。

输入输出样例

输入: #1

1
2
3
4
5
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

输出: #1

1
2
3

输入: #2

1
2
3
4
5
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

输出: #2

1
-1

说明&提示

【样例解释 1】

如下图，\(1\) 号地毯用实线表示，\(2\) 号地毯用虚线表示，\(3\) 号用双实线表示，覆盖点 \((2,2)\) 的最上面一张地毯是 \(3\) 号地毯。

100.png

【数据范围】

对于 \(30\%\) 的数据，有 \(n \le 2\)。
对于 \(50\%\) 的数据，\(0 \le a, b, g, k \le 100\)。
对于 \(100\%\) 的数据，有 \(0 \le n \le 10^4\), \(0 \le a, b, g, k \le {10}^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
#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n, x, y;

    scanf("%d", &n);

    vector<vector<int>> s(n, vector<int>(4, 0));
    for (int i = 0; i < n; ++i) {
        int a, b, g, k;
        scanf("%d%d%d%d", &a, &b, &g, &k);
        s[i][0] = a, s[i][1] = b, s[i][2] = g, s[i][3] = k;
    }

    scanf("%d%d", &x, &y);

    int ans = -1;
    for (int i = 0; i < n; ++i) {
        if (s[i][0] <= x && s[i][1] <= y && s[i][0] + s[i][2] >= x && s[i][1] + s[i][3] >= y)
            ans = i + 1;
    }
    printf("%d", ans);
    return 0;
}
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
import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] s = new int[n][4];
        for (int i = 0; i < n; ++i) {
            s[i][0] = sc.nextInt();
            s[i][1] = sc.nextInt();
            s[i][2] = sc.nextInt();
            s[i][3] = sc.nextInt();
        }
        int x = sc.nextInt(), y = sc.nextInt();
        sc.close();
        System.out.println(new Main().Crapet(s, x, y));
    }

    public int Crapet(int[][] s, int x, int y) {
        for (int i = s.length - 1; i >= 0; --i) {
            if (x >= s[i][0] && y >= s[i][1] && x <= s[i][0] + s[i][2] && y <= s[i][1] + s[i][3])
                return i + 1;
        }
        return -1;
    }
}

P1067 [NOIP2009 普及组] 多项式输出

题目描述

一元\(n\)次多项式可用如下的表达式表示：

26.png

\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,a_n\ne 0\]

其中，\(a_ix^i\)称为\(i\)次项，\(a_i\) 称为\(i\)次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：

  1. 多项式中自变量为$ x$，从左到右按照次数递减顺序给出多项式。

  2. 多项式中只包含系数不为\(0\)的项。

  3. 如果多项式\(n\)次项系数为正，则多项式开头不出现“+”号，如果多项式\(n\)次项系数为负，则多项式以“-”号开头。

  4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于\(0\)次的项，其系数的绝对值为\(1\)，则无需输出 \(1\)）。如果\(x\)的指数大于\(1\)，则接下来紧跟的指数部分的形式为“\(x^b\)”，其中 \(b\) 为 \(x\) 的指数；如果 \(x\) 的指数为\(1\)，则接下来紧跟的指数部分形式为“\(x\)”；如果 \(x\) 的指数为$ 0$，则仅需输出系数即可。

  5. 多项式中，多项式的开头、结尾不含多余的空格。

输入格式

输入共有 \(2\) 行

第一行$ 1$ 个整数，\(n\)，表示一元多项式的次数。

第二行有 $n+1 \(个整数，其中第\) i \(个整数表示第\) n-i+1$ 次项的系数，每两个整数之间用空格隔开。

输出格式

输出共 \(1\) 行，按题目所述格式输出多项式。

输入输出样例

输入: #1

1
2
5 
100 -1 1 -3 0 10

输出: #1

1
100x^5-x^4+x^3-3x^2+10

输入: #2

1
2
3 
-50 0 0 1

输出: #2

1
-50x^3+1

说明&提示

对于100%数据，\(0 \le n \le 100\),$-100 \(系数\) $

解题思路

模拟即可, 分情况讨论即可，一些细节见代码注释

解答代码

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
#include <cstdio>
using namespace std;

int main() {
    int n, a;
    scanf("%d", &n);
    bool first = true;    // 标志是否是输出中的第一项
    for (int i = n; i >= 0; --i) {
        scanf("%d", &a);
        if (a == 0) continue;
        // 系数部分
        if (first) { // 第一项，特殊之处在于正数前面不用加 + 号
            if (a == -1)
                printf("-");
            else if (a != 1)
                printf("%d", a);
            first = false;
        }
        else {
            if (a < 0) {
                if (a != -1)
                    printf("%d", a);
                else
                    printf("-");  // -1 前面只要一个负号也是易忽略的点
            }
            else if (a != 1)
                printf("+%d", a);
            else
                printf("+");
        }
        // 指数部分
        if (i > 1) {
            printf("x^%d", i);
        }
        else if (i == 1) {
            printf("x");
        }
        // 指数为 0 的且系数是 +1, -1 的要补上个 1
        else if (i == 0 && (a == 1 || a == -1))
            printf("1");
    }
    if (first) printf("0");
    return 0;
}
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
import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean first = true; // 标志是否是输出中的第一项
        for (int i = n; i >= 0; --i) {
            int a = sc.nextInt();
            if (a == 0)
                continue;
            // 系数部分
            if (first) { // 第一项，特殊之处在于正数前面不用加 + 号
                if (a == -1)
                    System.out.printf("-");
                else if (a != 1)
                    System.out.printf("%d", a);
                first = false;
            } else {
                if (a < 0) {
                    if (a != -1)
                        System.out.printf("%d", a);
                    else
                        System.out.printf("-"); // -1 前面只要一个负号也是易忽略的点
                } else if (a != 1)
                    System.out.printf("+%d", a);
                else
                    System.out.printf("+");
            }
            // 指数部分
            if (i > 1) {
                System.out.printf("x^%d", i);
            } else if (i == 1) {
                System.out.printf("x");
            }
            // 指数为 0 的且系数是 +1, -1 的要补上个 1
            else if (i == 0 && (a == 1 || a == -1))
                System.out.printf("1");
        }
        if (first)
            System.out.printf("0");
        sc.close();
    }
}

P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布

题目描述

石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一 样，则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上,增加了两个新手势:

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。

1346.png

现在,小 A和小 B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 \(6\) 的周期出拳,那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-......”,而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为 \(5\) 的周期出拳,那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-......”

已知小 A和小 B 一共进行 \(N\) 次猜拳。每一次赢的人得 \(1\) 分，输的得 \(0\) 分；平局两人都得 \(0\) 分。现请你统计 \(N\) 次猜拳结束之后两人的得分。

输入格式

第一行包含三个整数：\(N,N_A,N_B\),分别表示共进行 \(N\) 次猜拳、小 A出拳的周期长度，小 B 出拳的周期长度。数与数之间以一个空格分隔。

第二行包含 \(N_A\) 个整数,表示小 A出拳的规律,第三行包含 \(N_B\) 个整数,表示小 B 出拳的规律。其中，\(0\) 表示“剪刀”，\(1\) 表示“石头”，\(2\) 表示“布”，\(3\) 表示“蜥蜴人”，\(4\) 表示“斯波克”。数与数之间以一个空格分隔。

输出格式

输出一行，包含两个整数，以一个空格分隔，分别表示小 A、小 B的得分.

输入输出样例

输入: #1

1
2
3
10 5 6
0 1 2 3 4
0 3 4 2 1 0

输出: #1

1
6 2

输入: #2

1
2
3
9 5 5
0 1 2 3 4
1 0 3 2 4

输出: #2

1
4 4

说明&提示

对于\(100\%\)的数据，\(0 < N \leq 200, 0 < N_A \leq 200, 0 < N_B \leq 200\) 。

解题思路

没什么技巧，就遍历两人的猜拳过程然后计分即可

一个优化点就是，两人的出拳是周期的，自然胜负也是周期性的，即得分同样具有周期性，不难想到，得分的最小周期即两人出拳周期的最小公倍数，可以由此简化计算，不过本题游戏次数和两人的出拳周期大小相当，所以优化前后效果相差不大，若游戏次数比周期大得多，这个优化就能大大减少计算次数

真值表(a对b的结果，1 表示赢，-1 表示输，0 表示平)

a 0 1 2 3 4
0 0 -1 1 1 -1
1 1 0 -1 1 -1
2 -1 1 0 -1 1
3 -1 -1 1 0 1
4 1 1 -1 -1 0

解答代码

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
#include <cstdio>
using namespace std;

int game(int a, int b) {
    // a 胜利返回 1, b 胜利返回 -1，平局返回 0
    if (a == b)
        return 0;
    else if (a == 0)
        return b == 2 || b == 3 ? 1 : -1;
    else if (a == 1)
        return b == 0 || b == 3 ? 1 : -1;
    else if (a == 2)
        return b == 1 || b == 4 ? 1 : -1;
    else if (a == 3)
        return b == 2 || b == 4 ? 1 : -1;
    else if (a == 4)
        return b == 0 || b == 1 ? 1 : -1;
    else
        return 0;
}

int a[207], b[207];

int main() {
    int n, na, nb, p, q;
    scanf("%d%d%d", &n, &na, &nb);
    int ca = 0, cb = 0;    // 计分
    for (int i = 0; i < na; ++i) {
        scanf("%d", &p);
        a[i] = p;
    }
    for (int i = 0; i < nb; ++i) {
        scanf("%d", &q);
        b[i] = q;
    }
    for (int i = 0; i < n; ++i) {
        int res = game(a[i % na], b[i % nb]);
        if (res == 1) ca++;
        else if (res == -1)
            cb++;
    }
    printf("%d %d\n", ca, cb);
    return 0;
}
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
import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main s = new Main();
        int n = sc.nextInt(), na = sc.nextInt(), nb = sc.nextInt();
        int[] sa = new int[na], sb = new int[nb];
        for (int i = 0; i < na; ++i) {
            sa[i] = sc.nextInt();
        }
        for (int i = 0; i < nb; ++i) {
            sb[i] = sc.nextInt();
        }
        int[] ans = s.game(n, sa, sb);
        System.out.println(ans[0] + " " + ans[1]);
        sc.close();
    }

    int[] game(int n, int[] playerA, int[] playerB) {
        int n1 = playerA.length, n2 = playerB.length;
        int r = lcm(n1, n2);
        int d = n / r, m = n % r;
        int[] score = new int[2];
        for (int i = 0; i < m; ++i) {
            if (playerA[i % n1] == playerB[i % n2])
                continue;
            if (RPSSL(playerA[i % n1], playerB[i % n2]))
                score[0]++;
            else
                score[1]++;
        }
        if (d == 0)
            return score;
        int a = score[0], b = score[1];
        for (int i = m; i < r; ++i) {
            if (playerA[i % n1] == playerB[i % n2])
                continue;
            if (RPSSL(playerA[i % n1], playerB[i % n2]))
                a++;
            else
                b++;
        }
        score[0] += a * d;
        score[1] += b * d;
        return score;
    }

    boolean RPSSL(int a, int b) {
        // a 胜利返回 true, b 胜利返回 false
        if (a == 0)
            return b == 2 || b == 3 ? true : false;
        else if (a == 1)
            return b == 0 || b == 3 ? true : false;
        else if (a == 2)
            return b == 1 || b == 4 ? true : false;
        else if (a == 3)
            return b == 2 || b == 4 ? true : false;
        else if (a == 4)
            return b == 0 || b == 1 ? true : false;
        else
            return false;
    }

    int gcd(int a, int b) {
        // 计算两个数的最大公约数
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

    int lcm(int a, int b) {
        // 计算两个数的最小公倍数
        int g = gcd(a, b);
        return g * (a / g) * (b / g);
    }
}

下面这个py代码本地运行两个示例都能通过，但不知道为什么洛谷会报错，也不给错误信息，就提示 RE，我也不知道哪出问题了（逐行debug发现，math库 的 lcm 是 Python 3.9 版本的功能，洛谷的Python版本较低）, Python 3.9 原版的代码注释掉了，修改后的代码可以通过测试

当然，为了写法上的方便性稍微牺牲了一点效率，但不影响时空复杂度，例如四个 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
30
31
32
33
# from math import lcm
from math import gcd

def game(a: int, b: int) -> int:
    # a 胜利返回 1, b 胜利返回 -1，平局返回 0
    if a == b:
        return 0
    elif a == 0:
        return 1 if b == 2 or b == 3 else -1
    elif a == 1:
        return 1 if b == 0 or b == 3 else -1
    elif a == 2:
        return 1 if b == 1 or b == 4 else -1
    elif a == 3:
        return 1 if b == 2 or b == 4 else -1
    elif a == 4:
        return 1 if b == 0 or b == 1 else -1
    else:
        return 0

n, na, nb = map(int, input().split())

# r = lcm(na, nb)
g = gcd(na, nb)
r = g * (na // g) * (nb // g)

a, b = list(map(int, input().split())) * (r // na), list(map(int, input().split())) * (r // nb)
tim, k = divmod(n, r)
sa = sum((1 for x, y in zip(a, b) if game(x, y) == 1))
sb = sum((1 for x, y in zip(a, b) if game(x, y) == -1))
ca = sum((1 for x, y, _ in zip(a, b, range(k)) if game(x, y) == 1))
cb = sum((1 for x, y, _ in zip(a, b, range(k)) if game(x, y) == -1))
print("{} {}".format(sa * tim + ca, sb * tim + cb))

P1563 [NOIP2016 提高组] 玩具谜题

题目描述

小南有一套可爱的玩具小人, 它们各有不同的职业。

有一天, 这些玩具小人把小南的眼镜藏了起来。 小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:

0u7em9pi.png

这时\(singer\)告诉小南一个谜題: “眼镜藏在我左数第3个玩具小人的右数第\(1\)个玩具小人的左数第\(2\)个玩具小人那里。 ”

小南发现, 这个谜题中玩具小人的朝向非常关键, 因为朝内和朝外的玩具小人的左右方向是相反的: 面朝圈内的玩具小人, 它的左边是顺时针方向, 右边是逆时针方向; 而面向圈外的玩具小人, 它的左边是逆时针方向, 右边是顺时针方向。

小南一边艰难地辨认着玩具小人, 一边数着:

\(singer\)朝内, 左数第\(3\)个是\(archer\)。

\(archer\)朝外,右数第\(1\)个是\(thinker\)。

\(thinker\)朝外, 左数第\(2\)个是\(write\)r。

所以眼镜藏在\(writer\)这里!

虽然成功找回了眼镜, 但小南并没有放心。 如果下次有更多的玩具小人藏他的眼镜, 或是谜題的长度更长, 他可能就无法找到眼镜了 。 所以小南希望你写程序帮他解决类似的谜題。 这样的谜題具体可以描述为:

有 \(n\)个玩具小人围成一圈, 已知它们的职业和朝向。现在第\(1\)个玩具小人告诉小南一个包含\(m\)条指令的谜題, 其中第 \(z\)条指令形如“左数/右数第$ s$,个玩具小人”。 你需要输出依次数完这些指令后,到达的玩具小人的职业。

输入格式

输入的第一行包含两个正整数 \(n,m\)，表示玩具小人的个数和指令的条数。

接下来 \(n\) 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中 \(0\) 表示朝向圈内，\(1\) 表示朝向圈外。 保证不会出现其他的数。字符串长度不超过 \(10\) 且仅由小写字母构成，字符串不为空，并且字符串两两不同。整数和字符串之间用一个空格隔开。

接下来 \(m\) 行，其中第 \(i\) 行包含两个整数 \(a_i,s_i\)，表示第 \(i\) 条指令。若 \(a_i=0\)，表示向左数 \(s_i\) 个人；若 \(a_i=1\)，表示向右数 \(s_i\) 个人。 保证 \(a_i\) 不会出现其他的数，\(1 \le s_i < n\)。

输出格式

输出一个字符串，表示从第一个读入的小人开始，依次数完 \(m\) 条指令后到达的小人的职业。

输入输出样例

输入: #1

1
2
3
4
5
6
7
8
9
10
11
7 3
0 singer
0 reader
0 mengbier 
1 thinker
1 archer
0 writer
1 mogician 
0 3
1 1
0 2

输出: #1

1
writer

输入: #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4

输出: #2

1
y

说明&提示

【样例1说明】

这组数据就是【题目描述】 中提到的例子。

【子任务】

子任务会给出部分测试数据的特点。 如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表:

3439.png

其中一些简写的列意义如下:

• 全朝内: 若为“√”, 表示该测试点保证所有的玩具小人都朝向圈内;

全左数:若为“√”,表示该测试点保证所有的指令都向左数,即对任意的

\(1≤z≤m, a_i=0\);

\(s= 1\):若为“√”,表示该测试点保证所有的指令都只数1个,即对任意的

\(1≤z≤m,s_i=1\);

职业长度为\(1\) :若为“√”,表示该测试点保证所有玩具小人的职业一定是一个

长度为\(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
#include <bits/stdc++.h>
using namespace std;

int n, m;
int dir[100007];
string prof[100007];

int next(int cur, int d, int dir, int i) {
    // 当前位置 cur, 小人朝向 d, 方向 dir, 第 i 个
    // 小人位置在数组中是逆时针的，所以逆序是顺时针方向
    // d = 0 表示朝向圈内（左顺右逆），d = 1 表示朝向圈外（左逆右顺）
    // dir = 0 表示向左数，dir = 1 表示向右数
    // 返回执行完一次指令后的位置下标
    if (d == 1)
        dir = 1 - dir;    // 统一朝向方便讨论
    if (dir == 0)
        return (cur - i + n) % n;
    else
        return (cur + i) % n;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> dir[i] >> prof[i];
    }
    int d, s, cur = 0;
    for (int i = 0; i < m; ++i) {
        cin >> d >> s;
        cur = next(cur, dir[cur], d, s);
    }
    cout << prof[cur] << "\n";
    return 0;
}
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
import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        Main s = new Main(n);
        int[] dir = new int[n]; // Direction
        String[] prof = new String[n]; // profession
        for (int i = 0; i < n; ++i) {
            dir[i] = sc.nextInt();
            prof[i] = sc.next();
        }
        int cur = 0;
        for (int i = 0; i < m; ++i) {
            cur = s.next(cur, dir[cur], sc.nextInt(), sc.nextInt());
        }
        System.out.println(prof[cur]);
        sc.close();
    }

    public int n;

    public Main(int n) {
        this.n = n;
    }
    
    public int next(int cur, int d, int dir, int i) {
        // 当前位置 cur, 小人朝向 d, 方向 dir, 第 i 个
        // 小人位置在数组中是逆时针的，所以逆序是顺时针方向
        // d = 0 表示朝向圈内（左顺右逆），d = 1 表示朝向圈外（左逆右顺）
        // dir = 0 表示向左数，dir = 1 表示向右数
        // 返回执行完一次指令后的位置下标
        if (d == 1)
            dir = 1 - dir; // 统一朝向方便讨论
        if (dir == 0)
            return (cur - i + n) % n;
        else
            return (cur + i) % n;
    }
}

P1042 [NOIP2003 普及组] 乒乓球

题目描述

国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中 \(11\) 分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白 \(11\) 分制和 \(21\) 分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。

华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在 \(11\) 分制和 \(21\) 分制下，双方的比赛结果（截至记录末尾）。

比如现在有这么一份记录，（其中 \(\texttt W\) 表示华华获得一分，\(\texttt L\) 表示华华对手获得一分）：

\(\texttt{WWWWWWWWWWWWWWWWWWWWWWLW}\)

在 \(11\) 分制下，此时比赛的结果是华华第一局 \(11\) 比 \(0\) 获胜，第二局 \(11\) 比 \(0\) 获胜，正在进行第三局，当前比分 \(1\) 比 \(1\)。而在 \(21\) 分制下，此时比赛结果是华华第一局 \(21\) 比 \(0\) 获胜，正在进行第二局，比分 \(2\) 比 \(1\)。如果一局比赛刚开始，则此时比分为 \(0\) 比 \(0\)。直到分差大于或者等于 \(2\)，才一局结束。

你的程序就是要对于一系列比赛信息的输入（\(\texttt{WL}\) 形式），输出正确的结果。

输入格式

每个输入文件包含若干行字符串，字符串有大写的 \(\texttt W\) 、 \(\texttt L\) 和 \(\texttt E\) 组成。其中 \(\texttt E\) 表示比赛信息结束，程序应该忽略 \(\texttt E\) 之后的所有内容。

输出格式

输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是 \(11\) 分制下的结果，第二部分是 \(21\) 分制下的结果，两部分之间由一个空行分隔。

输入输出样例

输入: #1

1
2
WWWWWWWWWWWWWWWWWWWW
WWLWE

输出: #1

1
2
3
4
5
6
11:0
11:0
1:1

21:0
2:1

说明&提示

每行至多 \(25\) 个字母，最多有 \(2500\) 行。

解题思路

对输入分别计算两种分制下的结果即可, 另外，题目有点描述得不是特别清楚，并不是比赛 11 或 21 局就结束，而是比赛有人达到 11 分且两人分数差大于等于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
#include <cstdio>
using namespace std;

int s1[7007], s2[7007];    // 存放 21 分制的结果

int main() {
    int a = 0, b = 0;
    int c = 0, d = 0;
    int i = 0;
    char s;
    bool p1 = true, p2 = true;
    while (true) {
        s = getchar();
        p1 = true;
        p2 = true;
        if (s == 'E')
            break;
        else if (s == 'W') {
            a++, c++;
        }
        else if (s == 'L') {
            b++, d++;
        }
        if ((a >= 11 && a - b >= 2) || (b >= 11 && b - a >= 2)) {
            printf("%d:%d\n", a, b);
            a = 0;
            b = 0;
            p1 = false;
        }
        if ((c >= 21 && c - d >= 2) || (d >= 21 && d - c >= 2)) {
            s1[i] = c;
            s2[i++] = d;
            c = 0;
            d = 0;
            p2 = false;
        }
    }
    if (a + b != 0 || p1) {
        printf("%d:%d\n", a, b);
    }
    putchar('\n');
    for (int j = 0; j < i; ++j) {
        printf("%d:%d\n", s1[j], s2[j]);
    }
    if (c + d != 0 || p2)
        printf("%d:%d\n", c, d);
    return 0;
}

P1179 [NOIP2010 普及组] 数字统计

题目描述

请统计某个给定范围\([L, R]\)的所有整数中，数字 \(2\) 出现的次数。

比如给定范围\([2, 22]\)，数字$ 2$ 在数 \(2\) 中出现了 \(1\) 次，在数 \(12\) 中出现 \(1\) 次，在数 \(20\) 中出现 \(1\) 次，在数 21 中出现 \(1\) 次，在数 \(22\) 中出现 \(2\) 次，所以数字 \(2\) 在该范围内一共出现了 \(6\) 次。

输入格式

\(2\) 个正整数 \(L\) 和 \(R\)，之间用一个空格隔开。

输出格式

数字 $2 $出现的次数。

输入输出样例

输入: #1

1
2 22

输出: #1

1
6

说明&提示

\(1 ≤ L ≤R≤ 100000\)。

解题思路

前面有题类似的，也是数位dp

当然也可以模拟解法，遍历所有数字统计

解答代码

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
#include <cstdio>
using namespace std;
// 数据范围
const int N = 17;
typedef long long ll;
ll l, r, dp[N], mi[N];
int a[N];

inline ll Count(ll n, int k) {
    ll tmp = n, ans = 0;
    int len = 0;
    // 拆开 n 各位上的数存入 a 中
    while (n) a[++len] = n % 10, n /= 10;
    // 由高位向低位枚举
    for (int i = len; i >= 1; --i) {
        ans += dp[i - 1] * a[i];
        if (k < a[i]) ans += mi[i - 1];
        tmp -= mi[i - 1] * a[i];
        if (k == a[i]) ans += tmp + 1;
        if (k == 0) ans -= mi[i - 1];
    }
    return ans;
}

inline ll CountProblem(ll start, ll end, int k) {
    // 统计 [start, end] 范围内 0 ~ 9 出现次数，存于数组 ans 中
    return Count(end, k) - Count(start - 1, k);
}

int main() {
    scanf("%lld%lld", &l, &r);
    mi[0] = 1ll;
    for (int i = 1; i < N; ++i) {
        dp[i] = dp[i - 1] * 10 + mi[i - 1];
        mi[i] = 10ll * mi[i - 1];
    }
    printf("%lld ", CountProblem(l, r, 2));
    return 0;
}
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
import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long start = sc.nextLong(), end = sc.nextLong();
        sc.close();
        System.out.print(new Main().CountProblem(start, end, 2) + " ");
        System.out.println();
    }

    // dp[i] 表示 满 i 位中各个数码出现次数（9……9 (i个9) 中 k(=0~9) 出现次数）
    // base[i] = 10 ^ i
    private static int N = 17;
    private static long[] dp, base;
    static {
        dp = new long[N];
        base = new long[N];
        base[0] = 1;
        for (int i = 1; i < N; ++i) {
            // dp[i] = 10 * dp[i - 1] + 10 ^(i - 1)
            // 表示 前 i - 1 位的次数 + 第 i 位的出现次数
            dp[i] = dp[i - 1] * 10 + base[i - 1];
            base[i] = base[i - 1] * 10;
        }
    }

    private long Count(long n, int s) {
        long ans = 0;
        int[] num = new int[N];
        long k = n;
        // 拆开 n 各位上的数存入 数组中
        int i = 0;
        while (n != 0) {
            num[++i] = (int) (n % 10);
            n /= 10;
        }
        for (; i >= 1; --i) {
            ans += dp[i - 1] * num[i];
            if (s < num[i])
                ans += base[i - 1];
            k -= base[i - 1] * num[i];
            if (s == num[i])
                ans += k + 1;
            if (s == 0)
                ans -= base[i - 1];
        }
        return ans;
    }

    public long CountProblem(long start, long end, int k) {
        return Count(end, k) - Count(start - 1, k);
    }
}

模拟解法：

1
2
3
4
5
def CountProblem(start: int, end: int, k: int) -> int:
    """统计 k 在范围 [start,end] 的出现次数"""
    return sum((str(i).count('2') for i in range(start, end + 1)))

print(CountProblem(*map(int, input().split()), 2))

P2615 [NOIP2015 提高组] 神奇的幻方

题目描述

题目描述 幻方是一种很神奇的 \(N*N\) 矩阵：它由数字 \(1,2,3,\cdots \cdots ,N \times N\) 构成，且每行、每列及两条对角线上的数字之和都相同。

当 \(N\) 为奇数时，我们可以通过下方法构建一个幻方：

首先将 \(1\) 写在第一行的中间。

之后，按如下方式从小到大依次填写每个数 \(K (K=2,3,\cdots,N \times N)\) ：

  1. 若 \((K-1)\) 在第一行但不在最后一列，则将 \(K\) 填在最后一行， \((K-1)\) 所在列的右一列；
  2. 若 \((K-1)\) 在最后一列但不在第一行，则将 \(K\) 填在第一列， \((K-1)\) 所在行的上一行；
  3. 若 \((K-1)\) 在第一行最后一列，则将 \(K\) 填在 \((K-1)\) 的正下方；
  4. 若 \((K-1)\) 既不在第一行，也不在最后一列，如果 \((K-1)\) 的右上方还未填数，则将 \(K\) 填在 \((K-1)\) 的右上方，否则将 \(K\) 填在 \((K-1)\) 的正下方。

现给定 \(N\) ，请按上述方法构造 \(N \times N\) 的幻方。

输入格式

一个正整数 \(N\) ，即幻方的大小。

输出格式

共 \(N\) 行 ，每行 \(N\) 个整数，即按上述方法构造出的 \(N \times N\) 的幻方，相邻两个整数之间用单空格隔开。

输入输出样例

输入: #1

1
3

输出: #1

1
2
3
8 1 6
3 5 7
4 9 2

输入: #2

1
25

输出: #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
327 354 381 408 435 462 489 516 543 570 597 624 1 28 55 82 109 136 163 190 217 244 271 298 325
353 380 407 434 461 488 515 542 569 596 623 25 27 54 81 108 135 162 189 216 243 270 297 324 326
379 406 433 460 487 514 541 568 595 622 24 26 53 80 107 134 161 188 215 242 269 296 323 350 352
405 432 459 486 513 540 567 594 621 23 50 52 79 106 133 160 187 214 241 268 295 322 349 351 378
431 458 485 512 539 566 593 620 22 49 51 78 105 132 159 186 213 240 267 294 321 348 375 377 404
457 484 511 538 565 592 619 21 48 75 77 104 131 158 185 212 239 266 293 320 347 374 376 403 430
483 510 537 564 591 618 20 47 74 76 103 130 157 184 211 238 265 292 319 346 373 400 402 429 456
509 536 563 590 617 19 46 73 100 102 129 156 183 210 237 264 291 318 345 372 399 401 428 455 482
535 562 589 616 18 45 72 99 101 128 155 182 209 236 263 290 317 344 371 398 425 427 454 481 508
561 588 615 17 44 71 98 125 127 154 181 208 235 262 289 316 343 370 397 424 426 453 480 507 534
587 614 16 43 70 97 124 126 153 180 207 234 261 288 315 342 369 396 423 450 452 479 506 533 560
613 15 42 69 96 123 150 152 179 206 233 260 287 314 341 368 395 422 449 451 478 505 532 559 586
14 41 68 95 122 149 151 178 205 232 259 286 313 340 367 394 421 448 475 477 504 531 558 585 612
40 67 94 121 148 175 177 204 231 258 285 312 339 366 393 420 447 474 476 503 530 557 584 611 13
66 93 120 147 174 176 203 230 257 284 311 338 365 392 419 446 473 500 502 529 556 583 610 12 39
92 119 146 173 200 202 229 256 283 310 337 364 391 418 445 472 499 501 528 555 582 609 11 38 65
118 145 172 199 201 228 255 282 309 336 363 390 417 444 471 498 525 527 554 581 608 10 37 64 91
144 171 198 225 227 254 281 308 335 362 389 416 443 470 497 524 526 553 580 607 9 36 63 90 117
170 197 224 226 253 280 307 334 361 388 415 442 469 496 523 550 552 579 606 8 35 62 89 116 143
196 223 250 252 279 306 333 360 387 414 441 468 495 522 549 551 578 605 7 34 61 88 115 142 169
222 249 251 278 305 332 359 386 413 440 467 494 521 548 575 577 604 6 33 60 87 114 141 168 195
248 275 277 304 331 358 385 412 439 466 493 520 547 574 576 603 5 32 59 86 113 140 167 194 221
274 276 303 330 357 384 411 438 465 492 519 546 573 600 602 4 31 58 85 112 139 166 193 220 247
300 302 329 356 383 410 437 464 491 518 545 572 599 601 3 30 57 84 111 138 165 192 219 246 273
301 328 355 382 409 436 463 490 517 544 571 598 625 2 29 56 83 110 137 164 191 218 245 272 299

说明&提示

对于\(100\%\)的数据，对于全部数据， \(1 \leq N \leq 39\) 且 \(N\) 为奇数。

解题思路

按题意模拟即可

方法二：公式法，从评论区学习到的，其实没那么复杂，将条件归纳总结，其实就一步：对当前位置，若右上(即 \((x - 1, y + 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
#include <cstdio>
using namespace std;
const int N = 41;
int Magic[N][N];

inline void setMagic(int n) {
    int ed = n * n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            Magic[i][j] = 0;
    int x = 0, y = n >> 1;
    Magic[x][y] = 1;
    for (int i = 2; i <= ed; ++i) {
        if (x == 0 && y != n - 1)
            x = n - 1, y++;
        else if (y == n - 1 && x != 0)
            x--, y = 0;
        else if (x == 0 && y == n - 1)
            x++;
        else {
            if (Magic[x - 1][y + 1] == 0)
                x--, y++;
            else
                x++;
        }
        Magic[x][y] = i;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    setMagic(n);
    for (int i = 0; i < n; ++i) {
        printf("%d", Magic[i][0]);
        for (int j = 1; j < n; ++j)
            printf(" %d", Magic[i][j]);
        putchar('\n');
    }
    return 0;
}

公式法

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
import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        int[][] Magic = new int[n][n];
        int ed = n * n;

        for (int i = 1, x = 0, y = n >> 1; i <= ed; ++i) {
            Magic[x][y] = i;
            if (Magic[(x + n - 1) % n][(y + 1) % n] != 0) 
                x = (x + 1) % n;
            else {
                x = (x + n - 1) % n;
                y = (y + 1) % n;
            }
        }
        for (int i = 0; i < n; ++i) {
            System.out.printf("%d", Magic[i][0]);
            for (int j = 1; j < n; ++j)
                System.out.printf(" %d", Magic[i][j]);
            System.out.println();
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
Magic = [[0 for _ in range(n)] for _ in range(n)]
x, y = 0, n >> 1
for i in range(1, n * n + 1):
    Magic[x][y] = i
    if Magic[(x + n - 1) % n][(y + 1) % n]:
        x, y = (x + 1) % n, y
    else:
        x, y = (x + n - 1) % n, (y + 1) % n

for x in Magic:
    for y in x:
        print(y, end=" ")
    print()

P3952 [NOIP2017 提高组] 时间复杂度

题目描述

小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序， 于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下：

1
2
3
F i x y
    循环体
E

其中F i x y表示新建变量 \(i\)（变量 \(i\) 不可与未被销毁的变量重名）并初始化为 \(x\)， 然后判断 \(i\) 和 \(y\) 的大小关系，若 \(i\) 小于等于 \(y\) 则进入循环，否则不进入。每次循环结束后 \(i\) 都会被修改成 \(i +1\)，一旦 \(i\) 大于 \(y\) 终止循环。

\(x\) 和 \(y\) 可以是正整数（\(x\) 和 \(y\) 的大小关系不定）或变量 \(n\)。\(n\) 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 \(100\)。

E 表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

注：本题中为了书写方便，在描述复杂度时，使用大写英文字母 \(\operatorname O\) 表示通常意义下 \(Θ\) 的概念。

输入格式

输入文件第一行一个正整数 \(t\)，表示有 \(t\)（\(t \le 10\)）个程序需要计算时间复杂度。 每个程序我们只需抽取其中 F i x y 和 E 即可计算时间复杂度。注意：循环结构允许嵌套。

接下来每个程序的第一行包含一个正整数 \(L\) 和一个字符串，\(L\) 代表程序行数，字符串表示这个程序的复杂度，O(1) 表示常数复杂度，O(n^w) 表示复杂度为 \(n^w\)，其中 \(w\) 是一个小于 \(100\) 的正整数，输入保证复杂度只有 O(1) 和 O(n^w) 两种类型。

接下来 \(L\) 行代表程序中循环结构中的F i x y或者 E。 程序行若以F开头，表示进入一个循环，之后有空格分离的三个字符（串）i x y， 其中 \(i\) 是一个小写字母（保证不为\(n\)），表示新建的变量名，\(x\) 和 \(y\) 可能是正整数或 \(n\) ，已知若为正整数则一定小于 \(100\)。

程序行若以E开头，则表示循环体结束。

输出格式

输出文件共 \(t\) 行，对应输入的 \(t\) 个程序，每行输出 Yes 或 No 或者 ERR，若程序实际复杂度与输入给出的复杂度一致则输出 Yes，不一致则输出 No，若程序有语法错误（其中语法错误只有: ① F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出 ERR。

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。

输入输出样例

输入: #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
8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

输出: #1

1
2
3
4
5
6
7
8
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

说明&提示

【输入输出样例解释 \(1\)】

第一个程序 \(i\) 从 \(1\) 到 \(1\) 是常数复杂度。

第二个程序 \(x\) 从 \(1\) 到 \(n\) 是 \(n\) 的一次方的复杂度。

第三个程序有一个 F 开启循环却没有 E 结束，语法错误。

第四个程序二重循环，\(n\) 的平方的复杂度。

第五个程序两个一重循环，\(n\) 的一次方的复杂度。

第六个程序第一重循环正常，但第二重循环开始即终止（因为 \(n\) 远大于 \(100\)，\(100\) 大于 \(4\)）。

第七个程序第一重循环无法进入，故为常数复杂度。

第八个程序第二重循环中的变量 \(x\) 与第一重循环中的变量重复，出现语法错误②，输出 ERR。

【数据规模与约定】

对于 \(30\%\) 的数据：不存在语法错误，数据保证小明给出的每个程序的前 \(L/2\) 行一定为以 F 开头的语句，第 \(L/2+1\) 行至第 \(L\) 行一定为以 E 开头的语句，\(L \le 10\)，若 \(x\)、\(y\) 均为整数，\(x\) 一定小于 \(y\)，且只有 \(y\) 有可能为 \(n\)。

对于 \(50\%\) 的数据：不存在语法错误，\(L \le 100\)，且若 \(x\)、\(y\) 均为整数，\(x\) 一定小于 \(y\)， 且只有 \(y\) 有可能为 \(n\)。

对于 \(70\%\) 的数据：不存在语法错误，\(L \le 100\)。

对于 \(100\%\) 的数据：\(L \le 100\)。

解题思路

模拟题中的大题，实话说，思路简单但实现相当复杂，评论区一众调了好几个小时，十多个小时才调好的

有两个要求

  1. 判断程序是否有误，对于 \(F\) 与 \(E\) 是否匹配，使用栈是很自然的思路了，对于有无重复变量，进入栈中遍历检查即可
  2. 复杂度的计算，取决于循环的嵌套和循环的执行次数

有在线和离线两种做法

  • 离线做法：先把代码用字符串数组保存下来在做检查计算
  • 在线做法：边读入代码边计算

毫无疑问离线做法比在线做法更简单

解答代码

在线做法，37-46-82-100，提交了 4 次才通过全部 11 个用例，代码中有相当一部分是在线IDE调试时的打印内容，可以无视掉（main中的已经注释掉了），前三次失败提交的问题如下：

  1. 常数复杂度的循环没有更新对应栈中的复杂度，导致后序的复杂度计算错误，解决方法是该情况下复制前一个对象中保存的复杂度
  2. 栈空的情况下复杂度的更新会出错（因为依赖于栈顶元素的前一个计算，而且数组越界不会报错），解决方法是特判栈空的情况；循环过程中栈中元素没有重置为默认值，导致结点的 start, ed 变量依靠是否为初值来判断更新与否的地方不会执行更新，使得除第一次查询外的后序检查大多失效，解决方法是在循环开始将两变量恢复到默认值
  3. 循环执行一次也是常数复杂度而非无效循环，多了个等于号，去掉即可
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;    // 设为 n 的大小（无穷）

class loop {    // 栈结点，记录遍历名，循环起点和终点、当前复杂度
public:
    char var = '#';
    int start = -1, ed = -1;
    int comp;
};

int n, L;         // 程序数量、程序行数
int state = 1;    // 0 表示错误，返回 ERR，1 表示正常循环
int inv = -1;     // 记录 不会循环的层数 在栈中的位置
string s, comp, start, ed;
char var;
loop st[27];    // 存放变量名的栈
int p = -1;     // 栈顶指针，指向栈中栈顶元素
int w = 0;      // 计算得到的时间复杂度的指数

inline int str2int(string s) {
    int ans = 0;
    for (char v : s) ans = ans * 10 + (v - '0');
    return ans;
}

inline void printstack(int p) {
    // 输出栈内容，p 是栈顶指针
    cout << "---Begin print stack---\n";
    for (int i = 0; i <= p; ++i) {
        cout << "var = " << st[i].var << " start = " << st[i].start << " ed = " << st[i].ed << " comp = " << st[i].comp << "\n";
    }
    cout << "------end print------\n";
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> L >> comp;
        // cout << "L = " << L << " comp = " << comp << '\n';
        p = -1, state = 1, w = 0, inv = -1;    // 初始化栈顶指针、状态和复杂度
        // printstack(5);
        for (int j = 0; j < L; ++j) {
            cin >> s;
            // 有错误的程序直接读完程序后面的内容就可以了
            if (state == 0) {
                if (s == "F") cin >> var >> start >> ed;
                continue;
            }
            if (s == "F") {
                // s, var, start, ed 分别表示，循环标准 F, 变量名，循环起点，循环终点
                cin >> var >> start >> ed;
                // cout << s << " " << var << " " << start << " " << ed << '\n';
                st[++p].var = var;    // 变量名压栈
                st[p].start = -1, st[p].ed = -1;
                for (int i = 0; i < p; ++i) {    // 遍历栈检查是否有重复变量名
                    if (st[i].var == var) {
                        state = 0;
                        goto endloop;
                    }
                    if (st[i].var == start[0]) st[p].start = st[i].start;
                    if (st[i].var == ed[0]) st[p].ed = st[i].ed;
                }
                if (start == "n") st[p].start = INF;
                if (ed == "n") st[p].ed = INF;
                if (st[p].start == -1) st[p].start = str2int(start);
                if (st[p].ed == -1) st[p].ed = str2int(ed);
                if (st[p].ed < st[p].start) inv = p;    // 循环终点比循环起点低即无效
                if (st[p].ed - st[p].start > 200 && inv == -1) {
                    st[p].comp = p == 0 ? 1 : (st[p - 1].comp + 1);
                    w = max(st[p].comp, w);
                }
                else
                    st[p].comp = p == 0 ? 0 : (st[p - 1].comp);
                // printstack(p);
            }
            else {    // s == E
                // cout << s << "\n";
                if (p == inv) inv = -1;      // 退出 不执行的循环
                if (p-- == -1) state = 0;    // F 与 E 不匹配也将状态设为 0
            }
        endloop:
            continue;
        }
        // 栈非空和状态为 0 都表示程序有语法错误
        if (state == 0 || p != -1)
            printf("ERR\n");
        else if (w == 0) {
            // cout << "comp = " << comp << "  w = " << w << "\n";
            if (comp == "O(1)")
                printf("Yes\n");
            else
                printf("No\n");
        }
        else {
            // cout << "comp = " << comp << "  w = " << w << "\n";
            if (comp == "O(n^" + to_string(w) + ")")
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

P2482 [SDOI2010]猪国杀

题目描述

游戏背景

《猪国杀》是一种多猪牌类回合制游戏，一共有 \(3\) 种角色：主猪，忠猪，反猪。每局游戏主猪有且只有 \(1\) 只，忠猪和反猪可以有多只，每只猪扮演 $1 $ 种角色。

游戏目的

主猪 / \(\texttt{MP}\)：自己存活的情况下消灭所有的反猪。
忠猪 / \(\texttt{ZP}\)：不惜一切保护主猪，胜利条件与主猪相同。
反猪 / \(\texttt{FP}\)：杀死主猪。

游戏过程

游戏开始时，每个玩家手里都会有 \(4\) 张牌，且体力上限和初始体力都是 \(4\) 。

开始游戏时，从主猪开始，按照逆时针方向（数据中就是按照编号从 $ 1 , 2, 3 n , 1 $ 的顺序）依次行动。

每个玩家自己的回合可以分为 2 个阶段：

  • 摸牌阶段：从牌堆顶部摸 \(2\) 张牌，依次放到手牌的最右边；
  • 出牌阶段：你可以使用任意张牌，每次使用牌的时候都使用最靠左的能够使用的牌。当然，要满足如下规则：
    1. 如果没有猪哥连弩，每个出牌阶段只能使用 \(1\) 次「杀」来攻击；
    2. 任何牌被使用后被弃置（武器是装备上）；被弃置的牌以后都不能再用，即与游戏无关。

各种牌介绍

每张手牌用 \(1\) 个字母表示，字母代表牌的种类。

基本牌

  • 『桃 / \(\texttt{P}\)』在自己的回合内，如果自己的体力值不等于体力上限，那么使用 \(1\) 个桃可以为自己补充 \(1\) 点体力，否则不能使用桃；桃只能对自己使用；在自己的回合外，如果自己的血变为 \(0\) 或者更低，那么也可以使用。

  • 『杀 / \(\texttt{K}\)』在自己的回合内，对攻击范围内除自己以外的 \(1\) 名角色使用。如果没有被『闪』抵消，则造成 \(1\) 点伤害。无论有无武器，杀的攻击范围都是 \(1\)。

  • 『闪 / \(\texttt{D}\)』当你受到杀的攻击时，可以弃置 \(1\) 张闪来抵消杀的效果。

锦囊牌

  • 『决斗 / \(\texttt{F}\)』出牌阶段，对除自己以外任意 \(1\) 名角色使用，由目标角色先开始，自己和目标角色轮流弃置 \(1\) 张杀，首先没有杀可弃的一方受到 \(1\) 点伤害，另一方视为此伤害的来源。

  • 『南猪入侵 / \(\texttt{N}\)』出牌阶段，对除你以外所有角色使用，按逆时针顺序从使用者下家开始依次结算，除非弃置 \(1\) 张杀，否则受到 \(1\) 点伤害。

  • 『万箭齐发 / \(\texttt{W}\)』和南猪入侵类似，不过要弃置的不是杀而是闪。

  • 『无懈可击 / \(\texttt{J}\)』在目标锦囊生效前抵消其效果。每次有 \(1\) 张锦囊即将生效时，从使用这张锦囊的猪开始，按照逆时针顺序，依次得到使用无懈可击的机会；效果：用于决斗时，决斗无效并弃置；用于南猪入侵或万箭齐发时，当结算到某个角色时才能使用，当前角色不需弃置牌并且不会受到伤害（仅对 \(1\) 个角色产生效果）；用于无懈可击时，成为目标的无懈可击被无效。

装备牌

  • 『猪哥连弩 / \(\texttt{Z}\)』武器，攻击范围 \(1\) ，出牌阶段你可以使用任意张杀; 同一时刻最多只能装 \(1\) 把武器；如果先前已经有了 \(1\) 把武器，那么之后再装武器的话，会弃置以前的武器来装现在的武器。

特殊事件及概念解释

  • 伤害来源：杀、南猪入侵、万箭齐发的伤害来源均是使用该牌的猪，决斗的伤害来源如上；

  • 距离：两只猪的距离定义为沿着逆时针方向间隔的猪数 \(+1\) 。即初始时 \(1\) 和 \(2\) 的距离为 \(1\) ，但是 \(2\) 和 \(1\) 的距离就是 \(n-1\) 。注意一个角色的死亡会导致一些猪距离的改变；

  • 玩家死亡：如果该玩家的体力降到 \(0\) 或者更低，并且自己手中没有足够的桃使得自己的体力值回到 \(1\) ，那么就死亡了，死亡后所有的牌（装备区，手牌区）被弃置；

  • 奖励与惩罚：反猪死亡时，最后一个伤害来源处（即使是反猪）立即摸 \(3\) 张牌。忠猪死亡时，如果最后一个伤害来源是主猪，那么主猪所有装备牌、手牌被弃置。

注意：一旦达成胜利条件，游戏立刻结束，因此即使会摸 \(3\) 张牌或者还有牌可以用也不用执行了。

现在，我们已经知道每只猪的角色、手牌，还有牌堆初始情况，并且假设每个角色会按照如下的行为准则进行游戏，你需要做的就是告诉小猪 iPig 最后的结果。

几种行为

  • 献殷勤：使用无懈可击挡下南猪入侵、万箭齐发、决斗；使用无懈可击抵消表敌意；
  • 表敌意：对某个角色使用杀、决斗；使用无懈可击抵消献殷勤；
  • 跳忠：即通过行动表示自己是忠猪。跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤，或者对某只已经跳反的猪表敌意；
  • 跳反：即通过行动表示自己是反猪。跳反行动就是对主猪或对某只已经跳忠的猪表敌意，或者对某只已经跳反的猪献殷勤。

注意：忠猪不会跳反，反猪也不会跳忠；不管是忠猪还是反猪，能够跳必然跳。

行动准则

共性

  • 每个角色如果手里有桃且生命值未满，那么必然吃掉；
  • 有南猪入侵、万箭齐发、必然使用；有装备必然装上；
  • 受到杀时，有闪必然弃置；
  • 响应南猪入侵或者万箭齐发时候，有杀 / 闪必然弃置；
  • 不会对未表明身份的猪献殷勤（包括自己）。

特性

  • 主猪：
    • 主猪会认为「没有跳身份，且用南猪入侵 / 万箭齐发对自己造成伤害的猪」是类反猪（没伤害到不算，注意类反猪并没有表明身份），如果之后跳了，那么主猪会重新认识这只猪；
    • 对于每种表敌意的方式，对逆时针方向能够执行到的第一只类反猪或者已跳反猪表；如果没有，那么就不表敌意；
    • 决斗时会不遗余力弃置杀；
    • 如果能对已经跳忠的猪或自己献殷勤，那么一定献；如果能够对已经跳反的猪表敌意，那么一定表。
  • 忠猪：
    • 对于每种表敌意的方式，对「逆时针方向能够执行到的第一只已经跳反的猪」表，如果没有，那么就不表敌意；
    • 决斗时，如果对方是主猪，那么不会弃置杀，否则，会不遗余力弃置杀；
    • 如果有机会对主猪或者已经跳忠的猪献殷勤，那么一定献。
  • 反猪：
    • 对于每种表敌意的方式，如果有机会则对主猪表，否则，对「逆时针方向能够执行到的第一只已经跳忠的猪」表，如果没有，那么就不表敌意；
    • 决斗时会不遗余力弃置杀；
    • 如果有机会对已经跳反的猪献殷勤，那么一定献。

限于 iPig 只会用 P++ 语言写 A + B，他请你用 Pigcal (Pascal)、P (C) 或 P++ (C++) 语言来帮他预测最后的结果。

输入格式

输入文件第一行包含两个正整数 $ n $ $ (2 n ) $ 和 \(m\) $ (m ) $，分别代表玩家数和牌堆中牌的数量。数据保证牌的数量够用。

接下来 \(n\) 行，每行 \(5\) 个字符串，依次表示对第 \(i\) 只猪的角色和初始 $4 $ 张手牌描述。编号为 \(1\) 的肯定是主猪。

再接下来一行，一共 \(m\) 个字符串，按照从牌堆顶部到牌堆底部的顺序描述每张牌。

注意：所有的相邻的两个字符串都严格用 \(1\) 个空格隔开，行尾没有多余空格。

输出格式

输出数据第一行包含一个字符串代表游戏结果。如果是主猪胜利，那么输出 \(\texttt{MP}\) ，否则输出 \(\texttt{FP}\) 。数据保证游戏总会结束。

接下来 \(n\) 行，第 \(i\) 行是对第 \(i\) 只猪的手牌描述（注意只需要输出手牌），按照手牌从左往右的顺序输出，相邻两张牌用 \(1\) 个空格隔开，行末尾没有多余空格。如果这只猪已阵亡，那么只要输出 \(\texttt{DEAD}\) 即可。

注意：如果要输出手牌而没有手牌的话，那么只需输出 \(1\) 个空行。

由于数据问题，若牌堆已空，按照每次抽牌抽到的都是最后一张。

输入输出样例

输入: #1

1
2
3
4
5
3 10
MP D D F F
ZP N N N D
FP J J J J
F F D D J J F F K D

输出: #1

1
2
3
4
FP
DEAD
DEAD
J J J J J J D

说明&提示

样例解释

第一回合：

  • 主猪没有目标可以表敌意；
  • 接下来忠猪使用了 \(3\) 张南猪入侵，主猪掉了 \(3\) 点体力，并认为该角色为类反猪，\(3\) 号角色尽管手里有无懈可击，但是因为自己未表明身份，所以同样不能对自己用，乖乖掉 \(3\) 点体力；

下一回合：

  • 反猪无牌可出；
  • 接下来主猪对着类反猪爆发，使用 \(4\) 张决斗，忠猪死亡，结果主猪弃掉所有牌；
  • 下来反猪摸到 \(1\) 张杀直接杀死主猪获胜。

子任务

一共 \(20\) 组测试数据，每个点 \(5\) 分。

\(10\%\) 的数据没有锦囊牌，另外 \(20\%\) 的数据没有无懈可击。

解题思路

又是一个模拟大大题，和上一题不同的是，上一题难度在于各种特殊情况，这题的难度在理解题意上，并且代码量也比上一题多得多，另外，题目限制了只能使用 C++ （好吧，这么复杂的题目就是没限制也懒得再写第二次了）

另外，这一题适合使用面向对象的思想来解答，玩家对象的概念很明确

解答代码

这题太太太复杂了，已经不想写了，留着以后再不全补全吧ovo,未完待续

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
#include <bits/stdc++.h>
using namespace std;

const int MAX_LOVE = 4;        // 生命上限
const int MAX_PLAYER = 17;     // 最大玩家人数
const int MAX_CARDS = 2007;    // 最大牌堆数量

int n, m;    // 玩家数量和牌堆大小 n 范围 [2, 10], m <= 2000
string p;    // 玩家身份
char c;      // 牌

struct card {
    char c;    // 牌的种类
    card *prev, *next;
    card(char _c = '#', card* _prev = nullptr, card* _next = nullptr)
        : c(_c), prev(_prev), next(_next) {
    }
};

// 手牌链表，双向循环链表
class cards {
public:
    card* head;    // 手牌链表头结点
    cards() {
        head = new card();
        head->next = head;
        head->prev = head;
    }

    // 摸到一张类型为 c 的牌加入牌堆最右侧
    void draw(char c) {
        card* cur = new card(c, head->prev, head);
        head->prev->next = cur;
        head->prev = cur;
    }

    // 使用掉一张牌
    void discard(card* c) {
        c->prev->next = c->next;
        c->next->prev = c->prev;
        delete c;
    }

    // 使用一张类型为 c 的牌, 无牌可用则返回 false
    bool play(char c) {
        auto s = find(c);
        if (s == nullptr) return false;
        discard(s);
        return true;
    }

    // 牌堆中查找一张类型为 c 的牌并返回，若不存在则返回 nullptr
    card* find(char c) {
        for (card* p = head->next; p != head; p = p->next) {
            if (p->c == c) return p;
        }
        return nullptr;
    }
};

class player {    // 玩家
public:
    /* =========== 基本方法成员 =========== */
    player(int _r, int _id);            // 构造函数（身份&编号）
    string get_r();                     // 返回玩家身份
    int get_id();                       // 返回玩家编号
    void treat(int c = 1);              // 生命值增加
    void hurt(int c = 1);               // 生命值减少, 减少到 0 触发死亡
    void dead();                        // 玩家出局
    bool isLive();                      // 是否还活着
    void get_card(char c);              // 手牌最右侧加入一张牌
    char get_card();                    // 从牌堆摸一张牌
    player* add_player(player* nxt);    // 下家添加一位玩家
    bool play_P();                      // 使用 桃
    bool play_K(player* target);        // 使用 杀
    bool play_D();                      // 使用 闪
    bool play_F(player* target);        // 使用 决斗
    bool play_N();                      // 使用 南蛮入侵
    bool play_W();                      // 使用 万箭齐发
    bool play_J();                      // 使用 无懈可击
    bool play_Z();                      // 使用 诸葛连弩

    /* =========== 静态方法 =========== */
    static void set_mp(player* pig);    // 设置主将
    static void init_rcg();             // 初始化
    static void add_fp();               // 反贼增加
    static void fp_dead();              // 反贼出局
    static player* get_mp();            // 获取主将
    static bool player::FP_Live();      // 是否还有反贼存活

private:
    /* =========== 基本数据成员 =========== */
    int r;                 // 身份: 0 - 主将, 1 - 忠臣, 2 - 反贼
    int id;                // 编号 从 1 开始逆时针方向依次是 1, 2, 3, ……
    int love;              // 生命值，-1 表示已经出局
    player *pre, *next;    // 双向循环链式结构，上家和下家
    cards cd;              // 玩家的手牌

    /* =========== 静态数据成员 =========== */
    static char cards[MAX_CARDS];    // 牌堆
    static int cur_card;             // 当前摸牌位置（当前牌可摸）
    static int max_card;             // 牌堆大小（最后一张牌下标）
    static player* mp;               // 主将，同时也是头指针
    // 认定的对方身份，0 - 主将, 1 - 忠臣, 2 - 反贼, 3 - 类反贼, -1 表示不确定
    static int rcg[MAX_PLAYER];
    static int cnt_fp;    // 统计反贼数量
};

char player::cards[MAX_CARDS];
int player::cur_card = 0;
int player::max_card = 0;
player* player::mp = nullptr;
int player::rcg[MAX_PLAYER];
int player::cnt_fp = 0;

player::player(int _r, int _id)
    : r(_r), id(_id) {
    // 构造函数
    love = MAX_LOVE;
    pre = this, next = this;
}

inline player* player::add_player(player* nxt) {
    // 下家添加一位玩家
    nxt->next = this->next;
    nxt->pre = this;
    this->next->pre = nxt;
    this->next = nxt;
    return nxt;
}

inline void player::dead() {
    // 玩家出局
    this->love = -1;
    if (r == 2) {
        cnt_fp--;
        if (cnt_fp == 0)
            ;    // 触发游戏结束
    }
    if (r == 0)
        ;    // 触发游戏结束
}

// 手牌加入一张牌
inline void player::get_card(char c) {
    cd.draw(c);
}

// 摸一张牌
inline char player::get_card() {
    if (cur_card <= max_card)
        return cards[cur_card++];
    else
        return cards[max_card];
}

// 生命值减少, 减少到 0 触发死亡
inline void player::hurt(int c = 1) {
    love -= c;
    // 使用 桃 回血
    if (love <= 0) dead();
}

// 生命值增加
inline void player::treat(int c = 1) {
    love += c;
    if (love > MAX_LOVE) love = MAX_LOVE;
}

// 返回玩家身份
inline string player::get_r() {
    if (r == 0)
        return "MP";
    else if (r == 1)
        return "ZP";
    else
        return "FP";
}

// 返回玩家编号
inline int player::get_id() {
    return id;
}

// 返回玩家是否存活
inline bool player::isLive() {
    return love > 0;
}

// 使用 桃
inline bool player::play_P() {
    if (!cd.play('P')) return false;
    treat(1);
    return true;
}

// 对目标使用 杀
inline bool player::play_K(player* target) {
    // 在自己的回合内，对攻击范围内除自己以外的 1 名角色使用。如果没有被『闪』抵消，则造成 1 点伤害。无论有无武器，杀的攻击范围都是 1
    if (!cd.play('K')) return false;
    // 目标受到杀时，有闪必然弃置
    if (!target->play_D()) {
        // 没有闪，受到一点伤害
        target->hurt(1);
    }
    return true;
}

// 使用 闪
inline bool player::play_D() {
    // 当你受到杀的攻击时，可以弃置 1 张闪来抵消杀的效果
    if (!cd.play('D')) return false;
    return true;
}

// 使用 决斗
inline bool player::play_F(player* target) {
    return true;
}

// 使用 南蛮入侵
inline bool player::play_N() {
    return true;
}

// 使用 万箭齐发
inline bool player::play_W() {
    return true;
}

// 使用 无懈可击
inline bool player::play_J() {
    return true;
}

// 使用 诸葛连弩
inline bool player::play_Z() {
    return true;
}

// 设置主将
inline void player::set_mp(player* pig) {
    player::mp = pig;
}

// 初始化 rcg 数组
inline void player::init_rcg() {
    memset(player::rcg, -1, sizeof(player::rcg));
}

// 反贼增加
inline void player::add_fp() {
    player::cnt_fp++;
}

// 反贼出局
inline void player::fp_dead() {
    player::cnt_fp--;
}

// 获取主将
inline player* player::get_mp() {
    return player::mp;
}

// 是否还有反贼存活
inline bool player::FP_Live() {
    return player::cnt_fp > 0;
}

int main() {
    // 玩家数、牌堆数
    player::init_rcg();
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> p;
        int t = 0;
        if (p == "MP")
            t = 0;
        else if (p == "ZP")
            t = 1;
        else if (p == "FP")
            t = 2;
        player* pig = new player(t, i);
        if (t == 0) player::set_mp(pig);
        for (int j = 0; j < 4; ++j) {
            cin >> c;
            pig->get_card(c);
        }
    }
    for (int i = 0; i < m; ++i) {
        // 初始化牌堆
    }
    return 0;
}

P5380 [THUPC2019]鸭棋

题目描述

题目背景

鸭棋是一种风靡鸭子界的棋类游戏。事实上，它与中国象棋有一些相似之处，但规则不尽相同。在这里，我们将为你介绍鸭棋的规则。

同时，我们下发了一个模拟鸭棋规则的玩具，你可以结合这个玩具理解题目（也可以在 AK 后与你的队友进行对弈）。详情请见「玩具使用说明」。

鸭棋在一个 \(10\times 9\)（\(10\) 行 \(9\) 列）的网格棋盘上进行，网格上的每个格点都可以有棋子停留。对弈双方一方执红（red）棋、另一方执蓝（blue）棋，双方轮流执行操作，轮到一位玩家操作时，他必须选择一枚自己的棋子，并按照规则进行一步移动。

鸭棋发明者鸭子德规定一局鸭棋由红方执先手，并设计了初始棋盘布局如下：

initial_board.png

棋子类型与走子规则

棋子分为 \(7\) 类，下面介绍了它们的名字以及它们的移动规则。介绍移动规则时，我们默认棋子所处位置为 \(\left( x,y\right)\)（表示第 \(x\) 行的第 \(y\) 列，下同），并列出它可以到达的位置：

  • 王（captain)：可达的位置共 \(4\) 个，包括 \(\left(x\pm 1,y\right)\) 及 \(\left(x,y\pm 1\right)\)。
  • 士（guard）：可达的位置共 \(4\) 个，包括 \(\left(x\pm 1,y\pm 1\right)\) 及 \(\left(x\pm 1,y\mp 1\right)\)。
  • 象（elephant）：可达的位置至多 \(4\) 个，对于任意 \(s_x,s_y\in \left\{ 1,-1\right\}\)，分别有：
    • 如果位置 \(\left(x+s_x\times 1 ,y+ s_y\times 1\right)\) 上无任意一方的棋子停留，则 \(\left( x+s_x \times 2,y+s_y \times 2\right)\) 为一个可达的位置。
  • 马（horse）：可达的位置至多 \(8\) 个，对于任意 \(s_x,s_y\in \left\{ 1,-1\right\}\)，分别有：
    • 如果位置 \(\left(x+s_x\times 1 ,y\right)\) 上无任意一方的棋子停留，则 \(\left( x+s_x \times 2,y+s_y \times 1\right)\) 为一个可达的位置。
    • 如果位置 \(\left(x ,y+ s_y \times 1 \right)\) 上无任意一方的棋子停留，则 \(\left( x+s_x \times 1,y+s_y \times 2\right)\) 为一个可达的位置。
  • 车（car）：可在不跨越其他棋子的前提下，到达同行或同列的所有其他位置。
  • 鸭（duck）：可达的位置至多 \(8\) 个，对于任意 \(s_x,s_y\in \left\{ 1,-1\right\}\)，分别有：
    • 如果位置 \(\left(x+s_x\times 2 ,y+s_y \times 1\right),\left(x+s_x\times 1 ,y\right)\) 上均无任意一方的棋子停留，则 \(\left( x+s_x \times 3,y+s_y \times 2\right)\) 为一个可达的位置。
    • 如果位置 \(\left(x+s_x \times 1 ,y+ s_y \times 2 \right),\left(x ,y+ s_y \times 1 \right)\) 上均无任意一方的棋子停留，则 \(\left( x+s_x \times 2,y+s_y \times 3\right)\) 为一个可达的位置。
  • 兵（soldier）：可达的位置共 \(8\) 个，包括 \(\left(x\pm 1,y\right)\) 及 \(\left(x,y\pm 1\right)\) 及 \(\left(x\pm 1,y\pm 1\right)\) 及 \(\left(x\pm 1,y\mp 1\right)\)。

除上面描述的规则之外，棋子移动还有如下额外规则：

  • 不能将棋子移动到棋盘外的某个位置。
  • 玩家不能将棋子移动到已经停留了己方棋子的位置。
  • 如果玩家将棋子移动到了一个已经停留了对方棋子的位置，那么原本停留在该位置上的这个对方棋子将被移出游戏。

胜利条件与将军局面

玩家在这个游戏中的目标是将对方的王移出游戏。一旦一方的王被移出游戏，则另一方立即宣告胜利。

对于一个棋盘的状态，如果存在一方有一步合法的操作能够将另一方的王移出游戏，则我们说当前局面是一个将军的局面。需要友情提示的是，根据定义，将军局面的形成包括（但不限于）如下这些可能：

  1. 一方将一枚棋子移动到可以攻击对方王的位置

  2. 在己方王受到威胁时不采取措施躲避

  3. 主动将王移动至会受到攻击的位置

除此之外，需要特别说明的是，游戏结束后，由于双方不可再操作，因此不可能出现将军局面，即便此时另一方王处于被「攻击」的位置。

题目描述

今年的 IDCC（International Duck Chess Competition，国际鸭棋大赛）正在如火如荼地进行着。你观摩了一场精彩绝伦的比赛，但你对对弈过程的记忆已经模糊不清了，只有系统留下的他们的操作序列，序列中的每个操作为当前操作者试图移动某个位置的棋子至另一个位置。你希望用这个序列，来复现出整局棋局的对弈过程。即，对于每步操作，你需要首先判其是否合法，若合法，则进一步求出：

  1. 这步操作移动了哪个棋子。
  2. 这步操作后，是否存在棋子被移出游戏，如有则还需求出被移出游戏的棋子。
  3. 这步操作后，是否形成将军局面。
  4. 这步操作后，游戏是否结束。

可能包含的不合法情况如下：

  • 此步移动的初始位置无己方棋子停留。
  • 此步移动的初始位置有己方棋子停留，但移动不符合规则。
  • 游戏已经结束。

序列中的不合法操作是需要被忽略的。比如，如果轮到红方移动，此时序列中的当前操作恰好是不合法的，则这个操作将被忽略，序列中的下一步操作将成为红方这步的操作（如仍不合法则继续忽略，直至出现合法的操作）。

输入格式

第一行一个非负整数 \(Q\)，表示操作序列的长度。接下来依次描述每个操作。

接下来 \(Q\) 行，每行 \(4\) 个整数 \(x_s, y_s, x_t, y_t\)（\(0\leq x_s,x_t \lt 10\)，\(0\leq y_s,y_t \lt 9\)），描述一个欲将 \(\left(x_s,y_s\right)\) 处棋子移动到 \(\left(x_t,y_t\right)\) 的操作。在这里，我们规定左下角（即红方车摆放的位置，图见「题目背景」）为 \(\left(0,0\right)\)。

保证 \(Q\leq 1000\)。

输出格式

输出 \(Q\) 行，对于每个操作依次输出复现结果。每行输出一个操作的结果：

  • 如果该操作为不合法操作，则请输出 Invalid command。
  • 如果为合法操作，则依次回答「题目描述」中的问题 \(1\sim 4\)：
    • 被移动的棋子用 [颜色] [类型]（注意中间包含空格）来描述，请使用它们的英文名称（见「题目背景」）。如，红象为 red elephant，蓝王为 blue captain。
    • 被移出游戏的棋子的描述方式与上面类似。特别地，如果无棋子被移出游戏，则该问题的答案为 NA。
    • 用 yes、no 分别表示形成、不形成将军局面。
    • 用 yes、no 分别表示游戏结束、游戏不结束。
    • 用 ;（分号）将所有问题的答案隔开。
    • 比如，四个问题的答案分别为：被移动的棋子是蓝车，无棋子被移出游戏，形成将军局面，游戏未结束。则该行应输出 blue car;NA;yes;no。

输入输出样例

输入: #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
18
0 0 7 0
9 0 8 0
0 1 1 3
0 2 2 0
0 3 1 2
0 4 0 3
9 4 8 4
3 2 2 3
7 0 4 2
7 0 5 3
9 2 7 4
2 0 4 3
9 1 8 3
4 3 6 6
7 4 9 2
8 4 9 4
6 6 9 4
9 8 8 8

输出: #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Invalid command
Invalid command
Invalid command
Invalid command
red guard;NA;no;no
Invalid command
blue captain;NA;no;no
red soldier;NA;no;no
Invalid command
Invalid command
blue elephant;NA;no;no
red duck;NA;no;no
blue horse;NA;no;no
red duck;blue soldier;no;no
Invalid command
blue captain;NA;yes;no
red duck;blue captain;no;yes
Invalid command

说明&提示

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。

解题思路

照旧是模拟，比起前面那个猪国杀逻辑简单多了

因为中途有打印调试，提前排除了几个低级bug（包括棋子放错位置，函数传错参数等），最后提交只有两个问题：

  1. 移动棋子的操作中棋子在棋盘上的位置移动了，但棋子本身的坐标没变，导致出现访问空指针的异常
  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
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
#include <bits/stdc++.h>
using namespace std;

// 阵营
#define Camp bool
#define RED true
#define BLUE false

// 棋类
#define PIECE int     // 棋子
#define CAPTAIN 0     // 王
#define GUARD 1       // 士
#define ELEPHANT 2    // 象
#define HORSE 3       // 马
#define CAR 4         // 车
#define DUCK 5        // 鸭
#define SOLDIER 6     // 兵

// 棋子
class piece {
public:
    piece(Camp _color = RED, PIECE _p = CAPTAIN, int _x = 0, int _y = 0);
    int get_x();                // 返回当前横坐标
    int get_y();                // 返回当前纵坐标
    bool isLive();              // 返回是否还在棋盘上，若被吃掉了返回false
    void dead();                // 被吃
    bool eat(piece* p);         // 吃掉对方一个棋子
    Camp camp();                // 返回所属阵营
    PIECE type();               // 返回当前是哪一种棋子
    string print_piece();       // 返回类型对应的单个中文字符
    string tostring();          // 返回 [阵营] [类型] 的字符串
    bool move(int x, int y);    // 移动棋子到指定位置

private:
    Camp color;    // 所属阵营，true 表示红方，false 表示黑方
    PIECE p;       // 棋子类型
    int x, y;      // 当前坐标
    bool save;     // 是否还在棋盘上
};

// 双方阵营基类
class player {
public:
    piece* p[16];    // 指针数组
};

// 红方阵营
class red : public player {
public:
    red() {
        p[0] = new piece(RED, CAPTAIN, 0, 4);
        p[1] = new piece(RED, GUARD, 0, 3);
        p[2] = new piece(RED, GUARD, 0, 5);
        p[3] = new piece(RED, ELEPHANT, 0, 2);
        p[4] = new piece(RED, ELEPHANT, 0, 6);
        p[5] = new piece(RED, HORSE, 0, 1);
        p[6] = new piece(RED, HORSE, 0, 7);
        p[7] = new piece(RED, CAR, 0, 0);
        p[8] = new piece(RED, CAR, 0, 8);
        p[9] = new piece(RED, DUCK, 2, 0);
        p[10] = new piece(RED, DUCK, 2, 8);
        p[11] = new piece(RED, SOLDIER, 3, 0);
        p[12] = new piece(RED, SOLDIER, 3, 2);
        p[13] = new piece(RED, SOLDIER, 3, 4);
        p[14] = new piece(RED, SOLDIER, 3, 6);
        p[15] = new piece(RED, SOLDIER, 3, 8);
    }
    ~red() {
        for (int i = 0; i < 16; ++i) {
            delete p[i];
        }
    }
};

// 蓝方阵营
class blue : public player {
public:
    blue() {
        p[0] = new piece(BLUE, CAPTAIN, 9, 4);
        p[1] = new piece(BLUE, GUARD, 9, 3);
        p[2] = new piece(BLUE, GUARD, 9, 5);
        p[3] = new piece(BLUE, ELEPHANT, 9, 2);
        p[4] = new piece(BLUE, ELEPHANT, 9, 6);
        p[5] = new piece(BLUE, HORSE, 9, 1);
        p[6] = new piece(BLUE, HORSE, 9, 7);
        p[7] = new piece(BLUE, CAR, 9, 0);
        p[8] = new piece(BLUE, CAR, 9, 8);
        p[9] = new piece(BLUE, DUCK, 7, 0);
        p[10] = new piece(BLUE, DUCK, 7, 8);
        p[11] = new piece(BLUE, SOLDIER, 6, 0);
        p[12] = new piece(BLUE, SOLDIER, 6, 2);
        p[13] = new piece(BLUE, SOLDIER, 6, 4);
        p[14] = new piece(BLUE, SOLDIER, 6, 6);
        p[15] = new piece(BLUE, SOLDIER, 6, 8);
    }
    ~blue() {
        for (int i = 0; i < 16; ++i) {
            delete p[i];
        }
    }
};

// 棋盘
class board {
public:
    board();                                                // 初始化棋盘上的棋子
    bool canMove(int x1, int y1, int x2, int y2);           // 能否将棋子移动到对应位置
    bool Move(int x1, int y1, int x2, int y2, Camp cap);    // 移动棋子
    bool isEnd();                                           // 本局游戏是否结束
    bool isDanger();                                        // 当前棋局是否处于将军局面
    piece* Lasteat();                                       // 返回最后一步被吃掉的棋子
    piece* get_piece(int x, int y);                         // 获取某个位置的棋子
    void printBoard();                                      // 打印棋盘

private:
    piece* b[10][9];       // 10x9 的网格棋盘
    red player_red;        // 红方玩家
    blue player_blue;      // 蓝方玩家
    piece* d = nullptr;    // 最后一步被吃的棋子

    // 玩家 p1 是否被玩家 p2 将军
    bool check(player* p1, player* p2);

    // 能否将对应棋子移动到对应位置
    bool canMoveCaptain(int x1, int y1, int x2, int y2);
    bool canMoveGuard(int x1, int y1, int x2, int y2);
    bool canMoveElephant(int x1, int y1, int x2, int y2);
    bool canMoveHorse(int x1, int y1, int x2, int y2);
    bool canMoveCar(int x1, int y1, int x2, int y2);
    bool canMoveDuck(int x1, int y1, int x2, int y2);
    bool canMoveSoldier(int x1, int y1, int x2, int y2);
};

// -------------------  棋盘的方法成员  -----------------------

// 初始化棋盘
board::board()
    : d(nullptr) {
    // 棋盘初始化
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 9; ++j) {
            b[i][j] = nullptr;
        }
    }
    // 红方棋子摆上棋盘
    for (int i = 0; i < 16; ++i) {
        piece* cur = player_red.p[i];
        int x = cur->get_x(), y = cur->get_y();
        b[x][y] = cur;
    }
    // 蓝方棋子摆上棋盘
    for (int i = 0; i < 16; ++i) {
        piece* cur = player_blue.p[i];
        int x = cur->get_x(), y = cur->get_y();
        b[x][y] = cur;
    }
}

// 能否将棋子移动到对应位置(假设起始位置合法且有一枚棋子)
bool board::canMove(int x1, int y1, int x2, int y2) {
    // 目标位置不合法
    if (x2 < 0 || x2 > 9 || y2 < 0 || y2 > 8) return false;
    // 目标位置有己方棋子
    if (b[x2][y2] != nullptr && b[x1][y1]->camp() == b[x2][y2]->camp())
        return false;

    // 根据当前位置棋子类型调用判断函数
    switch (b[x1][y1]->type()) {
        case CAPTAIN: return canMoveCaptain(x1, y1, x2, y2);
        case GUARD: return canMoveGuard(x1, y1, x2, y2);
        case ELEPHANT: return canMoveElephant(x1, y1, x2, y2);
        case HORSE: return canMoveHorse(x1, y1, x2, y2);
        case CAR: return canMoveCar(x1, y1, x2, y2);
        case DUCK: return canMoveDuck(x1, y1, x2, y2);
        case SOLDIER: return canMoveSoldier(x1, y1, x2, y2);
        default: return false;
    }
}

// 移动棋子,移动成功返回 true，否则返回 false
bool board::Move(int x1, int y1, int x2, int y2, Camp cap) {
    // 游戏已经结束不可移动
    if (isEnd()) return false;
    // 检查起始位置是否合法，是否有一个棋子
    if (x1 < 0 || x1 > 9 || y1 < 0 || y1 > 8 || b[x1][y1] == nullptr)
        return false;
    // 起始位置的棋子是否是所给的阵营
    if (b[x1][y1]->camp() != cap) return false;
    // 检查目的地是否可达
    if (canMove(x1, y1, x2, y2)) {
        // 目的地可达那就移动
        if (b[x2][y2] != nullptr) {
            // 吃掉目的地的棋子
            b[x2][y2]->dead();
            d = b[x2][y2];
        }
        else
            d = nullptr;
        // 移动棋子
        b[x1][y1]->move(x2, y2);
        b[x2][y2] = b[x1][y1];
        b[x1][y1] = nullptr;
        return true;
    }
    else
        return false;
}

// 游戏是否结束
inline bool board::isEnd() {
    // 判断双方王是否存活即可
    if (player_red.p[0]->isLive() && player_blue.p[0]->isLive())
        return false;
    else
        return true;
}

// 玩家 p1 是否被玩家 p2 将军
bool board::check(player* p1, player* p2) {
    // p1 王的位置
    int x = p1->p[0]->get_x(), y = p1->p[0]->get_y();
    // 逐个棋子检查能否攻击到王
    for (int i = 0; i < 16; ++i) {
        if (p2->p[i]->isLive() && canMove(p2->p[i]->get_x(), p2->p[i]->get_y(), x, y))
            return true;
    }
    return false;
}

inline bool board::isDanger() {
    // 结束局面不可能是将军局面
    if (isEnd()) return false;
    return check(&player_red, &player_blue) || check(&player_blue, &player_red);
}

inline piece* board::Lasteat() {
    return d;
}

inline piece* board::get_piece(int x, int y) {
    return b[x][y];
}

// 能否将 王 移动到对应位置（假设当前位置有王且目标位置合法）
inline bool board::canMoveCaptain(int x1, int y1, int x2, int y2) {
    // 王只能上下左右移动
    if (x1 == x2 && (y1 - y2 == 1 || y2 - y1 == 1)) return true;
    if (y1 == y2 && (x1 - x2 == 1 || x2 - x1 == 1)) return true;
    return false;
}

// 能否将 士 移动到对应位置（假设当前位置有士且目标位置合法）
inline bool board::canMoveGuard(int x1, int y1, int x2, int y2) {
    // 士只能斜着移动
    if (x1 + 1 == x2 && y1 + 1 == y2)
        return true;
    else if (x1 - 1 == x2 && y1 - 1 == y2)
        return true;
    else if (x1 + 1 == x2 && y1 - 1 == y2)
        return true;
    else if (x1 - 1 == x2 && y1 + 1 == y2)
        return true;
    return false;
}

// 能否将 象 移动到对应位置（假设当前位置有象且目标位置合法）
inline bool board::canMoveElephant(int x1, int y1, int x2, int y2) {
    // 象只能走田字且中间不能有棋子
    if (x1 + 2 == x2 && y1 + 2 == y2 && b[x1 + 1][y1 + 1] == nullptr)
        return true;
    else if (x1 - 2 == x2 && y1 + 2 == y2 && b[x1 - 1][y1 + 1] == nullptr)
        return true;
    else if (x1 + 2 == x2 && y1 - 2 == y2 && b[x1 + 1][y1 - 1] == nullptr)
        return true;
    else if (x1 - 2 == x2 && y1 - 2 == y2 && b[x1 - 1][y1 - 1] == nullptr)
        return true;
    return false;
}

// 能否将 马 移动到对应位置（假设当前位置有马且目标位置合法）
inline bool board::canMoveHorse(int x1, int y1, int x2, int y2) {
    // 马走日字且中间不能有其他棋子
    for (int i = -1; i <= 1; i += 2) {
        for (int j = -1; j <= 1; j += 2) {
            if (x1 + i * 2 == x2 && y1 + j == y2 && b[x1 + i][y1] == nullptr)
                return true;
            if (x1 + i == x2 && y1 + j * 2 == y2 && b[x1][y1 + j] == nullptr)
                return true;
        }
    }
    return false;
}

// 能否将 车 移动到对应位置（假设当前位置有车且目标位置合法）
inline bool board::canMoveCar(int x1, int y1, int x2, int y2) {
    // 车可以在不跨越其他棋子的情况下到达同行或同列的任意位置
    if (x1 == x2) {
        int dir = y2 - y1 > 0 ? 1 : -1;    // 向左还是向右
        bool tmp = true;
        for (int i = y1 + dir; i != y2; i += dir) {
            if (b[x1][i] != nullptr) {
                tmp = false;
                break;
            }
        }
        if (tmp) return true;
    }
    if (y1 == y2) {
        int dir = x2 - x1 > 0 ? 1 : -1;
        bool tmp = true;
        for (int i = x1 + dir; i != x2; i += dir) {
            if (b[i][y1] != nullptr) {
                tmp = false;
                break;
            }
        }
        if (tmp) return true;
    }
    return false;
}

// 能否将 鸭 移动到对应位置（假设当前位置有鸭且目标位置合法）
inline bool board::canMoveDuck(int x1, int y1, int x2, int y2) {
    // 不懂，照本宣科
    for (int i = -1; i <= 1; i += 2) {
        for (int j = -1; j <= 1; j += 2) {
            if (x1 + i * 3 == x2 && y1 + j * 2 == y2 && b[x1 + i * 2][y1 + j] == nullptr && b[x1 + i][y1] == nullptr)
                return true;
            if (x1 + i * 2 == x2 && y1 + j * 3 == y2 && b[x1 + i][y1 + j * 2] == nullptr && b[x1][y1 + j] == nullptr)
                return true;
        }
    }
    return false;
}

// 能否将 兵 移动到对应位置（假设当前位置有兵且目标位置合法）
inline bool board::canMoveSoldier(int x1, int y1, int x2, int y2) {
    // 周围八个位置
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
            if (x1 + i == x2 && y1 + j == y2)
                return true;
        }
    }
    return false;
}

// 格式化输出棋盘
inline void board::printBoard() {
    for (int i = 9; i >= 0; --i) {
        for (int j = 8; j >= 0; --j) {
            if (b[i][j] == nullptr)
                cout << "十 ";
            else {
                cout << b[i][j]->print_piece() << ' ';
            }
        }
        putchar('\n');
    }
}

// -------------------  END - 棋盘的方法成员  -----------------------

// -------------------  棋子的方法成员  -----------------------

// 构造函数，传入阵营，类型，坐标
piece::piece(Camp _color, PIECE _p, int _x, int _y)
    : color(_color), p(_p), x(_x), y(_y) {
    save = true;
}

// 返回当前横坐标
inline int piece::get_x() {
    return this->x;
}

//  返回当前纵坐标
inline int piece::get_y() {
    return this->y;
}

// 是否还在棋盘上
inline bool piece::isLive() {
    return this->save;
}

// 被吃
inline void piece::dead() {
    this->save = false;
}

// 吃掉棋子
inline bool piece::eat(piece* p) {
    p->dead();
    return true;
}

// 移动棋子到指定位置
inline bool piece::move(int x, int y) {
    this->x = x;
    this->y = y;
    return true;
}

// 返回所属阵营
inline Camp piece::camp() {
    return this->color;
}

// 返回棋子类型
inline PIECE piece::type() {
    return this->p;
}

inline string piece::print_piece() {
    switch (p) {
        case CAPTAIN: return "王";
        case GUARD: return "士";
        case ELEPHANT: return "象";
        case HORSE: return "马";
        case CAR: return "车";
        case DUCK: return "鸭";
        case SOLDIER: return "兵";
        default: return "无";
    }
}

// 返回 [阵营] [类型] 的字符串
inline string piece::tostring() {
    string c = color == RED ? "red " : "blue ";
    string t;
    switch (p) {
        case CAPTAIN: t = "captain"; break;
        case GUARD: t = "guard"; break;
        case ELEPHANT: t = "elephant"; break;
        case HORSE: t = "horse"; break;
        case CAR: t = "car"; break;
        case DUCK: t = "duck"; break;
        case SOLDIER: t = "soldier"; break;
        default: t = "err";
    }
    return c + t;
}

// -------------------  END - 棋子的方法成员  -----------------------

int Q;    // 操作序列的长度
int x_s, y_s, x_t, y_t;
Camp c;

int main() {
    // freopen("luogu.in", "r", stdin);      // 输入流重定向
    // freopen("luogu.out", "w", stdout);    // 输出流重定向

    board b;
    c = RED;    // 红方先动

    // b.printBoard();

    scanf("%d", &Q);

    for (int i = 0; i < Q; ++i) {
        scanf("%d%d%d%d", &x_s, &y_s, &x_t, &y_t);
        if (b.Move(x_s, y_s, x_t, y_t, c)) {
            // 这步操作移动了哪个棋子
            cout << b.get_piece(x_t, y_t)->tostring() << ';';
            // 这步操作后，是否存在棋子被移出游戏，如有则还需求出被移出游戏的棋子
            cout << (b.Lasteat() == nullptr ? "NA" : b.Lasteat()->tostring()) << ';';
            // 这步操作后，是否形成将军局面
            cout << (b.isDanger() ? "yes" : "no") << ';';
            // 这步操作后，游戏是否结束
            cout << (b.isEnd() ? "yes" : "no");
            cout << '\n';
            c = c == RED ? BLUE : RED;
        }
        else {
            cout << "Invalid command\n";
        }

        // cout << '\n';
        // b.printBoard();
        // cout << '\n';
    }

    return 0;
}
--- ♥ end ♥ ---

欢迎关注我呀~