Au Revoir, icpc
—— 永别了，icpc
今日天梯赛打得并不好，甚至没能进前三，赛后 20s 发现是某个细节写错了。
具体是什么？
问题：有一块 \(n \times m\) 的海洋，上面有一些岛屿，此外还有一些宝藏。求岛屿个数和宝藏岛屿个数（四联通）。
我写的是，首先将所有岛屿标为 \(1\)（包括宝藏），然后求连通块个数。这是第一问，当然，没有问题。
然后是将所有宝藏岛标记为 \(2\)，求连通块个数，这里有问题，因为也数了那些 \(1\) 的连通块。
我没注意到这个细节，以为是其他地方写挂了。
修正后的代码
#include <bits/stdc++.h>
#include <bits/extc++.h>
using ll = long long;
using namespace __gnu_pbds;
template <class T> using splay =
tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using splay2 =
tree<T, null_type, std::greater<T>, rb_tree_tag, tree_order_statistics_node_update>;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
int cnt = n * m;
std::vector<std::string> mp(n);
for (auto &i : mp)
std::cin >> i, cnt -= std::count(i.begin(), i.end(), '0');
// std::cout << "! " << cnt << '\n';
auto get = [&](int x, int y) {
return x * m + y;
};
std::vector<int> vis(n * m);
std::vector<std::pair<int, int>> dir = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1},
};
std::function<void(int, int)> dfs = [&](int i, int j) {
if (vis[get(i, j)]) return;
vis[get(i, j)] = 1;
for (auto [dx, dy] : dir) {
int px = i + dx;
int py = j + dy;
if (px < 0 || px >= n || py < 0 || py >= m) continue;
if (vis[get(px, py)]) continue;
if (mp[px][py] != '0') {
mp[px][py] = mp[i][j];
dfs(px, py);
}
}
};
std::function<void(int, int)> dfs2 = [&](int i, int j) {
if (vis[get(i, j)]) return;
vis[get(i, j)] = 1;
for (auto [dx, dy] : dir) {
int px = i + dx;
int py = j + dy;
if (px < 0 || px >= n || py < 0 || py >= m) continue;
if (vis[get(px, py)]) continue;
if (mp[px][py] != '0') {
mp[px][py] = '2';
dfs2(px, py);
}
}
};
auto counter = [&]() {
static char c = '1';
int ans = cnt;
std::vector<int> p(n * m);
std::iota(p.begin(), p.end(), 0);
std::function<int(int)> find = [&](int x) -> int {
return p[x] = p[x] == x ? x : find(p[x]);
};
auto merge = [&](int i, int j, int x, int y) {
int X = find(get(i, j));
int Y = find(get(x, y));
if (X == Y) return 0;
return p[X] = Y, 1;
};
using pii = std::pair<int, int>;
std::queue<pii> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == c)
q.emplace(i, j);
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (vis[get(x, y)]) continue;
vis[get(x, y)] = 1;
for (auto [dx, dy] : dir) {
int px = dx + x, py = dy + y;
if (px < 0 || px >= n || py < 0 || py >= m) continue;
if (mp[px][py] == c) {
ans -= merge(x, y, px, py);
q.emplace(px, py);
vis[get(px, py)] = 1;
}
}
}
c ++;
return ans - 1;
};
auto restore = mp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == '1')
dfs(i, j);
}
}
vis = std::vector<int>(n * m);
std::cout << counter() << ' ';
vis = std::vector<int>(n * m);
mp = restore;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] >= '2')
mp[i][j] = '2';
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == '2')
dfs2(i, j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == '1') {
mp[i][j] = '0';
cnt -= 1;
}
}
}
// for (auto &i : mp) std::cout << i << '\n';
vis = std::vector<int>(n * m);
std::cout << counter() << '\n';
return 0;
}
按照 /p/train-20230419.html#walk 中代码块最下方的隐藏段落:
我要正式切割 ICPC 了。心中十分不舍于愧疚，尤其是让其他团队的同学去参加我团队负责的 ICPC。我曾经的队友们一个已经退出 ACM，两个准备考研，一个已经找到可转正的实习。
怎么这么多队友？
大一的时候和两个 OIer 组队了，战绩是一个省赛铜奖。
之后一直到大三上，都是和另外两个 0 基础的一起组队，当然，我也是 0 基础.
平庸的成绩
此外还有两个四川省赛铜。
真正意义上的人菜瘾大。
我与 ICPC
让我想想，是不是要来个时间线？其实也就是大一打学校的预选赛然后进入团队学习，期间觉得自己太菜了退过一段时间，后来打新生赛又回去了。
大一很幸运得到一个省赛名额，去了西南民大比赛，那场比赛有 cjb 出题。
不想却是唯一一次线下比赛。
之后大二就学新算法，不断刷题，ojhunter 上数数有 \(2647\) 道题，可能很多重复的，提交有 \(20811\) 次。西安打炸之后还因为刷这么多题却连铜都摸不到感到十分痛苦，也成为了学弟用来调侃的笑话。不过现在释然了，如果对 icpc 不报有任何功利心的话，她还是很有趣的，至少我这三年过得很快乐，也让我爱上了算法与 C++。
这就够了。
要说 ICPC 给我带来了什么的话……
- 朋友。虽然大多是素未谋面的陌生网友。
- 挂科。甚至无法升入大四，果然应了那句 icpc + 娱乐 = 挂科 恒等式。不过不用担心，我下学期好好修读应该还是能 2024 年毕业的。
- C++ 知识。太多太多了，这也许对我的面试会有不小的帮助。甚至我打算从事 C++ 相关的工作。
- 真相。我如此弱的真相。
致谢
特别感谢 @繁凡さん 允许我加入团队。
对一路上给予过我帮助的同学/网友们表示感谢。
感谢 ICPC，给我带来了如此快乐的大学生活。
F.I.N.
标签：std,get,int,px,py,icpc,Au,mp,Revoir From： https://www.cnblogs.com/patricky/p/icpc-au-revoir.html