蓝桥杯2025年第十六届省赛真题-水质检测-C语言题解

解题思路:

1、坐标压缩
只关注原来含 # 的列，将这些列的下标收集到数组 col[1..k]，对应的行掩码（1 表示只在上行，2 表示只在下行，3 表示两行都有）收集到 mask[1..k]。
这样DP只需在 k 列之间做，时间从 O(n)降到O(k)。

2、滚动数组

因为每列的状态只依赖前一列，故用两个变量 prev0, prev1 分别表示“到上一活跃列且最后在上行/下行的最小新增数”，空间 O(1)。

3、状态转移
从第 i−1 个活跃列过渡到第 i个活跃列，需要：

横向补空格：列间空列数Δ = col[i] − col[i − 1] − 1；

跨行切换：如果上一列在行 rrr，本列想落在另一个行 r′≠r，则需在本列“竖直”再放一个探测器（由 cross[r'] 表示，0/1）；

本列补探测器：如果原来本列目标行没有 #，则需再放一个（由 cost[r'] 表示，0/1）。

因此，令：

cur0 = min(prev0, prev1 + cross0) + Δ + cost0;

cur1 = min(prev1, prev0 + cross1) + Δ + cost1;

然后将 prev0=cur0, prev1=cur1，推进到下一列。

4、快速 I/O
使用 getchar_unlocked 批量读两行字符串，保证 nnn 达到 10610^6106 时也能迅速读取。

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

#define MAXN 1000005

#define INF 0x3f3f3f3f

// 使用 getchar_unlocked 快速读入一行到 buf 中，返回长度

static int fast_read_line(char *buf) {

    int c, len = 0;

    # 用 getchar_unlocked 一次性读字符，比 scanf 更快。

    while ((c = getchar_unlocked()) != EOF && c != '\n') {

        buf[len++] = (char)c;

    }

    buf[len] = '\0';

    return len;

}

// 取两数最小

static inline int min(int a, int b) {

    return a < b ? a : b;

}

int main() {

    static char s1[MAXN], s2[MAXN];

    int n = fast_read_line(s1);

    fast_read_line(s2);  // 同样长度 n

    // 收集所有含 '#’ 的列

    static int col[MAXN], mask[MAXN];

    int k = 0;

    for (int i = 0; i < n; i++) {

        int m = 0;

        if (s1[i] == '#') m |= 1;

        if (s2[i] == '#') m |= 2;

        if (m) {

            col[++k] = i;

            mask[k] = m;

        }

    }

    // 少于两列含检测器，直接 0

    if (k <= 1) {

        puts("0");

        return 0;

    }

    // 首列初始化

    // 末尾在行0/1的总代价

    int add0 = (mask[1] & 1) ? 0 : 1;

    int add1 = (mask[1] & 2) ? 0 : 1;

    int prev0 = add0, prev1 = add1;

    // 滚动 DP

    for (int i = 2; i <= k; i++) {

        int delta = col[i] - col[i-1] - 1;

        // 本列需要在行0/1放探测器的代价

        int cost0 = (mask[i] & 1) ? 0 : 1;

        int cost1 = (mask[i] & 2) ? 0 : 1;

        // 跨行切换时，还需补竖直一格的代价

        int cross0 = (mask[i] & 2) ? 0 : 1;  // 到行0，但上一列在行1时需要

        int cross1 = (mask[i] & 1) ? 0 : 1;  // 到行1，但上一列在行0时需要

        int cur0 = min(prev0, prev1 + cross0) + delta + cost0;

        int cur1 = min(prev1, prev0 + cross1) + delta + cost1;

        prev0 = cur0;

        prev1 = cur1;

    }

    int ans = min(prev0, prev1);

    printf("%d\n", ans);

    return 0;

}