重复局面

形式化题目

国际象棋每走一步都会产生一个 $8\times 8$ 的字符局面。输入共 $n$ 步棋，每步棋用 8 行、每行 8 个字符描述当前局面；两个局面当且仅当 64 个位置字符全部相同时视为同一局面。要求输出每一步棋时该局面截至当前是第几次出现。

思路

首先可以想到逐个和之前所有局面比较的朴素做法：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
// brute.cpp：小数据暴力解，逐个和之前出现过的局面比较。
#include <bits/stdc++.h>
using namespace std;

int n;
vector<string> board;  // 保存不同局面的字符串
vector<int> count_times; // 每个局面已经出现的次数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int step = 1; step <= n; step++) {
        // 拼出当前局面
        string current;
        for (int row = 0; row < 8; row++) {
            string line;
            cin >> line;
            current += line;
        }

        // 线性查找之前是否出现过该局面
        int position = -1;
        for (int i = 0; i < (int)board.size(); i++) {
            if (board[i] == current) {
                position = i;
                break;
            }
        }
        if (position == -1) { // 首次出现
            board.push_back(current);
            count_times.push_back(1);
            cout << 1 << '\n';
        } else { // 出现过，次数加一
            count_times[position]++;
            cout << count_times[position] << '\n';
        }
    }

    return 0;
}

这个做法每步都要扫描之前的全部局面，虽然正确但在数据大时较慢。

用字符串作为键

每个局面固定有 64 个字符，把 8 行依次拼接成一个长度为 64 的字符串。字符串完全相等就代表局面相同，于是“局面”这个对象被序列化成一个唯一的字符串。

用 map<string,int> 以局面字符串为键、出现次数为值：每读入一个局面就 count++ 并输出。这样省去了逐个比较的历史扫描。

这里不需要理解国际象棋规则，也不需要判断走法是否合法；* 和各种棋子字符都只是局面字符串中的普通字符。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

int n;
map<string, int> appeared; // 局面字符串 -> 已经出现的次数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int step = 1; step <= n; step++) {
        // 每 8 行拼成一个长度为 64 的字符串表示当前局面
        string board;
        for (int row = 0; row < 8; row++) {
            string line;
            cin >> line;
            board += line;
        }
        // 先累计本次出现，再输出次数
        appeared[board]++;
        cout << appeared[board] << '\n';
    }

    return 0;
}

复杂度

每个局面长度固定为 64。使用 map 时，单次查找为 $O(64\log n)$ ，总时间复杂度为 $O(n\log n)$ ，空间复杂度为 $O(n)$ ；若改用 unordered_map，平均时间复杂度可降为 $O(n)$ 。

总结

固定大小的二维字符结构可以序列化成字符串作为唯一键，这是把“对象相等”变成“字符串相等”的通用手法。统计“当前对象此前出现几次”时，应先更新计数再输出。

目录

形式化题目

思路

用字符串作为键

代码

复杂度

总结