dp做法

本题与这道题思路感觉差不多

首先发现对于任意一个数如果异或两次就白异或了

所以说每个数都异或一次

那么就很像01背包了

我们用01背包求出来所有可能凑出来的数

然后再 $2^L$ 次方枚举所有的数来比较海明距离最小的

时间复杂度 $O(n\times 2^L)$

最后记得加前导0，不加在赛事挂70分（我是超级唐氏）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define L 20
#define N 105
using namespace std;
bool flg=0,flg2=0;
int n,d,l,minn=2e9,minp=0,cnt=0;
int a[N],dp[(1<<17)],ans[N];
char s[L];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
signed main(){
	memset(dp,0x3f,sizeof(dp));
	l=reads(),n=reads();
	for(int i=1;i<=n+1;i++){
		scanf("%s",s+1);
		for(int j=l,k=0;j>=1;j--,k++){
			a[i-1]+=pow(2,k)*(s[j]-'0');
		}
	}
	for(int i=1;i<=n;i++){
		if(!a[i]) flg=1;
		dp[a[i]]=0;
	}
	d=a[0];
	for(int i=1;i<=n;i++){
		for(int j=(1<<l)-1;j>=0;j--){
			dp[j]=min(dp[j],dp[j^a[i]]+1);
		}
	}
	for(int i=0;i<(1<<l);i++){
		if(dp[i]==0x3f3f3f3f) continue;
		int p=i^d,cnt=0;
		while(p){
			int x=p%2;
			p/=2;
			if(x) cnt++;
		}
		if(cnt<minn){
			minn=cnt;
			minp=i;
		}
		else if(cnt==minn){
			if(dp[minp]>dp[i]) minp=i;
			else if(dp[minp]==dp[i]) minp=min(minp,i);
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]==minp){
			flg2=1;
			break;
		}
	}
	if(flg2){
		if(flg) puts("1");
		else puts("2");
	}
	else printf("%d\n",dp[minp]);
	while(minp){
		int x=minp%2;
		ans[++cnt]=x;
		minp/=2;
	}
	for(int i=l;i>=1;i--) printf("%d",ans[i]);
	return 0;
}

简单的暴力题（bfs）

赛时以为是dp，成功挂掉了

读题

1 ≤ N ≤ 100, 1 ≤ L ≤ 16

注意到异或出来的状态不超过2^16^ （65536）种，bfs暴力所有状态用的步数，不会超时

dis[x^y] = dis[x]+1;
q.push(x^y);

坑点

1. 得到的数再放入集合中，所以集合中的数量只增不减

2. 输出格式：一个长度为 L 的二进制数，记得有前导零！！！

3. 小 A 希望通过若干次（至少一次）操作。 那么初始化时dis[a[i]]=0，bfs完后记得特判一下（0次操作不合法）

if (dis[i]==0) {
	if (i==0) dis[i]=1;
	else dis[i]=2;
}

两次选同一个数，异或为0，所以dis[0]=1

0^x=x，因为dis[0]=1，那dis[i]=2

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	string s;
	ll l, n, d, x, in, id;
	ll dis[(1<<17)];
	queue <ll> q;
	vector <ll> v;
	ll init (string s) {
		ll sum = 0;
		for (ll i=0; i<s.length(); i++)
			sum = sum*2+s[i]-'0';
		return sum;
	}
	ll check (ll a, ll b) {
		ll sum = 0;
		while (a || b) {
			sum += ((a&1)!=(b&1));
			a >>= 1;
			b >>= 1;
		}
		return sum;
	}
	void work()
	{
		cin>>l>>n>>s;
		d = init(s);
		memset(dis, -1, sizeof(dis));
		for (ll i=1; i<=n; i++) {
			cin>>s;
			x = init(s);
			if (dis[x]) {
				q.push(x);
				v.push_back(x);
			}
			dis[x] = 0;
		}
		while (!q.empty()) {
			ll x = q.front();
			q.pop();
			for (ll i=0; i<v.size(); i++) {
				ll y = v[i];
				if (dis[x^y]>0) continue;
				dis[x^y] = dis[x]+1;
				q.push(x^y);
			}
		}
		in = 0x7f7f7f7f;
		for (ll i=0; i<(1<<l); i++) {
			if (dis[i]==-1) continue;
			if (!dis[i]) {
				if (!i) dis[i]=1;
				else dis[i]=2;
			}
			ll t = check(i, d);
			if (t<in) {
				in = t;
				id = i;
			}else if (t==in && dis[i]<dis[id]) id=i;
		}
		cout<<dis[id]<<'\n';
		for (ll i=l-1; i>=0; i--) {
			if (id<(1<<i)) cout<<"0";
			else {
				id -= (1<<i);
				cout<<"1";
			}
		}
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

为啥这题比赛时通过率这么低？

注意到能用的数很少啊，所以考虑暴力。首先预处理出 $1$ 次操作能够得到的数，然后套路的把每个数 $x$ 看成一个节点，然后每个节点都有 $n$ 条出边，第 $i$ 条出边连向 $x\oplus a_i$，然后 bfs 出最短距离，最后扫一遍值域统计答案就好了啊。

一共有 $2^l$ 个数，每个数 $n$ 个出边，时间复杂度 $O(n2^l)$。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=(1LL<<16);
const ll INF=2147483647;
ll dis[N],a[105],D,mx,n,L,qu[N],front,rear;
inline ll lowbit(ll x){return x&(-x);}
inline ll popct(ll x){
	ll ret=0;
	while(x) x^=lowbit(x),ret++;
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>L>>n;
	string DD;cin>>DD;DD=' '+DD;
	for(ll i=1;i<=L;i++) D<<=1,D+=(DD[i]=='1');
	mx=(1LL<<L);
	for(ll i=0;i<mx;i++) dis[i]=INF;
	for(ll i=1;i<=n;i++){
		string s;cin>>s;s=' '+s;
		for(ll j=1;j<=L;j++){a[i]<<=1,a[i]+=(s[j]=='1');}
	}
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=n;j++)
			dis[a[i]^a[j]]=1;
	for(ll i=0;i<mx;i++) if(dis[i]!=INF) qu[rear++]=i;
	while(front<rear){
		ll now=qu[front++];
		for(ll i=1;i<=n;i++){
			if(dis[a[i]^now]!=INF) continue;
			dis[a[i]^now]=dis[now]+1;
			qu[rear++]=a[i]^now;
		}
	}
	ll ans=-1;
	for(ll i=0;i<mx;i++){
		if(dis[i]==INF) continue;
		if(ans==-1) ans=i;
		else if(popct(D^i)<popct(D^ans)) ans=i;
	}
	cout<<dis[ans]<<"\n"; 
	for(ll i=L-1;i>=0;i--) cout<<((ans&(1LL<<i))!=0);
	return 0;
}