当前位置: 首页 > news >正文

【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练习】机器人塔

题目描述 题目分析 由于数据小&#xff0c;直接考虑DFS搜索底层所有排列组合。 我的代码 需要注意&#xff1a;这个数据有点漏洞的是题干声明NM<231&#xff0c;但实际上有个测试点是等于231的。 一开始在build_tower&#xff08;&#xff09;函数中建完整个塔再判定是否…...

酒店预订订房小程序源码系统 多酒店入驻+打造类似美团的酒店模式 带完整的安装代码包以及搭建部署教程

系统概述 随着移动互联网的普及&#xff0c;小程序因其轻量级、无需下载安装、即用即走的特点&#xff0c;迅速成为各行业的标配。对于酒店预订行业而言&#xff0c;小程序不仅能够有效提升用户体验&#xff0c;还能降低运营成本&#xff0c;提高转化率。本源码系统正是基于这…...

springboot037基于SpringBoot的墙绘产品展示交易平台的设计与实现(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;墙绘产品展示交易平台设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本墙绘产品展示…...

YOLOv8实战人脸-口罩检测与识别【数据集+YOLOv8模型+源码+PyQt5界面】

本文采用YOLOv8作为核心算法框架&#xff0c;结合PyQt5构建用户界面&#xff0c;使用Python3进行开发。YOLOv8以其高效的实时检测能力&#xff0c;在多个目标检测任务中展现出卓越性能。本研究针对人脸-口罩数据集进行训练和优化&#xff0c;该数据集包含丰富的人脸-口罩图像样…...

《黑神话悟空》各章节boss顺序汇总

第一章BOSS顺序&#xff1a; 1、牯护院&#xff1a;犀牛精&#xff0c;位于苍狼岭娟&#xff0c;击败后能获得定身术。 2、广智&#xff1a;火刀狼&#xff0c; 位于观音禅院&#xff0c;击败后获得广智变身&#xff0c;记得敲钟。 3、蓝皮幽魂&#xff1a;蓝皮大头&#xff0…...

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安装(二)

服务器配置如下&#xff1a; CPU/NPU&#xff1a;鲲鹏 CPU&#xff08;ARM64&#xff09;A300I pro推理卡 系统&#xff1a;Kylin V10 SP1【下载链接】【安装链接】 驱动与固件版本版本&#xff1a; Ascend-hdk-310p-npu-driver_23.0.1_linux-aarch64.run【下载链接】 Ascend-…...

考研鼓励小程序

考研冲刺倒计时&#xff0c;加入我们一起奋斗&#x1f4a5; 考研倒计时提醒神器来啦&#xff01; 距离考研越来越近&#xff0c;复习是否紧张又有些焦虑&#xff1f;不用担心&#xff01;我特别制作了一个 考研倒计时提醒服务&#xff0c;每天在 7:00 和 23:59 准时为你发送倒…...

Wooden UI(木头UI纹理按钮边框 背景图标 带PNG素材)

资源包包含以下元素&#xff1a;按钮、图标、框架、复选框等&#xff0c;提供分层的 PSD 文件。 下载&#xff1a;​​Unity资源商店链接资源下载链接 效果图&#xff1a;...

WebRTC音频 03 - 实时通信框架

WebRTC音频01 - 设备管理 WebRTC音频 02 - Windows平台设备管理 WebRTC音频 03 - 实时通信框架(本文) WebRTC音频 04 - 关键类 WebRTC音频 05 - 音频采集编码 一、前言&#xff1a; 前面介绍了音频设备管理&#xff0c;并且以windows平台为例子&#xff0c;介绍了ADM相关的类…...

Maven陷阱揭秘:避开Java项目构建的10大常见误区

文章目录 引言基础知识核心概念示例演示实际应用深入与最佳实践常见问题解答结语学习资源互动环节 引言 Maven是Java项目中广泛使用的项目管理和构建自动化工具。它通过一个中央仓库和依赖管理系统&#xff0c;简化了项目的构建和依赖管理。理解Maven的依赖机制对于构建和维护…...

基础数据结构思路写法记录,便于回顾

重思路非代码。基础的思路搞懂了&#xff0c;变形题目顺着思考基本都能写出来&#xff01; 二分查找 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安装问题记录

版权声明&#xff1a;本文为博主原创文章&#xff0c;如需转载请贴上原博文链接&#xff1a;基于AI的量化投资框架Qlib的Python依赖包pyqlib安装问题记录-CSDN博客 前言&#xff1a;最近想使用Qlib来做量化交易的策略研究&#xff0c;但是第一步就卡在了安装pyqlib依赖包&#…...

《语音识别方案选择》

《语音识别方案选择》 一、引言二、语音识别技术概述&#xff08;一&#xff09;语音识别的基本原理&#xff08;二&#xff09;语音识别技术的发展历程&#xff08;三&#xff09;语音识别技术的分类1、基于声学模型的语音识别2、基于语言模型的语音识别3、端到端的语音识别 三…...

目标检测数据集图片及标签同步裁剪

目录 前言 具体方法 使用介绍 完整代码 前言 在目标检测任务中&#xff0c;模型的训练依赖于大量高质量的标注数据。然而&#xff0c;获取足够多的标注数据集往往代价高昂&#xff0c;并且某些情况下&#xff0c;数据集中的样本分布不均衡&#xff0c;这会导致模型的泛化能…...

【设计模式-简单工厂】

定义 简单工厂模式&#xff08;Simple Factory Pattern&#xff09;是一种创建型设计模式&#xff0c;用于通过一个工厂类来创建某个产品类的实例&#xff0c;而不直接在客户端&#xff08;调用方&#xff09;中实例化对象。 这种模式的主要思想是将对象的创建逻辑集中在一个…...

多个版本的GCC(GNU编译器集合)可以同时安装并存

在Ubuntu系统中&#xff0c;多个版本的GCC&#xff08;GNU编译器集合&#xff09;可以同时安装并存。GCC是编译C、C以及其他编程语言程序的重要工具&#xff0c;不同的项目可能需要不同版本的GCC来确保兼容性。 为什么需要多个GCC版本 项目依赖&#xff1a;不同的软件项目可能…...

量子纠错--shor‘s 码

定理1 (量子纠错的条件) C是一组量子编码&#xff0c;P是映射到C上的投影算子。假设是一个算子元素描述的量子操作&#xff0c;那么基于量子编码C&#xff0c;存在一个能对抗描述的噪声的纠错操作R的充要条件是 对某个复元素厄米矩阵成立。 将算子元素称为导致的错误。如果这样…...

机器学习2

一、模型评估方法 1.1 K折交叉验证法&#xff08;K-Fold Cross Validation&#xff09; 1.1.1 定义 K折交叉验证法是一种用于评估模型性能的技术。它将数据集分为K个相等的子集&#xff0c;模型会轮流使用一个子集作为测试集&#xff0c;其余K-1个子集作为训练集。这个过程会…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

小智AI+MCP

什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析&#xff1a;AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github&#xff1a;https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...

在Spring Boot中集成RabbitMQ的完整指南

前言 在现代微服务架构中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件&#xff0c;支持多种消息协议&#xff0c;具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...

智能体革命:企业如何构建自主决策的AI代理?

OpenAI智能代理构建实用指南详解 随着大型语言模型&#xff08;LLM&#xff09;在推理、多模态理解和工具调用能力上的进步&#xff0c;智能代理&#xff08;Agents&#xff09;成为自动化领域的新突破。与传统软件仅帮助用户自动化流程不同&#xff0c;智能代理能够自主执行工…...