题解：P12135 [蓝桥杯 2025 省 B] 水质检测

蒟蒻的我第一次在洛谷写题解，还请多包涵不足的地方。

因为只有 2 行，而且看到这种问题一般会想到 dfs，逛了一圈发现没有我的这种解法，我采用的是 dfs + 思维来完成这个问题。接下来我说一下我的思路：

首先对于中间的某一个 "#" 号，如果其前面有一个连通块，但是没有与其连通，那么这个 "#" 是必然要与前面连通的。至于怎么连通呢？贪心来说显然直接往前走，走到水平距离和这个点的位置最近的点就行了。这个时候有两种情况：

第一种：两个 "#" 在同一行，那么需要的贡献就是两点的距离

d

	#	~~~~~~~	#
	.	~~~~~~~

第二种：两个 "#" 不在同一行，那么需要的贡献就是两点的水平距离

d + 1

	.	~~~~~~	#
	#	~~~~~~

除了这两种情况，其他情况都包含了，肯定是两点的水平距离最近的时候最优。如果想往左边继续拓展，妄图与其他的 "#" 连起来，肯定是不如在离得近的这个地方的。

现在我们只需要找到左边的第一个连通块的最右端的点的坐标，然后记为

last

。这个时候往右边遍历找到一个 "#"，这个地方需要与

last

这个位置连起来，分类讨论看看是上面的哪一种情况，然后给 ans 加上贡献就行了。

注意，在找到这个块的时候，计算完贡献后就可以寻找这个块的最右端，更新

last

。

冷知识：如果需要拐弯，那么我们可以一开始就拐弯，这样可以使得答案最优，可能会连通更多块。例如：

.	~~~~~~	目标#
目标#	~~~~~~	??	#

由图知，如果一开始就拐弯，那么可以多连通右下角的一个块（WA 了才发现的）。

如果有不清楚的地方或者有误，还请评论区指出来。感谢大家。

接下来请看完整代码：

CPP

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll N = 1e5 + 5, mod = 1e9 + 7, inf = 2e18;
const double esp = 1e-4;
double PI = 3.1415926;
int maxx, n, m = 2;
int xx[] = {0, 0, -1, 1};
int yy[] = {-1, 1, 0, 0};
bool vis[1000005][3];

bool in_map(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void dfs(int x, int y, vector<vector<char>>& a) {
    maxx = max(maxx, x);
    if (vis[x][y]) return;

    for (int i = 0; i < 4; i++) {
        int nx = x + xx[i], ny = y + yy[i];
        if (!in_map(nx, ny) || vis[nx][ny] || a[nx][ny] != '#') continue;
        vis[nx][ny] = true;
        dfs(nx, ny, a);
    }
}

void solve() {
    string s1, s2;
    cin >> s1 >> s2;
    n = s1.size();
    s1 = "!" + s1;
    s2 = "!" + s2;
    vector<vector<char>> a(n + 5, vector<char>(3));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 2; j++) {
            if (j == 1) {
                a[i][j] = s1[i];
            } else {
                a[i][j] = s2[i];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i][1] == '#') {
            maxx = i;
            dfs(i, 1, a);
            break;
        }
        if (a[i][2] == '#') {
            maxx = i;
            dfs(i, 2, a);
            break;
        }
    }

    ll ans = 0, last = maxx;

    for (int i = maxx + 1; i <= n; i++) {
        if (a[i][1] == '#') {
            if (a[last][1] == '#') {
                ans += i - last - 1;
                dfs(i, 1, a);
                last = maxx;
            } else {
                if (a[i][2] == '#') {
                    ans += i - last - 1;
                    dfs(i, 1, a);
                    last = maxx;
                } else {
                    ans += i - last;
                    a[i][2] = '#';
                    dfs(i, 1, a);
                    last = maxx;
                }
            }
            i = maxx;
        } else if (a[i][2] == '#') {
            if (a[last][2] == '#') {
                ans += i - last - 1;
                dfs(i, 2, a);
                last = maxx;
            } else {
                if (a[i][1] == '#') {
                    ans += i - last - 1;
                    dfs(i, 2, a);
                    last = maxx;
                } else {
                    ans += i - last;
                    a[i][1] = '#';
                    dfs(i, 2, a);
                    last = maxx;
                } 
            }
            i = maxx;
        }
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

题解：P12135 [蓝桥杯 2025 省 B] 水质检测

文章操作

相关推荐

评论

题解：P12135 [蓝桥杯 2025 省 B] 水质检测