首页 > 其他分享 >BFS 简单应用

BFS 简单应用

时间:2023-04-27 23:47:38浏览次数:41  
标签:min max 整数 BFS 应用 简单 字符串 define

前言:

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

相关文章

  • C++实现一个简单的生产者-消费者队列
    本文的代码都是ChatGPT生成,我只是做了微小的调整和整合,AI提示词如下:设计一个C++类,支持生产者-消费者模型,可以通过size函数获取剩余数量可能第一次生成的不一定合适,多刷新几次。生成的ProducerConsumerQueue.h代码如下:#ifndefPRODUCER_CONSUMER_QUEUE_H#definePRODUCER_CON......
  • 视觉定位领域专栏(一)领域介绍、应用场景和研究难点
    前言 本篇主要介绍三个方面,即视觉定位领域介绍、应用场景以及研究难点,同时会对专栏后续讲解内容做一个概述。本教程禁止转载。同时,本教程来自知识星球【CV技术指南】更多技术教程,可加入星球学习。欢迎关注公众号CV技术指南,专注于计算机视觉的技术总结、最新技术跟踪、经典论文......
  • 计算机网络基础——10 活动目录AD的配置和应用
    10.1实验目的1.了解域和活动目录的概念2.掌握 Windows server 2003 中活动目录 AD 的安装与配置3.掌握加入域和登录域的方法10.2实验相关知识:域与活动目录的概念  一台 Windows 计算机,在网络中要么隶属于工作组,要么隶属于域。工作组通常是几部计算机组成的逻辑集合,又......
  • TSINGSEE城市“一网统管”平台—智慧平安小区的场景应用
    随着城市建设进程的不断加快,关于城市的智能化治理需求也随之增多。在国家发布的“十四五”规划中,已经明确指出,推进新型城市建设,推行城市运行一网统管。作为推动城市治理体系和治理能力现代化的重要探索,“一网统管”将成为关键基础工程。“一网统管”的本质,是指充分运用大数据、云......
  • 浅谈机器学习的学习策略及技术应用
    导言:在科技飞速发展的今天,机器学习已成为人工智能领域的重要组成部分。作为一名程序员,掌握机器学习技术已经成为提升自身竞争力的必备技能。本文将从学习策略和技术应用两个方面,探讨机器学习的相关内容。一、学习策略加强基础知识:机器学习是建立在数学、统计学、计算机科学等多个学......
  • flask简单实现
    一、flask简介二、flask安装及简单实现三、问题 一、flask简介Flask本身相当于一个内核,其他几乎所有的功能都要用到扩展(邮件扩展Flask-Mail,用户认证Flask-Login,数据库Flask-SQLAlchemy),都需要用第三方的扩展来实现。比如可以用Flask扩展加入ORM、窗体验证工具,文件......
  • eclipse创建一个简单的MyBatis项目
    1.创建一个web应用程序 2.输入项目名称 3.在lib文件夹中添加jar包 4.在src文件夹中创建com.demo.po,com.demo.mapper,com.demo.dao三个包,并创建MyBatis框架配置文件mybatis-config.xml文件,在mapper目录下创建数据实体映射文件CommodityStorageMapper.xml,在po目录下创建名为......
  • Kivy中的Logger组件用于记录应用程序的日志信息
    name:可选参数,指定Logger组件的名称。默认为root。level:可选参数,指定Logger组件的记录级别。默认为debug。propagate:可选参数,指定是否向父Logger组件传递记录消息。默认为True。handlers:可选参数,指定Logger组件的处理程序。默认为None。disabled:可......
  • 用C++编写一个简单的发布者和订阅者
    摘要:节点(Node)是通过ROS图进行通信的可执行进程。本文分享自华为云社区《编写一个简单的发布者和订阅者》,作者:MAVER1CK。@[toc]参考官方文档:Writingasimplepublisherandsubscriber(C++)背景节点(Node)是通过ROS图进行通信的可执行进程。在本教程中,节点将通过话题(To......
  • 借助尾号限行 API 实现限行规则应用的设计思路分析
    引言尾号限行是指根据车牌号的末尾数字,规定某些时段内不能在特定区域行驶,这是城市交通管理的一种措施。尾号限行政策的实施可以缓解城市交通拥堵问题,减少环境污染和交通事故等问题。尾号限行API是一种提供已知所有执行限行政策的城市(如中国大陆等地)未来一段时间内机动车尾号限......