题解：P13247 [GCJ 2014 #1A] Charging Chaos

fish_love_cat · 2025-07-23 22:43:26 · 题解

简要题意：

给定集合 a,b，寻找 \text{popcount} 最小的 k 使得 a 中的每一个数异或上 k 后可以得到 a'=b。

若不存在报告无解。

由于 a' 中每一个数字都可以在 b 中找到，所以我们将每一个 b 中的数字与 a 的某一个固定元素异或得到一个可能的 k 后，模拟进行 check 并取最优即可。

时间复杂度 O(Tn^2)，跑得飞快。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[155],b[155],c[155];
int flc;
void solve(){
    printf("Case #%d: ",++flc);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        a[i]=0;
        for(int j=0;j<m;j++)
        a[i]+=(1ll<<(m-j-1))*(s[j]-'0');
    }
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        b[i]=0;
        for(int j=0;j<m;j++)
        b[i]+=(1ll<<(m-j-1))*(s[j]-'0');
        c[i]=b[i];
    }
    sort(a+1,a+1+n);
    int ans=1e9;
    for(int i=1;i<=n;i++){
        int k=c[i]^a[1];
        for(int j=1;j<=n;j++)
        b[j]^=k;
        sort(b+1,b+1+n);
        bool flc=1;
        for(int j=1;j<=n;j++){
            if(b[j]!=a[j])flc=0;
            b[j]^=k;
        }
        if(flc){
            int ret=0;
            while(k){
                ret+=k&1;
                k>>=1;
            }
            ans=min(ret,ans);
        }
    }
    if(ans==1e9)puts("NOT POSSIBLE");
    else cout<<ans<<'\n';
}
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 直到公园的风吹起羽毛
// 才想起还有飞翔细胞