专栏文章

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

ffish_love_cat
P13247题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mioroo0p
此快照首次捕获于
2025/12/03 00:03
3 个月前
此快照最后确认于
2025/12/03 00:03
3 个月前
查看原文
简要题意：
给定集合 a,ba,b，寻找 popcount\text{popcount} 最小的 kk 使得 aa 中的每一个数异或上 kk 后可以得到 a′=ba'=b。
若不存在报告无解。
由于 a′a' 中每一个数字都可以在 bb 中找到，所以我们将每一个 bb 中的数字与 aa 的某一个固定元素异或得到一个可能的 kk 后，模拟进行 check 并取最优即可。
时间复杂度 O(Tn2)O(Tn^2)，跑得飞快。
CPP
#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;
}
// 直到公园的风吹起羽毛
// 才想起还有飞翔细胞

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...