前言:
BFS 即广度优先搜索(或宽度优先搜索),具体定义和实现不在赘述。
本文所有代码前的开头头文件,宏定义和命名空间如下(只是一些常用的 define 和一个快读):
#include <bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define ll long long #define CI const int #define RI int #define W while #define gc getchar #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)<(y)?(x):(y)) #define Mt(a,x) memset((a),(x),sizeof(a)) using namespace std; namespace SlowIO { void Readc (char& c) {W (isspace (c = gc ()));} Tp void Read (Ty& x) {char c; int f = 1; x = 0; W (! isdigit (c = gc ())) f = c ^ '-' ? 1 : -1; W (x = (x * 10) + (c ^ 48), isdigit (c = gc ())); x *= f;} Ts void Read (Ty& x, Ar&... y) {Read (x); Read (y...);} } using namespace SlowIO;
1.[USACO23OPEN] Field Day S
summarization
给定 \(n\) 个长度为 \(m\) 的字符串(仅由 GH
组成),定义 calc(x,y)
表示两个字符串不一样的位的个数,需要求出每一个字符串 \(s\) 的 \(\max\limits_{i\in\text{给出的字符串}}calc(s,i)\) 。(\(1\le m\le18,1\le n\le10^5\))
solution
明显的,考虑转化为求 \(\min\)。先将字符串转化为 01
序列,即可以表示为一个十进制整数。
定义 “一个整数 \(x\) 的 \(\min/\max\)” 术语:即为此整数 \(x\) 对应的字符串 \(s_x\) 的 \(\min/\max_{i\in\text{给出的字符串}}calc(s_x,i)\)
对于一个整数 \(x\),考虑求 \(y=2^m-1-x\) 的 \(\min\),即为 \(x\) 的 \(\max\)。
证明:易知,\(y\) 即为 \(x\) 的前 \(m\) 位取反后的数值。求出和 \(y\) 最接近的值,就是和前 \(m\) 位取反后的 \(x\) 的最远的值。得证。
定义 “一步”:将一个整数的二进制表示上的一位取反。
所以问题变为:求 \(y\) 最少经过几步可以变为给定的整数(字符串可以转化为整数),求得后将 \(m\) 减去它即为答案。
考虑一个问题:在一个迷宫中有一个入口和若干个出口,需要求出从入口开始走出迷宫的最小步数。
基本思路是反向求解,将出口加入 BFS 队列中,通过 BFS 求得最短的出口走向入口的路径。
类比到此题,将给定整数加入队列,通过 BFS 一步一步求得给定整数到 \(0\sim2^m-1\) 所有状态的最少步数,即为所有状态下最短到达某个目标状态的步数。
最终对于 \(\forall x\),求出 \(2^m-1-x\) 的 \(\min\),输出 \(m-\min\) 即可。
得解。
code
CI N = 1e5, B = (1 << 18); int m, n, a[N + 5], dis[B + 5]; struct node {int x; int val;} h, p, r; queue <node> q;
int main () {
RI i, j; for (Read (m, n), i = 1; i <= n; ++ i) {char ch = getchar (); W (ch != '\n') a[i] = (a[i] << 1) + (ch == 'H'), ch = getchar ();} Mt (dis, -1);
for (i = 1; i <= n; ++ i) {h.x = a[i]; h.val = 0; q.push (h); dis[a[i]] = 0;} W (! q.empty ()) {
p = q.front (); q.pop (); for (i = 0; i < m; ++ i) {int o = p.x ^ (1 << i); if (dis[o] == -1) dis[o] = p.val + 1, r.x = o, r.val = p.val + 1, q.push (r);}
} for (i = 1; i <= n; ++ i) {printf ("%d\n", m - dis[(1 << m) - 1 - a[i]]);}
return 0;
}
标签:min,max,整数,BFS,应用,简单,字符串,define
From: https://www.cnblogs.com/ClapEcho233/p/17360541.html