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;
}

经典转化题。

$x,y$ 两数的海明距离等于 $\operatorname{popcount}(x\oplus y)$，想要最大化该值很困难，但是最小化该值是很容易的，我们只需要把每个数抽象成一个节点，然后让每个数字向与其海明距离为 $1$ 的数字连边，最后跑多源 bfs 即可得到结果。同时注意到：

$$\operatorname{popcount}(x\oplus y)=L-\operatorname{popcount}(x\oplus \neg y) $$

等价于最小化 $\operatorname{popcount}(x\oplus \neg y)$，采用上述算法即可。

由于与每个数字海明距离为 $1$ 的数只有 $L$ 个，所以时间复杂度为 $O(L2^L)$。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=(1LL<<18);
ll dis[N],a[N],n,L,qu[N],front,rear;
bool vis[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>L;
	for(ll i=1;i<=n;i++){
		string s;cin>>s;s=' '+s;
		for(ll j=1;j<=L;j++){
			a[i]<<=1;
			if(s[j]=='1') a[i]+=1; 
		}
		if(vis[a[i]]) continue; 
		qu[rear++]=a[i];
		vis[a[i]]=1;
	}
	while(front<rear){
		ll now=qu[front++];
		for(ll i=0;i<L;i++){
			ll to=now^(1LL<<i);
			if(vis[to]) continue;
			vis[to]=1;dis[to]=dis[now]+1;
			qu[rear++]=to;
		}
	}
	ll chg=(1LL<<L)-1;
	for(ll i=1;i<=n;i++) cout<<L-dis[a[i]^chg]<<"\n"; 
	return 0;
}

也不知道为什么，写了一发暴力就过了，，，，

我们考虑 $haming(x,y)=popcnt(x\oplus y)$，设$z=x\oplus y$，然后我们把 $z$ 按照其 $popcnt$ 从大到小的顺序预处理出来，然后我们对于每一种数直接从大到小枚举海明距离，如果可以就停掉并且输出。

我们发现每一种数字的答案是一样的，考虑对于每一种数开一个 $res$ ，记录每一种数的答案，如果之前算过了，就直接输出。

复杂度 $O(玄学）$ ，我也不知道复杂度到底对不对。。。

求 $hack$ 或者复杂度分析

#include<bits/stdc++.h>
using namespace std;
inline int read_bit(){
	char ch=getchar(); 
	while(ch<'0'||ch>'9')ch=getchar();
	int x=0;
	while('0'<=ch&&ch<='9')x=(x<<1)+(ch^48),ch=getchar();
	return x;
}
inline int lowbit(int x){return x&-x;}
inline int popcnt(int x){
	int ans=0;
	while(x)ans++,x-=lowbit(x);
	return ans;
}bool vis[300005];
int res[300005];
int a[100005];
vector<int>vec[20];
int main(){
//	freopen("514.in","r",stdin);
//	freopen("514.out","w",stdout);
	int n,l;
	scanf("%d%d",&n,&l);
	for(int i=1; i<=n; i++){
		a[i]=read_bit();
		vis[a[i]]=1;
	}for(int i=0; i<(1<<l); i++)vec[popcnt(i)].push_back(i);
	for(int i=1; i<=n; i++){
		if(!res[a[i]]){
			for(int j=l; j>=0; j--){
				for(int k=0; k<vec[j].size(); k++){
					if(vis[vec[j][k]^a[i]]){
						res[a[i]]=j;
						break;
					}
				}if(res[a[i]]){
					break;
				}
			}
		}printf("%d\n",res[a[i]]);
	}
	return 0;
}