T4

T4

有点考察注意力

step 1 转化

我们不太喜欢求最大值，因为在只加的情况下当前最优可能被反超，但当前最小一定是最小的，因为不可能被反超

我们先考虑如何求解最小值

首先，若有不只一个自己，答案为0

其次，若有一个是我异或一位，答案为1

可以枚举位数，然后枚举那几位不同

$O(N2^L)$

step 2 优化

思考经典优化

每次枚举一些转化为每次枚举一个，并枚举多次

这样操作：

建一张图，每个点代表一个数，向和它差为一的连边

跑一个多源bfs，找到每个点最近的有数的点即可

$O(L2^L)$

step 3 最后一步

给每个数取反即可

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define x first
#define y second

const int N = 2e5 + 10,M = 19;

int n,L,a[N],dis[1<<M],vis[1<<M],cnt[1<<M];
string s;
vector<int>p[1<<M];
queue<PII>q;

int read()
{
	cin>>s;
	int ret=0;
	for(int i=0;i<L;i++)
		ret=((ret<<1)|(s[i]-'0'));
	return ret;
}

void bfs()
{
	for(int i=1;i<=n;i++) q.push({a[i],0});
	while(!q.empty())
	{
		int u=q.front().x,d=q.front().y;
		q.pop();
		if(vis[u]) continue;
		dis[u]=d;
		vis[u]=1;
//		cout<<u<<" "<<d<<"\n";
		for(int v : p[u])
			q.push({v,d+1});
	}
}

signed main()
{
//	freopen("hamming.in","r",stdin);
//	freopen("hamming.out","w",stdout);
	cin>>n>>L;                 
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) cnt[a[i]]++;
	for(int i=0;i<(1<<L);i++)  
		for(int j=0;j<L;j++)   
			p[i].push_back(i^(1<<j));
	bfs();              
	for(int i=1;i<=n;i++)
		a[i]^=(1<<L)-1;       
	for(int i=1;i<=n;i++)
		cout<<(cnt[a[i]]>1?L:L-dis[a[i]])<<"\n";
	return 0;
}