2025_ICPC_NERC_Northern_Eurasia_Finals——M. Medical Parity · znzryb
## 题目大意
### 题目总结：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$。
1. 此时合法的 $y$ 应为 $10111$。
1. 对比原 $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啊就非常容易了。）
```cpp
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](https://codeforces.com/contest/2181/submission/362133326)
::: 源代码
```cpp
/**
* 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 顺利！
:::