这次省赛，实际上我并无准备，因为我一如既往地对算法没有什么兴趣。
竞赛一共八道题，A和B题是填空题，后六道题都是程序设计。前五题都做了，第六题暴力应该只拿了部分分，后两题就没时间写了。
在赛场上当时看到C++编译器是2014年发布的gcc 4.7.4，用的是C++98标准。但蓝桥杯的云端是可以运行C++11以上的标准的代码的。
本地做题环境的编译器低版本，导致许多C++函数用不了。比如 to_string()函数用不了。前两题最快速的做饭需要将数转到字符串类型，但是我只知道c++中有一个方便的 to_string() 函数，还好当时我看到赛场机子中有Pycharm，所以我就用python计算了前两道填空题。
这个向下兼容的过程，消耗了我大量时间。
最致命的是，有一道题我需要声明一个迭代器，但是我不知道迭代器的类型名，一般来说都是用auto自动推导的，但auto只在C++11标准以上才有，导致这道题的代码我在本地环境无法测试。明明代码是正确的，但本地的低版本编译器却认为我的代码是错误的。这种割裂感很少有。
而现在看来这道题也依旧做对了。
// C++98
std::vector<int> vec;
std::vector<int>::iterator it = vec.begin();
// C++ 11
auto it = vec.begin(); // 自动推导为 std::vector<int>::iterator
与当时赛场的老师沟通，得知组委会只要求提供5.11版本的dev c++，而他们似乎只更新了代码编辑器版本，但一般来说dev c++是捆绑了一个编译器的，但不知为何内置的编译器却十分古典，感觉有点意思。
比赛完后，我查找了在 C++98 的字符串类型转换方法：
// for C++98/03 standard
string old_int_to_string(int v) {
ostringstream oss;
oss << v;
return oss.str();
}
string old_double_to_string(double v) {
ostringstream oss;
oss << fixed << setprecision(6) << v;
return oss.str();
}
string old_c_style_to_string(int v) {
char buffer[32]; // make sure buffer is suffcient
sprintf(buffer, "%d", v);
return string(buffer);
}
事实上，生活在草台班子里的我们不必认真太多。
部分题解
7. 拼好数
当时留给我写第七道题的时间只有5分钟左右，大概读完了题就已经结束了。 这道题是省赛 C++ C组，Python A组，Java A组的题。
题目
我们将含有不少于 6 个 6 的数视为一个好数。例如 666666, 162636465666 是好数，12366666 不是好数。
给定 n 个正整数 $a_i$，你可以把这些数分成若干组拼起来，每组内的数可以按任意顺序拼，但一组最多只能有 3 个数。求最多可以得到多少个好数。
输入格式
输入的第一行包含一个正整数 n 。
第二行包含 n 个正整数 a1, a2, · · · , an ，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案，即最多可以得到的好数的数量
【样例输入 1】
3
66 66 66
【样例输出 1】
1
【样例输入 2】
7 666666 16166 6696 666 6 6 6
【样例输出 2】
2
这个问题是分组问题：如何分组，使得包含6个6的组尽可能的多。而每个组最多能有三个数，那么最少能有1个数。
我们可以统计每个数中6的个数：比如将 16166 6193 66 转化为 3 1 2，再进行排序，之后算出如何相加才能得到最多的6。
分组的情况只有三种：
sum1 = a1
sum2 = a1 + a2
sum3 = a1 + a2 + a3
我们为了得到最大的组数，使用贪心策略追求局部最优，则每次都要尽可能地先选择最少的数，且尽可能地用最大的数与最小的数组合：
如果一个数包含6个以上的6，则单独成一组。
此时，转换后的数组只可能由 1 2 3 4 5 这五个数字组成。
对于 5 我们为它找 1，如果没有则找 2。同理，对于4，我们找 2，没有则找 3。
此时未配对的数，只可能由 1 2 3 4 组成。三元组中：首先查找4 + 1 + 1，对于 4 + 2 + 1，不优于 4 + 2。
而对于 1 2 3，3 + 2 + 1 优于 3 + 2 + 2 ，并且优于 3 + 3，因为 1 2 如果没有 3 就无法成组。
最后只剩 2 3 的情况：
- 2 + 2 + 2
- 3 + 2 + 2
- 3 + 3
#include <bits/stdc++.h>
using namespace std;
int n;
int count_six(int n) {
string s = to_string(n);
int cnt = count(s.begin(), s.end(), '6');
if(cnt > 6) cnt=6;
return cnt;
}
int main() {
cin >> n;
int a[7] = {0};
for(int i = 0;i<n;i++) {
int t; cin>>t;
a[count_six(t)] += 1;
}
int ans = a[6];
int idx = 1; // range 1 2 3 4 5
while(a[5]>0) {
if(a[idx]){
a[idx]--; a[5]--;
ans++;
} else if(idx < 6) {
idx++;
}
}
while(a[4] > 0 && a[1] > 1) {
a[4]--; a[1]-=2;
ans++;
}
idx = 2; // range 2 3 4
while(a[4] > 0) {
if(a[idx]){
a[idx]--; a[4]--;
ans++;
} else if(idx < 5) {
idx++;
}
}
while(a[3] && a[2] && a[1]) {
--a[3]; --a[2]; --a[1];
ans++;
}
// 2 + 2 + 2
ans += a[2] / 3;
a[2] = a[2] % 3;
// 3 + 2 + 2
int possible = min(a[3], a[2] / 2);
ans += possible;
a[3] -= possible;
a[2] -= 2 * possible;
// 3 + 3
ans += a[3] / 2;
a[3] = a[3] % 2;
cout << ans << endl;
return 0;
}
8. 登山
题目
小蓝正在登山，山峰的高度构成 n 行 m 列的正整数矩阵，$a_(i, j)$ 表示第 i 行 第 j 列格子 (i, j) 上的山峰的高度。小蓝以一种特别的方式进行登山，如果他此刻在第 p 行第 q 列的格子 (p, q) 上，那么下一步可以选择：
走到格子 (i, q)，满足 ai,q < ap,q 且 i > p ；
走到格子 (i, q)，满足 ai,q > ap,q 且 i < p ；
走到格子 (p, j)，满足 ap, j < ap,q 且 j > q ；
走到格子 (p, j)，满足 ap, j > ap,q 且 j < q 。
小蓝想知道，如果他依次从每一个格子开始出发，按照最优策略，他最高能到达的山峰的高度的平均值是多少？
输入格式
输入的第一行包含两个正整数 n, m ，用一个空格分隔。
接下来 n 行，每行包含 m 个正整数。其中第 i 行包含 ai,1, ai,2, · · · , ai,m ，相 邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个实数表示答案，四舍五入保留正好 6 位小数。
题解
我们先来分析一下移动规则：
- 向下移动 （i > p)，需要高度更低。
- 向上移动 （i < p)，需要高度更高。
- 向右移动 (j > q)，需要高度更低。
- 向左移动 (j < q)，需要高度更高。
每次移动只顺着一个行或列方向上的变化，并且是可以跳着走的。
对于每一个格子，或者叫做起点 $(p, q)$，都要算出能到达的最高山峰高度，最后将每一个格子的结果求平均值。
我自己尝试直接用dfs，加上记忆搜索来做，只通过了部分：
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> a;
vector<vector<int>> dp;
int n, m;
set<pair<int, int>> used; // unordered_set require customizing hash func
const NEG_INF = -1;
int dfs(int p, int q) {
if(dp[p][q] != -1) return dp[p][q];
if(used.find({p, q}) != used.end()) return NEG_INF;
int max_h = a[p][q];
// Downward
for(int i = p+1; i<n; i++) {
if(a[i][q] < a[p][q]){
used.insert({p, q});
max_h = max(max_h, dfs(i, q));
used.erase({p, q});
}
}
// Upward
for(int i = p-1; i>=0; i--) {
if(a[i][q] > a[p][q]) {
used.insert({p, q});
max_h = max(max_h, dfs(i, q));
used.erase({p, q});
}
}
// Rightward
for(int j = q+1; j<m; j++) {
if(a[p][j] < a[p][q]){
used.insert({p, q});
max_h = max(max_h, dfs(p, j));
used.erase({p, q});
}
}
// Leftward
for(int j = q-1; j>=0; j--) {
if(a[p][j] > a[p][q]){
used.insert({p, q});
max_h = max(max_h, dfs(p, j));
used.erase({p, q});
}
}
dp[p][q] = max_h;
return max_h;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
a.assign(n, vector<int>(m));
dp.assign(n, vector<int>(m, -1));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
double total = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
total += dfs(i, j);
}
}
double average = total / (n * m);
cout << fixed << setprecision(6) << average << endl;
return 0;
}
Refs