题解：P8689 [蓝桥杯 2019 国 A] 填空问题

思路

A

由于数据规模不大（$30 \times 50 = 1500$ 个字符），我们可以采用暴力枚举的方法：

  1. 垂直方向：对每一行 $i$，枚举所有可能的三个列位置（$j_₁ < j_₂ < j_₃$），检查字符是否满足 $mat_{i, j_1} < mat_{i, j_2} < mat_{i, j_3}$。
  2. 水平方向：对每一列，枚举所有可能的三个行位置（$i_₁ < i_₂ < i_₃$），检查字符是否满足 $mat_{i_1, j} < mat_{i_2, j} < mat_{i_3, j}$。
  3. 从左上至右下：对于每条斜线（行索引减去列索引为常数），枚举三个点，按列排序后检查字符是否递增。
  4. 从左下至右上：对于每条斜线（行索引加上列索引为常数），枚举三个点，分别按列排序和按行排序检查字符是否递增。

代码：

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

char a[35][55];  // 从(1,1)开始存储
int ansA = 0;

int solveA() {
    // 读取矩阵数据
    string mat[30] = {
        "VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG",
        "SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF",
        "ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA",
        "BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL",
        "YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH",
        "ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU",
        "XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR",
        "ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG",
        "MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA",
        "VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF",
        "GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC",
        "EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK",
        "PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW",
        "CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP",
        "RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS",
        "PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR",
        "JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL",
        "YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP",
        "HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN",
        "DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF",
        "LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW",
        "CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ",
        "IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI",
        "ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB",
        "HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP",
        "FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS",
        "VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ",
        "BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR",
        "RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY",
        "ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX"
    };
  
    // 存入数组，下标从1开始
    for (int i = 1; i <= 30; i++) {
        for (int j = 1; j <= 50; j++) {
            a[i][j] = mat[i-1][j-1];
        }
    }
  
    // 1. 水平方向
    for (int i = 1; i <= 30; i++) {
        for (int j1 = 1; j1 <= 48; j1++) {
            for (int j2 = j1 + 1; j2 <= 49; j2++) {
                for (int j3 = j2 + 1; j3 <= 50; j3++) {
                    if (a[i][j1] < a[i][j2] && a[i][j2] < a[i][j3]) {
                        ansA++;
                    }
                }
            }
        }
    }
  
    // 2. 垂直方向
    for (int j = 1; j <= 50; j++) {
        for (int i1 = 1; i1 <= 28; i1++) {
            for (int i2 = i1 + 1; i2 <= 29; i2++) {
                for (int i3 = i2 + 1; i3 <= 30; i3++) {
                    if (a[i1][j] < a[i2][j] && a[i2][j] < a[i3][j]) {
                        ansA++;
                    }
                }
            }
        }
    }
  
    // 3. 左上-右下方向（45°斜线）
    // 斜线索引：i-j 的范围是[-49, 29]，加上50使其非负
    int d1[100][35][2];  // d1[k][][]存储第k条斜线上的点
    int cnt1[100] = {0}; // 每条斜线上的点数
  
    // 收集斜线上的点
    for (int i = 1; i <= 30; i++) {
        for (int j = 1; j <= 50; j++) {
            int idx = i - j + 50;  // 使索引非负
            d1[idx][cnt1[idx]][0] = i;
            d1[idx][cnt1[idx]][1] = j;
            cnt1[idx]++;
        }
    }
  
    // 处理每条斜线
    for (int k = 0; k < 100; k++) {
        int n = cnt1[k];
        if (n < 3) continue;
      
        // 对斜线上的点按列排序（冒泡排序）
        for (int x = 0; x < n - 1; x++) {
            for (int y = 0; y < n - 1 - x; y++) {
                if (d1[k][y][1] > d1[k][y+1][1]) {
                    int tmp1 = d1[k][y][0], tmp2 = d1[k][y][1];
                    d1[k][y][0] = d1[k][y+1][0];
                    d1[k][y][1] = d1[k][y+1][1];
                    d1[k][y+1][0] = tmp1;
                    d1[k][y+1][1] = tmp2;
                }
            }
        }
      
        // 枚举三个点
        for (int x = 0; x < n - 2; x++) {
            for (int y = x + 1; y < n - 1; y++) {
                for (int z = y + 1; z < n; z++) {
                    int i1 = d1[k][x][0], j1 = d1[k][x][1];
                    int i2 = d1[k][y][0], j2 = d1[k][y][1];
                    int i3 = d1[k][z][0], j3 = d1[k][z][1];
                  
                    char c1 = a[i1][j1];
                    char c2 = a[i2][j2];
                    char c3 = a[i3][j3];
                  
                    if (c1 < c2 && c2 < c3) {
                        ansA++;
                    }
                }
            }
        }
    }
  
    // 4. 左下-右上方向（135°斜线）
    // 斜线索引：i+j 的范围是[2, 80]
    int d2[85][35][2];  // d2[k][][]存储第k条斜线上的点
    int cnt2[85] = {0}; // 每条斜线上的点数
  
    // 收集斜线上的点
    for (int i = 1; i <= 30; i++) {
        for (int j = 1; j <= 50; j++) {
            int idx = i + j;
            d2[idx][cnt2[idx]][0] = i;
            d2[idx][cnt2[idx]][1] = j;
            cnt2[idx]++;
        }
    }
  
    // 处理每条斜线
    for (int k = 0; k < 85; k++) {
        int n = cnt2[k];
        if (n < 3) continue;
      
        // 枚举三个点
        for (int x = 0; x < n - 2; x++) {
            for (int y = x + 1; y < n - 1; y++) {
                for (int z = y + 1; z < n; z++) {
                    int i1 = d2[k][x][0], j1 = d2[k][x][1];
                    int i2 = d2[k][y][0], j2 = d2[k][y][1];
                    int i3 = d2[k][z][0], j3 = d2[k][z][1];
                  
                    char c1 = a[i1][j1];
                    char c2 = a[i2][j2];
                    char c3 = a[i3][j3];
                  
                    // 按列排序检查
                    int col1 = j1, col2 = j2, col3 = j3;
                    char ch1 = c1, ch2 = c2, ch3 = c3;
                  
                    // 冒泡排序按列排序
                    if (col1 > col2) { swap(col1, col2); swap(ch1, ch2); }
                    if (col2 > col3) { swap(col2, col3); swap(ch2, ch3); }
                    if (col1 > col2) { swap(col1, col2); swap(ch1, ch2); }
                  
                    bool col_ok = (ch1 < ch2 && ch2 < ch3);
                  
                    // 按行排序检查
                    int row1 = i1, row2 = i2, row3 = i3;
                    ch1 = c1; ch2 = c2; ch3 = c3;
                  
                    // 冒泡排序按行排序
                    if (row1 > row2) { swap(row1, row2); swap(ch1, ch2); }
                    if (row2 > row3) { swap(row2, row3); swap(ch2, ch3); }
                    if (row1 > row2) { swap(row1, row2); swap(ch1, ch2); }
                  
                    bool row_ok = (ch1 < ch2 && ch2 < ch3);
                  
                    if (col_ok || row_ok) {
                        ansA++;
                    }
                }
            }
        }
    }
    return ansA;
}

答案为 $180414$。

B

该问题可抽象为旅行商问题的变体。首先对数据进行预处理：将 $20$ 个城市名称映射为编号，并将所有车次时间转换为分钟数。文件中除起始两行外，其余边均为双向且无自环；对于起始两行存在的重边，仅保留首行数据即可，因其对应从北京出发的首班车，否则这两条车次在后续计算中不会被采用，由此解决了重边问题。

题目要求在每个城市至少停留 $24$ 小时，这部分停留时间可在计算出交通时间后统一累加。因此，问题转化为从北京出发，乘坐高铁访问其余 $19$ 个城市各一次并返回北京，求最小交通时间。所有车次均在当天出发与到达。

考虑使用状态压缩动态规划求解。需注意换乘时若后一班车时间晚于前一班车到达时间，则需等待至次日，该时间差应在计算中纳入。

代码：

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 20, INF = 0x3f3f3f3f;
string a[21] = {"", "北京", "上海", "广州", "长沙", "西安", "杭州", "济南", "成都", "南京", "昆明", "郑州", "天津", "太原", "武汉", "重庆", "南昌", "长春", "沈阳", "贵阳", "福州"};
int b[21][21], c[21][21];
int f[1 << 20][21];

int getid(string s) {
    for (int i = 1; i <= N; i++)
        if (a[i] == s)
            return i;
    return -1;
}

int gettime(string s) {
    return ((s[0] - '0') * 10 + (s[1] - '0')) * 60 + ((s[3] - '0') * 10 + (s[4] - '0'));
}

int calc(int now, int x, int y) {
    int t = now % 1440;
    int res = now - t + c[x][y];
    if (t > b[x][y])
        res += 1440;
    return res;
}

int solveB() {
    freopen("trip.txt", "r", stdin);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            b[i][j] = c[i][j] = -1;
    string s;
    cin >> s >> s >> s >> s >> s;
    while (cin >> s) {
        int x, y;
        cin >> s;
        x = getid(s);
        cin >> s;
        y = getid(s);
        cin >> s;
        if (b[x][y] == -1)
            b[x][y] = gettime(s);
        cin >> s;
        if (c[x][y] == -1)
            c[x][y] = gettime(s);
    }
    for (int i = 0; i < (1 << N); i++)
        for (int j = 1; j <= N; j++)
            f[i][j] = INF;
    f[1][1] = 720;
    for (int i = 0; i < (1 << N); i++)
        for (int j = 1; j <= N; j++)
            if (i & (1 << (j - 1)))
                for (int k = 1; k <= N; k++)
                    if ((i & (1 << (k - 1))) && b[k][j] != -1 && f[i ^ (1 << (j - 1))][k] != INF) {
                        int tmp = calc(f[i ^ (1 << (j - 1))][k], k, j);
                        if (tmp < f[i][j])
                            f[i][j] = tmp;
                    }
    int ans = INF;
    for (int i = 1; i <= N; i++)
        if (b[i][1] != -1)
            ans = min(ans, calc(f[(1 << N) - 1][i], i, 1));
    return ans - 720 + 1440 * (N - 1);
}

答案为 $41613$。

C

需要计算在旋转同构意义下，不同的骰子数量。

众所周知，骰子有这样的特性：

  • $6$ 个面，分别标有 $1$ 至 $6$ 点；
  • 数字 $1$、$4$、$5$：旋转 $90^{\circ}$、$180^{\circ}$、$270^{\circ}$ 后形状不变（有 $4$ 种旋转对称）；
  • 数字 $2$、$3$、$6$：旋转 $180^{\circ}$ 后形状不变（有 $2$ 种旋转对称）。

而立方体有 $24$ 种旋转方式。

考虑在 Burnside 引理上进行变形：$\text{不同骰子数} = \frac{1}{24} × 每种旋转下不变的骰子数$。

一共有 $6! = 720$ 种分配数字的方案，而 $1$、$4$、$5$ 只有 $1$ 种朝向，$2$、$3$、$6$ 各有 $2$ 种朝向，所以总方案数为 $720 \times 2^3 = 5760$，最终结果为 $5760 \times \frac{1}{24} = 240$。

没有代码。

D

从小到大枚举整数 $n$，计算其约数个数 $d$，然后对于每个 $i(i \le d)$，如果 $S_i$ 尚未找到，则令 $S_i = n$。

优化：

  1. 只需枚举到 $\sqrt n$，每个约数 $i$ 对应两个约数 ($i$ 和 $n / i$)；
  2. 当找到前 $60$ 个 $S_i$ 时停止。

代码：

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 <bits/stdc++.h>
#define endl '\n'
using namespace std;

int S[65];  // S[i]存储至少含有i个约数的最小数
int found = 0;  // 已找到的个数

int solveD() {
    memset(S, 0, sizeof(S));
  
    for (int n = 1; found < 60; n++) {
        // 计算n的约数个数
        int cnt = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                cnt++;
                if (i * i != n) cnt++;
            }
        }
      
        // 更新S数组
        for (int i = 1; i <= cnt && i <= 60; i++) {
            if (S[i] == 0) {
                S[i] = n;
                found++;
            }
        }
    }
  
    // 计算前60个S[i]的和
    int sum = 0;
    for (int i = 1; i <= 60; i++) {
        sum += S[i];
    }
  
    return sum;
}

答案：$101449$。

E

这个问题是最大独立集问题，可以转化为图论模型求解。

首先将问题转化为图论问题：

  • 顶点：数字 $1$ 至 $100$（排除完全平方数）；
  • 边：如果两个数字的和是完全平方数，则它们之间有边；
  • 目标：找到最大的顶点集合，使得集合中任意两个顶点之间都没有边。

完全平方数在题目范围内的有：$1, 4, 9, 16, 25, 36, 49, 64, 81, 100$。

由于不能选择完全平方数本身，这意味着我们只能从剩下的 $90$ 个数字中选择。

可以使用贪心算法：

  1. 从所有可选的数字开始
  2. 每次选择度数最小的数字（与其他数字冲突最少的）
  3. 将其加入集合，并删除所有与之冲突的数字
  4. 重复步骤 $2$、$3$ 直到没有数字可选

当然，对于较小规模的问题（$100$ 个顶点），也可以使用回溯搜索找到最大独立集。

剪枝策略：

  1. 按度数排序，优先考虑度数小的顶点
  2. 使用上界估计（当前解大小 + 剩余顶点数）
  3. 如果不可能超过当前最优解，则剪枝

通过以上方法可以得到其中一种结果：

1
2
3
4
5
6
7
2, 3, 6, 10, 11, 13,
14, 15, 17, 18, 19,
22, 23, 26, 29, 30,
34, 35, 37, 38, 42,
43, 46, 47, 51, 53,
54, 55, 58, 59, 62,
66, 67, 71, 73, 78

答案为 $36$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "180414", // 双引号中替换为 A 题的答案
        "47373", // 双引号中替换为 B 题的答案
        "240", // 双引号中替换为 C 题的答案
        "101449", // 双引号中替换为 D 题的答案
        "36", // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}