题解：P14794 [NERC 2025] Medical Parity

· · 题解

题目分析

题目要求找到将给定的二进制字符串 x' 和 y' 修正为满足奇偶控制关系的 x 和 y 所需的最小翻转次数。核心逻辑是：

  1. 奇偶控制字符串 y 的第 i 位是 x 前 i 位中 1 的个数的奇偶性（奇数为 1，偶数为 0）。
  2. 我们需要逐位推导 x 和 y 的正确值，并计算与原字符串的翻转次数差。

解题思路

  1. 状态推导：维护一个变量current_sum_mod表示 x 前 i-1 位中 1 的个数的奇偶性（初始为 0）。
  2. 逐位计算：
    • 对于第 i 位，y[i] 的正确值必须等于 current_sum_mod ^ x[i]（^ 表示异或）。
    • 枚举 x[i] 的可能值（0 或 1 ），计算对应的 y[i] 正确值，统计翻转次数，并更新 current_sum_mod。
  3. 动态规划（dp）：用动态规划记录前 i 位的最小翻转次数，状态定义为dp[i][s]（s 表示前 i 位 1 的个数的奇偶性）。

代码

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int solve(string x_prime, string y_prime) {
    int n = x_prime.size();
    vector<int> dp_prev(2, INF);
    dp_prev[0] = 0; // 初始状态：前0位和为0，翻转次数0

    for (int i = 0; i < n; ++i) {
        vector<int> dp_curr(2, INF);
        char xc = x_prime[i];
        char yc = y_prime[i];
        // 遍历前i位的可能状态（和的奇偶性）
        for (int prev_sum_mod = 0; prev_sum_mod < 2; ++prev_sum_mod) {
            if (dp_prev[prev_sum_mod] == INF) continue;
            for (int x_val = 0; x_val < 2; ++x_val) {
                int y_val = (prev_sum_mod + x_val) % 2;
                // 计算翻转次数：x需要翻转则+1，y需要翻转则+1
                int cost = 0;
                if (x_val != (xc - '0')) cost++;
                if (y_val != (yc - '0')) cost++;
                int curr_sum_mod = (prev_sum_mod + x_val) % 2;
                dp_curr[curr_sum_mod] = min(dp_curr[curr_sum_mod], dp_prev[prev_sum_mod] + cost);
            }
        }
        dp_prev = move(dp_curr);
    }
    // 最终结果是两种状态中的最小值
    return min(dp_prev[0], dp_prev[1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);//加速

    int t;
    cin >> t;
    while (t--) {
        string x, y;
        cin >> x >> y;
        cout << solve(x, y) << '\n';
    }

    return 0;
}