2025_ICPC_NERC_Northern_Eurasia_Finals——M. Medical Parity

题目大意

题目总结：M. Medical Parity

问题描述

给定两个长度为 $n$ 的二进制字符串 $x'$（测试结果串）和 $y'$（奇偶校验控制串）。

在理想情况下，字符串 $y$ 与 $x$ 必须满足以下关系：

对于每一个位置 $i$（$1 \le i \le n$），$y_i$ 是字符串 $x$ 前 $i$ 个字符中 ‘1’ 的数量对 2 取模的结果。

即：$y_i = (\sum_{j=1}^{i} x_j) \pmod 2$。

这意味着：

• 如果 $x$ 的前 $i$ 个字符中有奇数个 ‘1’，则 $y_i = 1$。

• 如果 $x$ 的前 $i$ 个字符中有偶数个 ‘1’，则 $y_i = 0$.

由于记录数据时可能存在错误，输入的 $x'$ 和 $y'$ 可能不满足上述规则。你需要通过翻转最少数量的位（将 ‘0’ 变 ‘1’ 或将 ‘1’ 变 ‘0’），使得修改后的 $y$ 成为修改后的 $x$ 的合法奇偶校验控制串。翻转操作可以在 $x'$ 或 $y'$ 的任意位置进行。

输出要求

输出使 $y$ 成为 $x$ 的合法奇偶校验串所需的最少总翻转次数。

---

样例解释

• 样例 1
  输入：$x'=11101, y'=10110$
  根据 $x'$ 计算合法的校验串 $y$：

  • $i=1$: $x$ 前 1 位有 1 个 ‘1’（奇数），$y_1=1$
  • $i=2$: $x$ 前 2 位有 2 个 ‘1’（偶数），$y_2=0$
  • $i=3$: $x$ 前 3 位有 3 个 ‘1’（奇数），$y_3=1$
  • $i=4$: $x$ 前 4 位有 3 个 ‘1’（奇数），$y_4=1$
  • $i=5$: $x$ 前 5 位有 4 个 ‘1’（偶数），$y_5=0$
    计算得 $y=10110$，与给定的 $y'$ 完全一致。
    结论： 翻转次数为 0。

• 样例 2
  输入：$x'=11101, y'=10010$
  根据 $x'$ 计算出的合法 $y$ 应为 $10110$（见样例 1）。
  对比给定的 $y'=10010$，只有第 3 位不同（$y_3$ 应为 1，给定为 0）。
  结论： 只需翻转 $y'$ 的第 3 位，总翻转次数为 1。

• 样例 3
  输入：$x'=01100, y'=10110$
  若要达成合法状态，一种最少翻转方案是：

  1. 翻转 $x'$ 的第 1 位，使其变为 $11100$。
  2. 此时合法的 $y$ 应为 $10111$。
  3. 对比原 $y'=10110$，只需再翻转 $y'$ 的最后一位（第 5 位）。
     结论： 总共翻转了 2 次（$x'$ 一次，$y'$ 一次）。

思路讲解

$y_i = c_i \bmod 2$，其中 $c_i$ 是 $x$ 前 $i$ 个字符中 1 的个数。注意到 $y_i \oplus y_{i-1} = x_i$（定义 $y_0 = 0$）。也就是说，$x$ 完全由 $y$ 决定（反之亦然）。所以你实际上只需要确定一个最终的 $y$（或 $x$），另一个就自动确定了。

（其实只要观察到了红字的这个约束，红字的这个东西，那么剩下来这个DP啊就非常容易了。）

vector<array<ll,2>> dp(N+2,{INF,INF});
dp[0][0]=0;
for (int i=1;i<=N;++i) {
    dp[i][1]=(Y[i]!=1)+min(dp[i-1][0]+(X[i]!=1),dp[i-1][1]+(X[i]!=0));
    dp[i][0]=(Y[i]!=0)+min(dp[i-1][0]+(X[i]!=0),dp[i-1][1]+(X[i]!=1));
}

AC代码

AC
https://codeforces.com/contest/2181/submission/362133326

源代码

/**
 * Problem: B. Battle of Arrays
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2181/problem/B
 * Created: 2026-02-09 20:45:55
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    string sx,sy;
    cin>>sx>>sy;
    ll N=sx.size();
    vector<ll> X(N+2),Y(N+2);
    sx.insert(sx.begin(),'#');
    sy.insert(sy.begin(),'#');
    ll cnt=0;
    vector<ll> presum(N+2);
    bool ok=true;
    for (int i=1;i<=N;++i) {
        cnt+=sx[i]-'0';
        X[i]=sx[i]-'0';
        Y[i]=sy[i]-'0';
        presum[i]=cnt;
        if (presum[i]%2!=Y[i]) {
            ok=false;
        }
    }
    if (ok) {
        cout<<0<<"\n";
        return;
    }
    vector<array<ll,2>> dp(N+2,{INF,INF});
    dp[0][0]=0;
    for (int i=1;i<=N;++i) {
        dp[i][1]=(Y[i]!=1)+min(dp[i-1][0]+(X[i]!=1),dp[i-1][1]+(X[i]!=0));
        dp[i][0]=(Y[i]!=0)+min(dp[i-1][0]+(X[i]!=0),dp[i-1][1]+(X[i]!=1));
    }
    debug2d(dp);
    cout<<min(dp[N][0],dp[N][1])<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2181/submission/362133326

*/

心路历程（WA，TLE，MLE……）

AI 的提示

[1 tool called]
好的，你在 VP，我给你一些递进的提示，你可以根据需要看多少：
提示 1：观察 $y$ 和 $x$ 的关系
$y_i = c_i \bmod 2$，其中 $c_i$ 是 $x$ 前 $i$ 个字符中 1 的个数。注意到 $y_i \oplus y_{i-1} = x_i$（定义 $y_0 = 0$）。也就是说，$x$ 完全由 $y$ 决定（反之亦然）。所以你实际上只需要确定一个最终的 $y$（或 $x$），另一个就自动确定了。
提示 2：代价的刻画
假设你选定了最终的 $y$，那么 $x$ 就确定了（$x_i = y_i \oplus y_{i-1}$）。翻转的总代价就是：

$$\sum_{i=1}^{n} [x_i \neq x'i] + \sum{i=1}^{n} [y_i \neq y'_i]$$

把 $x_i = y_i \oplus y_{i-1}$ 代入后，每个位置的代价只取决于 $y_{i-1}$ 和 $y_i$。试着把它写成关于相邻 $y$ 值的函数。
提示 3：DP 的思路
既然每一位的代价只依赖 $y_{i-1}$ 和 $y_i$，你可以用一个很简单的 DP：设 $dp_{i,v}$ 表示确定了 $y_1, y_2, \dots, y_i$ 且 $y_i = v$（$v \in \{0, 1\}$）时的最小总代价。转移时枚举 $y_i$ 的取值，计算当前位在 $x$ 和 $y$ 上分别需要翻转多少位即可。
这个 DP 是 $O(n)$ 的，完全够用。
祝 VP 顺利！