[USACO23OPEN] Field Day S 题解

· · 题解

前言

一月进金组之后，就没怎么关注银组的消息。

3 月的 OPEN 赛季我们学校有几个人去参加银组，赛后 @ZYC210712 大佬分享了他在银组 T2 的广搜思路。本篇题解的思路就来自该大佬。

解法

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

将 G 和 H 视为二进制下的 0 和 1，本题就可以转化成：

给定 n 整数 a_1,a_2,\ldots,a_n 的二进制表示，\forall 1\le i\le n，求 \max\limits_{j=1}^n\ \operatorname{popcount}\left(a_i\bigoplus a_j\right) 的值。

这里 \bigoplus 表示按位异或，\operatorname{popcount} 表示一个整数二进制表示下 1 的个数。

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

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

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

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

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int c,n; cin>>c>>n;
  vector<int> a(n),m(1<<c,-1);
  queue<pair<int,int> > q;
  for(auto &i:a){
    for(int j=0;j<c;j++){
      char x; cin>>x;
      if(x=='G')i|=1<<j;
    }
    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]<<endl;
  return 0;
}