[COCI2022-2023 #5] Diskurs 题解

FFTotoro · 2023-04-07 21:21:10 · 题解

本题可以使用广度优先搜索。

定义两个“相邻”的整数 a,b 为满足如下条件的整数：

考虑广搜，对于每个给出的整数为源点开始搜。每次搜相邻的整数，若该整数没被搜过，该整数步数 +1，将该整数放入队列。

最后对于每个 a_i，求出 b=2^m-1-a_i（即 a_i 从右往左数 m 位按位取反的值）的“步数”x，答案即为 m-x。

原理：“最大的异或 \operatorname{popcount}”（即汉明距离）即为总位数 m 减去“b 最小的异或 \operatorname{popcount}”，而最小的答案即为广搜出来 b 的步数。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n,c; cin>>n>>c;
  vector<int> a(n),m(1<<c,-1);
  queue<pair<int,int> > q;
  for(auto &i:a)
    cin>>i,q.emplace(i,m[i]=0);
  while(!q.empty()){
    auto [u,w]=q.front(); q.pop();
    for(int i=0;i<c;i++)
      if(int v=u^(1<<i);m[v]==-1)
        q.emplace(v,m[v]=w+1);
  }
  for(int i:a)cout<<c-m[(1<<c)-1^i]<<' ';
  return 0;
}