P14794 [NERC 2025] Medical Parity题解

heziqian666 · 2025-12-19 20:04:56 · 题解

思路

我用贪心，这道题考察了前缀异或，主要有两种操作：

• 改变异或数组单个值。
• 改变异或数组从当前下标到结尾的区间值。

所以贪心代码如下。

#include<bits/stdc++.h>
using namespace std;
int a[10000001],b[10000001],c[10000001];
void solve(string x,string y){
    int t=x.size();
    x=' '+x;
    y=' '+y;
    int now=0,len=0,ans=0;
    for(int i=1;i<=t;i++){
        now=x[i]-'0';
        a[i]=now;
        a[i]=a[i]^a[i-1];
        b[i]=a[i]^1;
    }
    for(int i=1;i<=t;i++){
        c[i]=y[i]-'0';
    }
    bool flag=0;
    for(int i=1;i<=t;i++){
        if(!flag){
            if(a[i]!=c[i])len++;
            else{
                if(len==1)len=0,ans++;
                else if(len>1) len=1,flag=1,ans++;
            }
        }
        else{
            if(b[i]!=c[i])len++;
            else{
                if(len==1)len=0,ans++;
                else if(len>1) len=1,flag=0,ans++;
            }
        }
    }
    if(len)ans++;
    cout<<ans<<endl;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        string x,y;
        cin>>x>>y;
        solve(x,y);
    }
}