【2024.10.22练习】机器人塔
题目描述

题目分析
由于数据小,直接考虑DFS搜索底层所有排列组合。
我的代码
需要注意:这个数据有点漏洞的是题干声明N+M<231,但实际上有个测试点是等于231的。
一开始在build_tower()函数中建完整个塔再判定是否合格,结果最大数据量下超时了。后面修改了函数,每添加一个机器人就判定一次是否合格,不合格直接退出函数,这样运行时间就在有效时长内了。因此对于时间复杂度在极限附近的程序,剪枝也是很有效的。
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_L=22;
int m; //A数量
int n; //B数量
int l; //层数:也是最底层的机器人数
bool bottom[MAX_L];//最底层机器人排列
bool tower[MAX_L][MAX_L];
//tower[i][j]表示第i层从左往右第j个机器人种类
int ans;
void build_tower(){//记录用于构筑的A,B数量int A=m;int B=n; //构建底层 for(int i=1;i<=l;i++){tower[l][i]=bottom[i]; if(!bottom[i]) A--;if(bottom[i]) B--;}//构建上层for(int i=l-1;i>0;i--){for(int j=1;j<=i;j++){tower[i][j]=tower[i+1][j]^tower[i+1][j+1]; //异或运算 if(!tower[i][j]) A--;if(tower[i][j]) B--;if(A<0||B<0) return;}}if(A==0&&B==0){ans++;//数量正确 }
}
void dfs(int a,int b,int x){//a,b为剩余A,B的数量 if(a<0||b<0||x>l) return;if(x==l){build_tower();return;}bottom[x+1]=0; dfs(a-1,b,x+1); //0代表Abottom[x+1]=1;dfs(a,b-1,x+1); //1代表B
}
int main()
{cin>>m>>n;for(int i=1;i<=21;i++){if(i*(i+1)/2==m+n){l=i;}}ans=0;dfs(m,n,0);cout<<ans;return 0;
}相关文章:
【2024.10.22练习】机器人塔
题目描述 题目分析 由于数据小,直接考虑DFS搜索底层所有排列组合。 我的代码 需要注意:这个数据有点漏洞的是题干声明NM<231,但实际上有个测试点是等于231的。 一开始在build_tower()函数中建完整个塔再判定是否…...
酒店预订订房小程序源码系统 多酒店入驻+打造类似美团的酒店模式 带完整的安装代码包以及搭建部署教程
系统概述 随着移动互联网的普及,小程序因其轻量级、无需下载安装、即用即走的特点,迅速成为各行业的标配。对于酒店预订行业而言,小程序不仅能够有效提升用户体验,还能降低运营成本,提高转化率。本源码系统正是基于这…...
springboot037基于SpringBoot的墙绘产品展示交易平台的设计与实现(论文+源码)_kaic
毕 业 设 计(论 文) 题目:墙绘产品展示交易平台设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本墙绘产品展示…...
YOLOv8实战人脸-口罩检测与识别【数据集+YOLOv8模型+源码+PyQt5界面】
本文采用YOLOv8作为核心算法框架,结合PyQt5构建用户界面,使用Python3进行开发。YOLOv8以其高效的实时检测能力,在多个目标检测任务中展现出卓越性能。本研究针对人脸-口罩数据集进行训练和优化,该数据集包含丰富的人脸-口罩图像样…...
《黑神话悟空》各章节boss顺序汇总
第一章BOSS顺序: 1、牯护院:犀牛精,位于苍狼岭娟,击败后能获得定身术。 2、广智:火刀狼, 位于观音禅院,击败后获得广智变身,记得敲钟。 3、蓝皮幽魂:蓝皮大头࿰…...
rust中cargo.toml详细介绍
1. cargo.toml介绍 Cargo.toml是 Rust 项目的配置文件,它使用 TOML(Tom’s Obvious, Minimal Language)格式。 1.1 基本结构 [package]:包含项目的基本信息。 name:项目名称。version:项目版本号。edition:Rust 版本,如 2018、2021 等。[package]name = "abc&q…...
jupyter notebook 笔记
nbclassic 经典版 新版的 jupyter notebook 太丑了。 最难受的是字体太小了。 我还是喜欢老版本的 jupyter notebook. 安装经典版: pip install nbclassic 启动经典版: jupyter server 或是 jupyter nbclassic 参考来源: https://github.com/jupyter/nbclassic jupyter note…...
Atlas800昇腾服务器(型号:3000)—CANN安装(二)
服务器配置如下: CPU/NPU:鲲鹏 CPU(ARM64)A300I pro推理卡 系统:Kylin V10 SP1【下载链接】【安装链接】 驱动与固件版本版本: Ascend-hdk-310p-npu-driver_23.0.1_linux-aarch64.run【下载链接】 Ascend-…...
考研鼓励小程序
考研冲刺倒计时,加入我们一起奋斗💥 考研倒计时提醒神器来啦! 距离考研越来越近,复习是否紧张又有些焦虑?不用担心!我特别制作了一个 考研倒计时提醒服务,每天在 7:00 和 23:59 准时为你发送倒…...
Wooden UI(木头UI纹理按钮边框 背景图标 带PNG素材)
资源包包含以下元素:按钮、图标、框架、复选框等,提供分层的 PSD 文件。 下载:Unity资源商店链接资源下载链接 效果图:...
WebRTC音频 03 - 实时通信框架
WebRTC音频01 - 设备管理 WebRTC音频 02 - Windows平台设备管理 WebRTC音频 03 - 实时通信框架(本文) WebRTC音频 04 - 关键类 WebRTC音频 05 - 音频采集编码 一、前言: 前面介绍了音频设备管理,并且以windows平台为例子,介绍了ADM相关的类…...
Maven陷阱揭秘:避开Java项目构建的10大常见误区
文章目录 引言基础知识核心概念示例演示实际应用深入与最佳实践常见问题解答结语学习资源互动环节 引言 Maven是Java项目中广泛使用的项目管理和构建自动化工具。它通过一个中央仓库和依赖管理系统,简化了项目的构建和依赖管理。理解Maven的依赖机制对于构建和维护…...
基础数据结构思路写法记录,便于回顾
重思路非代码。基础的思路搞懂了,变形题目顺着思考基本都能写出来! 二分查找 int binarySearch(vector<int> &nums, int target) {// write your code hereif (nums.empty()) {return -1;}int start 0;int end nums.size() - 1;while (star…...
基于AI的量化投资框架Qlib的Python依赖包pyqlib安装问题记录
版权声明:本文为博主原创文章,如需转载请贴上原博文链接:基于AI的量化投资框架Qlib的Python依赖包pyqlib安装问题记录-CSDN博客 前言:最近想使用Qlib来做量化交易的策略研究,但是第一步就卡在了安装pyqlib依赖包&#…...
《语音识别方案选择》
《语音识别方案选择》 一、引言二、语音识别技术概述(一)语音识别的基本原理(二)语音识别技术的发展历程(三)语音识别技术的分类1、基于声学模型的语音识别2、基于语言模型的语音识别3、端到端的语音识别 三…...
目标检测数据集图片及标签同步裁剪
目录 前言 具体方法 使用介绍 完整代码 前言 在目标检测任务中,模型的训练依赖于大量高质量的标注数据。然而,获取足够多的标注数据集往往代价高昂,并且某些情况下,数据集中的样本分布不均衡,这会导致模型的泛化能…...
【设计模式-简单工厂】
定义 简单工厂模式(Simple Factory Pattern)是一种创建型设计模式,用于通过一个工厂类来创建某个产品类的实例,而不直接在客户端(调用方)中实例化对象。 这种模式的主要思想是将对象的创建逻辑集中在一个…...
多个版本的GCC(GNU编译器集合)可以同时安装并存
在Ubuntu系统中,多个版本的GCC(GNU编译器集合)可以同时安装并存。GCC是编译C、C以及其他编程语言程序的重要工具,不同的项目可能需要不同版本的GCC来确保兼容性。 为什么需要多个GCC版本 项目依赖:不同的软件项目可能…...
量子纠错--shor‘s 码
定理1 (量子纠错的条件) C是一组量子编码,P是映射到C上的投影算子。假设是一个算子元素描述的量子操作,那么基于量子编码C,存在一个能对抗描述的噪声的纠错操作R的充要条件是 对某个复元素厄米矩阵成立。 将算子元素称为导致的错误。如果这样…...
机器学习2
一、模型评估方法 1.1 K折交叉验证法(K-Fold Cross Validation) 1.1.1 定义 K折交叉验证法是一种用于评估模型性能的技术。它将数据集分为K个相等的子集,模型会轮流使用一个子集作为测试集,其余K-1个子集作为训练集。这个过程会…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
