NO.72十六届蓝桥杯备战|搜索算法-DFS|选数|飞机降落|八皇后|数独(C++)
P1036 [NOIP 2002 普及组] 选数 - 洛谷
组合型枚举,路径⾥⾯记录选择数的「总和」。在选出k 个数之后,判断「是否是质数」
#include <bits/stdc++.h>
using namespace std;const int N = 25;
int n, k;
int a[N];int ret;
int path; //记录路径中所选择的数的和bool isprime(int x)
{if (x <= 1) return false;//试除法for (int i = 2; i <= x / i; i++){if (x % i == 0) return false; }return true;
}void dfs(int pos, int begin)
{if (pos > k){if (isprime(path)) ret++;return;}for (int i = begin; i <= n; i++){path += a[i];dfs(pos+1, i+1);path -= a[i];}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];dfs(1, 1);cout << ret << endl;return 0;
}
P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷
枚举所有⻜机的「全排列」,判断是否存在⼀种排列,使的全部的⻜机都能安全降落。
剪枝:
- 当前路径⾥⾯只能选没有选过的⻜机;
- 如果这架⻜机不能正常降落,剪掉;
- 如果已经找到⼀种安全降落的⽅式,停⽌枚举,可以通过「递归的返回值」判断是否搜索成功
#include <bits/stdc++.h>
using namespace std;const int N = 15;int n;
int t[N], d[N], l[N];
bool st[N];bool dfs(int pos, int end)
{if (pos > n){return true;}for (int i = 1; i <= n; i++){if (st[i] == true) continue; //剪枝if (end > t[i] + d[i]) continue; //剪枝int newend = max(t[i], end) + l[i];st[i] = true;if (dfs(pos+1, newend)) return true;st[i] = false; //恢复现场}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int T; cin >> T;while (T--){memset(st, 0, sizeof st);cin >> n;for (int i = 1; i <= n; i++) cin >> t[i] >> d[i] >> l[i];if (dfs(1, 0)) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}
P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷
枚举策略:
- 「⼀⾏⼀⾏」的放皇后:从第⼀⾏开始,尝试在每⼀列上放皇后;
- 如果当前列放上皇后之后「没有冲突」,就标记⼀下这个「放法」,记录⼀下当前⾏的决策,然后「递归」考虑下⼀⾏;
- 等到「所有⾏」都放置完毕之后,输出本次枚举的决策。
枚举策略应该是⽐较容易想到的,这道题的难点在于如何判断「在这⼀列放上这个皇后之后,是否冲突」。当我们⼀⾏⼀⾏放的时候,「⾏是不会产⽣冲突的」。产⽣冲突的只有「列」,「主对⻆线」,以及「副对⻆线」。我们可以⽤三个数组分别标记: col[i] = true
,表⽰第i ⾏放置了⼀个皇后;dig1[j - i + n] = true
,表⽰y = x + (j - i)
这条「主对⻆线」上放置了⼀个皇后;dig2[j + i] = true
,表⽰y = -x + (j + i)
这条「副对⻆线」上放置了⼀个皇后
#include <bits/stdc++.h>
using namespace std;const int N = 15;int n;
bool col[N], st1[N*2], st2[N*2];int ret;
vector<int> path;void dfs(int x)
{if (x > n){ret++;if (ret <= 3){for (auto x : path) cout << x << " ";cout << endl;}return;}for (int y = 1; y <= n; y++){//判断能不能摆在这一列if (col[y] || st1[y-x+n] || st2[x+y]) continue; //剪枝col[y] = st1[y-x+n] = st2[x+y] = true;path.push_back(y);dfs(x+1);col[y] = st1[y-x+n] = st2[x+y] = false;path.pop_back();}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;dfs(1);cout << ret << endl;return 0;
}
P1784 数独 - 洛谷
枚举策略:
- 「⼀个格⼦⼀个格⼦」往⾥⾯填数
- 从第⼀⾏的第⼀个格⼦开始,填上⼀个「没有冲突」的数,然后「递归」到下⼀个格⼦;
- 当某⼀⾏填满之后,递归到「下⼀⾏的起始位置」继续填数。
可以创建三个数组,⽤来帮助判断填上某⼀个数之后,是否会发⽣冲突。对于3x3⽅格,我们可以给每⼀个格⼦编上号,快读定位。 row[i][num] = true
表⽰:第i ⾏已经放上了num 这个数;col[j][num] = true
表⽰:第j 列已经放上了num 这个数;st[i/3][j/3][num] = true
表⽰:[i/3, j/3]
的3 × 3 ⽅格⾥,已经放上了num 这个数
#include <bits/stdc++.h>
using namespace std;int n = 9;
const int N = 10;
int a[N][N];
bool row[N][N], col[N][N], st[N][N][N];bool dfs(int i, int j)
{if (j == n){//填满一行后i++;j = 0;}if (i == n) return true;if (a[i][j]) return dfs(i, j+1);for (int x = 1; x <= 9; x++){if (row[i][x] || col[j][x] || st[i/3][j/3][x]) continue; row[i][x] = col[j][x] = st[i/3][j/3][x] = true;a[i][j] = x;if (dfs(i, j+1)) return true;row[i][x] = col[j][x] = st[i/3][j/3][x] = false;a[i][j] = 0;}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cin >> a[i][j];int x = a[i][j];if (x){//标记row[i][x] = col[j][x] = st[i/3][j/3][x] = true;}}}dfs(0, 0);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cout << a[i][j] << " "; }cout << endl;}return 0;
}
相关文章:
NO.72十六届蓝桥杯备战|搜索算法-DFS|选数|飞机降落|八皇后|数独(C++)
P1036 [NOIP 2002 普及组] 选数 - 洛谷 组合型枚举,路径⾥⾯记录选择数的「总和」。在选出k 个数之后,判断「是否是质数」 #include <bits/stdc.h> using namespace std;const int N 25; int n, k; int a[N];int ret; int path; //记录路径中所…...
网络Socket编程基于UDP协议模拟简易网络通信
一、预备知识 网络编程(Network Programming)是指编写程序来实现计算机网络之间的通信。这通常涉及到使用套接字(sockets)来建立连接、发送和接收数据。 (一)套接字 套接字(Socket࿰…...
rust 使用select退出线程
#[derive(Serialize, Deserialize, Debug, Clone, PartialEq)] pub struct Capture {clear: bool, // ????????interface: String, // ??times: u64, // ?? }pub async fn cmd_capture(State(web_env): State<ArcWebEnv>,Json(args): Json<C…...
C++学习day7
思维导图: 使用vector实现一个简单的本地注册登录系统 注册:将账号密码存入vector里面,注意防重复判断 登录:判断登录的账号密码是否正确 #include <iostream> #include <cstring> #include <cstdlib> #includ…...
【学习笔记】CoACD: 基于碰撞感知凹性与树搜索的近似凸分解
CoACD 基于碰撞感知凹性与树搜索的近似凸分解 CoACD 官方文档 CoACD(Convex Approximation of Complex Decompositions)是一种用于将复杂网格分解为多个凸包的算法, 专为 3D 网格设计了近似凸分解算法,强调在保持物体间潜在碰撞条件的同时减…...
Three.js 系列专题 6:后处理与特效
内容概述 后处理(Post-Processing)是在渲染完成后对画面进行额外的处理,以实现模糊、辉光、颜色校正等效果。Three.js 通过 EffectComposer 提供后处理支持。本专题还将简要介绍着色器和粒子系统,为更复杂的特效打基础。 学习目标 掌握 EffectComposer 的基本使用。实现辉…...
2025 年江苏保安员职业资格考试经验分享
江苏保安行业发展成熟,2025 年考试注重对考生综合素养的考查。报考条件常规,但对诚信记录有额外关注,如有不良信用记录可能影响报考资格。 报名在江苏省各地级市公安局指定点进行,提交资料包括身份证、学历证、个人诚信报告&am…...
亚马逊算法重构消费市场:解码2024年Q1北美站热搜商品的底层逻辑
在跨境电商迈入精细化运营时代的背景下,亚马逊平台最新发布的《2024年Q1零售搜索趋势报告》揭示了算法驱动下的消费新图景。数据显示,北美站点月均超300万人次重复搜索特定品类商品,健康生活、智能家居等五大领域形成持续增长极。这份由亚马逊…...
powershell绑定按钮事件的两种方式
写一个powershell的简单GUI做本地任务,试验出2个方法: 方法1: function btn1_click {write-host $text1.Text -ForegroundColor Green -BackgroundColor Black }$btn1.Add_Click({btn1_click})方法2: $btn2_click {write-host $…...
LearnOpenGL——OIT
教程地址:简介 - LearnOpenGL CN 简介 原文链接:LearnOpenGL - Introduction 前言 在混合(Blending)章节中,我们介绍了颜色混合的主题。混合是在3D场景中实现透明表面的方法。简而言之,透明度涉及到在计算…...
【蓝桥杯】Python大学A组第十五届省赛
1.填空题 1.1.拼正方形 问题描述 小蓝正在玩拼图游戏,他有个的方块和个的方块,他需要从中挑出一些来拼出一个正方形。 比如用个和个的方块可以拼出一个的正方形;用个的方块可以拼出一个的正方形。 请问小蓝能拼成的最大的正方形的边长为多少。 import math # 2*2的个数 a =…...
使用JS+HTML+CSS编写提词器实例
手搓提词器网页版,有些BUG但是基本功能使用没有问题,有需要的可复制粘贴,BUG自行修复。下面直接进入代码: <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><me…...
人工智能基础知识详解:从概念到前沿技术与应用
在数字化浪潮席卷全球的今天,人工智能(Artificial Intelligence,简称AI)已不再是科技前沿的神秘概念,而是融入我们日常工作的实用工具。从智能语音助手到自动驾驶汽车,从医疗影像诊断到生成式艺术创作&…...
重温经典,畅享怀旧游戏盛宴
FC街机是一款专为安卓设备设计的经典游戏合集应用,它将玩家熟悉的红白机(FC)游戏体验带到了移动设备上。这款应用不仅提供了丰富的游戏选择,还通过优化的界面和操作,让玩家能够随时随地享受经典游戏的乐趣。 游戏非常…...
CPU 压力测试命令大全
CPU 压力测试命令大全 以下是 Linux/Unix 系统下常用的 CPU 压力测试命令和工具,可用于测试 CPU 性能、稳定性和散热能力。 1. 基本压力测试命令 1.1 使用 yes 命令 yes > /dev/null & # 启动一个无限循环进程 yes > /dev/null & # 启动第二个进…...
Windows 系统下用 VMware 安装 CentOS 7 虚拟机超详细教程(包含VMware和镜像安装包)
前言 资源 一、准备工作 (一)下载 VMware Workstation (二)下载 CentOS 7 镜像 二、安装 VMware Workstation(比较简单,按下面走即可) 三、创建 CentOS 7 虚拟机 四、安装 CentOS 7 系统…...
QLineEdit的提交前验证
QLineEdit是pyqt中常用的输入控件,默认情况下,它可以接受键盘输入的任何可打印字符。有时候,我们需要在用户提交前对其输入的内容先行验证,当用户输入不符合预期时予以清空,这就需要对QLineEdit控件进行以下操作&#…...
【Linux高级IO(二)】初识epoll
目录 1、epoll的接口 2、epoll原理 3、epoll工作方式 1、epoll的接口 #include <sys/epoll.h> 1、int epoll_create(int size) :创建epoll模型 返回值是一个文件描述符,创建一个struct file结构体,指向epoll模型,返回的…...
2018年真题
数学基础 一、 (共4分)用逻辑符号表达下列语句(论域为包含一切事物的集合) 1、(2分)集合A的任一元素的元素都是A的元素 经过对图片文字的识别与逻辑分析,结果如下: 符号定义&…...
Linux xxd命令
目录 一. xxd命令简介二. 简单使用三. -p选项纯16进制输出四. -r选项将十六进制还原成原始内容五. 小应用 一. xxd命令简介 xxd 是一个将文件或输入内容转换为十六进制(Hex Dump)格式的工具,也可以将十六进制恢复成原始数据。 它在调试二进制…...
高校实验室安全数智化分级分类管理-危化品管理LIMS
一、背景与依据 传统实验室安全管理如同老式挂钟,齿轮咬合处总会随时间产生间隙。为进一步规范学校实验室建设与适用,从源头管控实验室和实验项目安全风险,确保教学科研活动安全有序开展,分级分类体系构建如同绘制实验室的"…...
春芽儿智能跳绳:以创新技术引领运动健康新潮流
在全球运动健康产业蓬勃发展的浪潮中,智能健身器材正成为连接科技与生活的重要纽带。据《中国体育用品产业发展报告》显示,2023年中国智能运动装备市场规模突破千亿元,其中跳绳类目因兼具大众普及性与技术升级空间,年均增速超30%。…...
Fast网络速度测试工具
目录 网站简介 功能特点 测试过程 为什么使用Fast 如果网络速度不达标 网站简介 Fast是一个由Netflix提供的网络速度测试工具,主要用来测试用户的互联网下载速度。它以其简洁的界面和快速的测试过程而受到用户的欢迎。 功能特点 下载速度测试:这是…...
java的文件输入输出流(FileInputStream、FileOutputStream、FileReader、FileWriter)
文章目录 文件输入输出流1 java I/O 流的原理流的分类 2 FileInputStream 文件字节输入流3 FileOutputStream 文件字节输出流4 使用文件字节输入输出流完成对文件的拷贝5 FileReader 文件字符输入流6 FileWriter 文件字符输出流 文件输入输出流 1 java I/O 流的原理 I/O 是 In…...
stm32week10
stm32学习 七.CAN 7.STM32 CAN外设 标识符过滤器: 每个过滤器的核心由两个32位寄存器组成:R1[31:0]和R2[31:0] FSCx:位宽设置,置0为16位,置1为32位 FBMx:模式设置,置0为屏蔽模式,…...
【UnityEditor扩展】如何在 Unity 中创建棱柱体(用作VR安全区检测),同时在编辑器插件中实现与撤销/恢复功能
Unity 编辑器扩展:3D 空间中绘制安全区棱柱体(含撤销/恢复/保存/读取) 在虚拟现实(VR)和增强现实(AR)开发中,安全区是保障用户安全的重要组成部分。通过精确控制用户活动范围&#…...
C++小游戏 合集
生化危机 #include<conio.h> #include<string.h> #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<time.h> #include<direct.h> int n,round,gold0; bool f1,f2,f3,deadfalse,PC_64Bit; char str[4]; struct n…...
常州 d??
回来了! 今天(?发出来的时候可能已经是第二天了吧 真的爆零了qaq 挺难的 最高分只有100 而且t2t3t4一个人都没拿分qaq 这段时间在写网络流 唉博客还是不要写太水了 抄一点网络流代码上来 EK不写了 dinic会就行了 板子题洛谷p3376 dini…...
juc并发包的常用类、线程安全实现方式、锁机制及 JVM 优化策略
juc并发包的常用类、线程安全实现方式、锁机制及 JVM 优化策略 1. juc包下的常用类:线程池:并发集合类:同步工具类:原子类: 2. 怎么保证多线程安全:3. Java中常用锁及使用场景:4. 线程同步的方法…...
学习日记-0407(Inductive Matrix Completion Using Graph Autoencoder)
论文阅读:Inductive Matrix Completion Using Graph Autoencoder 代码:swtheing/IMC-GAE 总而言之就是设计了一个不同评分下的邻接图,然后对每一个评分图T进行独立GNN编码。这个 GNN 编码器主要由三个组件构成:嵌入层、消息传递层…...
FPGA入门:状态机思想编程
一、状态机思想编写流水灯 1、状态机思想的概念 状态机思想是一种用于描述和处理具有多个状态以及状态之间转换关系的系统的思维方式。以下是对其主要概念、应用场景和优势的介绍: 主要概念 状态:指系统在某一时刻的状况或条件。例如,在一…...
【电路笔记】-切换触发器
切换触发器 文章目录 切换触发器1、概述2、切换触发器3、JK触发器转换为D型触发器4、D型触发器转换为切换触发器切换触发器是常用的时序逻辑电路,作为单个比特双稳态存储元件,在计数器、存储器设备中经常使用,或作为响应时钟脉冲的分频器。 1、概述 切换触发器是另一种基于…...
示例项目文档模板集:TaskBoard 任务管理系统
一套完整、高可读性、结构清晰的项目文档模板,适用于中小型软件项目的设计、开发、交接与展示全流程。 📌 项目概述文档(overview.md) 📂 项目名称:TaskBoard 🧭 项目简介 TaskBoard 是一款专为敏捷团队打造的任务管理系统,支持任务分配、状态追踪与协作沟通,帮…...
TF-IDF忽略词序问题思考
自从开始做自然语言处理的业务,TF-IDF就是使用很频繁的文本特征技术,他的优点很多,比如:容易理解,不需要训练,提取效果好,可以给予大规模数据使用,总之用的很顺手,但是人…...
代理模式的优缺点是什么?
什么是代理模式? 代理模式(Proxy Pattern)是一种结构型设计模式,它通过创建代理对象来控制对原始对象的访问。 这种模式在前端开发中广泛应用,特别是在需要控制对象访问、添加额外逻辑或优化性能的场景中。 核心…...
十分钟上手:Distilling the Knowledge in a Neural Network
概述:知识蒸馏是一种模型压缩技术,通过让轻量化的学生模型模仿复杂教师模型的输出概率分布,结合软目标和硬目标进行训练,从而将教师模型的泛化能力迁移至学生模型,实现小模型的高效部署而不显著降低性能。 硬目标&…...
百度的deepseek与硅基模型的差距。
问题: 已经下载速度8兆每秒,请问下载30G的文件需要多长时间? 关于这个问题。百度的回答如下: 30GB文件下载时间计算 理论计算(基于十进制单位): 单位换算 文件大小:3…...
OpenCV 图形API(18)用于执行两个矩阵(或数组)的逐元素减法操作函数sub()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 描述 计算两个矩阵之间的逐元素差值。 sub 函数计算两个矩阵之间的差值,要求这两个矩阵具有相同的尺寸和通道数: dst ( I ) src…...
布谷一对一直播源码android版环境配置流程及功能明细
一:举例布谷交友(一对一直播源码)搭建部署的基本环境说明 1. 首先安装Center OS 7.9系统,硬盘最低 40G 2. 安装宝塔环境 https://bt.cn(强烈推荐使用) 3. 安装环境 ● PHP 7.3(安装redis扩展…...
#MongoDB 快速上手
docker pull mongo docker run -d --name my-mongo -p 27017:27017 mongo docker exec -it my-mongo mongo 🚪进入 Mongo Shell 后的第一步 你进入后会看到类似提示符: >说明已经进入 Mongo Shell,现在就可以操作数据库了。 …...
docker相关命令
常用命令 #创建并启动 docker-compose up -d # 启动之后就可以通过浏览器访问了 #停止并删除 docker-compose down #重启 docker-compose restart #停止 docker-compose stop #启动 docker-compose startdocker search #搜索镜像(只搜索官方仓库的,官方仓库地址&am…...
浅谈进程与程序的区别
如大家所了解的,进程与程序是有区别的。 下面做了一个总结,供大家参考、学习: 1. 程序是指令的有序集合,是一个静态的概念,其本身没有任何运行的含义。进程是程序在 CPU 上的一次执行过程,是一个动态的概…...
redis 和 MongoDB都可以存储键值对,并且值可以是复杂json,用完整例子分别展示说明两者在存储json键值对上的使用对比
Redis 存储 JSON 键值对示例 存储操作: // 存储用户信息(键:user:1001,值:JSON对象) SET user:1001 {"name":"Alice", "age":30, "address":"New York&quo…...
基于chatgpt得到的生活成本计算
意大利的生活成本因城市而异,比如米兰和罗马相对较贵,而南部城市如那不勒斯或巴勒莫则便宜一些。下面是意大利大致的基本生活成本和费用明细(以欧元€为单位,2025年初数据为基础,具体数值可能随时间和汇率略有变化&…...
C和C++有什么区别?
C和C是两种不同的编程语言,虽然它们有许多相似之处,但也存在一些关键的区别。 C是一种过程化编程语言,专注于函数和流程控制,非常适合系统级编程。而 C是一种面向对象编程语言,支持类、对象和封装、继承、多态等特性。…...
力扣1338 === 贪心算法解决数组减半问题
目录 问题分析 方法思路:贪心算法 步骤分解 代码解释 复杂度分析 正确性证明 示例验证 边界情况 总结 要解决这个问题,我们需要找到最少需要删除的不同整数集合,使得剩余的元素个数不超过原数组的一半。以下是对该问题的详细分析和解…...
企业知识库如何搭建?应对高频咨询的AI自助问答系统
在客户服务和内部沟通中,“同样的问题被反复问”、“信息找不到”、“新员工上手慢”等现象屡见不鲜。为了提升企业运营效率,越来越多企业开始重视知识库建设,而“企业知识库如何搭建”也成为热门话题。 尤其在AI技术快速发展的今天…...
UE5学习笔记 FPS游戏制作44 统一UI大小 sizeBox
如果我们希望多个类似的UI大小一样,例如不同菜单的标题,可以使用sizeBox组件 我们在标题控件上,用sizeBox包裹所有子物体 然后指定他的最小宽高,或最大宽高 如果指定的是最小宽高,当子元素(如图片…...
SpringAOP新链浅析
前言 在复现CCSSSC软件攻防赛的时候发现需要打SpringAOP链子,于是跟着前人的文章自己动手调试了一下 参考了大佬的文章 https://gsbp0.github.io/post/springaop/#%E6%B5%81%E7%A8%8B https://mp.weixin.qq.com/s/oQ1mFohc332v8U1yA7RaMQ 正文 依赖于Spring-AO…...
高效网页截图利器:支持长截图、异步加载内容截图、API调用、Docker一键部署!
一、简介 利用playwright自动化工具,模拟浏览器打开网页,实现完整网页截图功能支持长截图,支持异步加载动态渲染内容截图支持docker一键部署支持API调用项目地址:https://github.com/luler/hello_screenshot 二、安装 提前安装好d…...