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

牛客网 NC16407 题解：托米航空公司的座位安排问题

news 来源：原创 2025/7/4 18:18:26

牛客网 NC16407 题解：托米航空公司的座位安排问题

题目分析

在这里插入图片描述

解题思路

本题可以采用深度优先搜索(DFS)来解决：

从左上角开始，按行优先顺序遍历每个座位
对于每个座位，有两种选择：
- 选择该座位（如果满足条件）
- 不选择该座位
使用二维数组 st[][] 记录座位状态
当选择了 K 个座位时，方案数加1

代码详解

#include <bits/stdc++.h>
using namespace std;// 全局变量定义
int n, m, k, ans;  // n行m列，选择k个座位，ans记录答案
const int N = 90;  // 数组大小
const int P = 420047;  // 取模数
int st[N][N];  // 记录座位状态// DFS函数：x,y表示当前位置，u表示已选择的座位数
void dfs(int x, int y, int u) {// 如果已经选择了k个座位，方案数+1if(u == k) {ans++;ans %= P;return;}// 如果当前列超出范围，移动到下一行第一列if(y > m) {y = 1;x++;}// 如果所有位置都遍历完，返回if(x > n) return;// 尝试选择当前位置if(!st[x-1][y] && !st[x][y-1]) {  // 检查上方和左方是否为空st[x][y] = 1;  // 标记为已选dfs(x, y+1, u+1);  // 继续搜索下一个位置st[x][y] = 0;  // 回溯，取消选择}// 不选择当前位置，继续搜索dfs(x, y+1, u);
}int main() {int t;cin >> t;  // 读入测试用例数while(t--) {cin >> n >> m >> k;  // 读入行列数和需要选择的座位数ans = 0;  // 初始化答案dfs(1, 1, 0);  // 从(1,1)开始搜索cout << ans % P << endl;  // 输出结果}return 0;
}

算法分析

时间复杂度：O(2^(M*N))，最坏情况下需要遍历所有可能的组合
空间复杂度：O(M*N)，主要用于存储座位状态数组

优化建议

可以添加剪枝优化，比如：
- 当剩余未遍历的座位数小于还需要选择的座位数时，直接返回
- 可以预处理每个位置可以选择的座位数，提前判断是否可能达到目标
对于大规模数据，可以考虑使用动态规划或状态压缩DP来优化

注意事项

数组大小要开够，题目中说明 N*M <= 80，所以开90足够
注意取模运算，每次更新答案时都要取模
回溯时要记得恢复状态

总结

这道题目是一个典型的DFS回溯问题，通过合理的状态记录和回溯，可以有效地求解所有合法的座位安排方案。代码实现简洁，但要注意细节处理，如边界条件和状态恢复。

牛客网 NC16407 题解：托米航空公司的座位安排问题

牛客网 NC16407 题解：托米航空公司的座位安排问题题目分析解题思路本题可以采用深度优先搜索(DFS)来解决： 从左上角开始，按行优先顺序遍历每个座位对于每个座位，有两种选择： 选择该座位（如果满足条件…...

编程日记 2025/7/4 18:18:26

拉普拉斯高斯（LoG）滤波器掩模的注意事项

目录问题： 解答： 一、高斯函数归一化：消除幅度偏差 1. 归一化的定义 2. 为何必须归一化？ 二、拉普拉斯系数和为零：抑制直流项干扰 1. 拉普拉斯算子的特性 2. 系数和不为零的后果三、直流项如何影响零交叉点&…...

编程日记 2025/7/4 18:15:49

OSPF基础实验-多区域

互联接口、IP地址如下图所示，所有设备均创建Loopback0，其IP地址为10.0.x.x/24，其中x为设备编号。 R1、R3的所有接口以及R2的GE0/0/4接口属于OSPF区域2，R2、R4的Loopback0接口及互联接口属于OSPF区域0，R4、R5的互联接口…...

编程日记 2025/7/4 17:57:57

ERP 与 WMS 对接深度解析：双视角下的业务与技术协同

在企业数字化运营的复杂体系中，ERP（企业资源规划）与 WMS（仓储管理系统）的有效对接，已成为优化供应链管理、提升运营效率的关键环节。本文将从 ERP 和 WMS 两个核心视角出发，深度剖析两者对接过程…...

编程日记 2025/7/1 15:43:12

基于 Node.js 的 HTML 转 PDF 服务

这是一个基于 Node.js 开发的 Web 服务，主要功能是将 HTML 内容转换为 PDF 文件。项目使用了 Express 作为 Web 框架，Puppeteer 作为 PDF 生成引擎，提供了简单易用的 API 接口。前端开发人员提供了一个简单而强大的 HTML 转 PDF 解决方案&…...

编程日记 2025/7/3 22:57:42

Java阻塞队列（BlockingQueue）的使用：ArrayBlockingQueue类、LinkedBlockingQueue类

1、阻塞队列的介绍 Java 中的阻塞队列（BlockingQueue）‌ 是多线程编程中用于协调生产者和消费者线程的重要工具，属于 java.util.concurrent 包。它的核心特点是：‌当队列为空时，消费者线程会被阻塞，直到队列中有新元素；当队列满时，生产者线程会被阻塞，直到队列有空闲…...

编程日记 2025/6/27 23:27:13

esp32cmini SK6812 2个方式

1 #include <SPI.h> // ESP32-C系列的SPI引脚 #define MOSI_PIN 7 // ESP32-C3/C6的SPI MOSI引脚 #define NUM_LEDS 30 // LED灯带实际LED数量 - 确保与实际数量匹配！ #define SPI_CLOCK 10000000 // SPI时钟频率 // 颜色结构体 st…...

编程日记 2025/7/4 16:25:01

2025年 PMP 6月 8月专题知识

2025年 PMP 6月 8月专题知识文章目录 2025年 PMP 6月 8月专题知识三点估算1. 概念:2. 原理: 决策树1. 概念:2. 步骤: 真题三点估算 1. 概念: 三点估算常用于估算活动持续时间（也可以用于估算成本）；源自计划评审技术（PERT&am…...

编程日记 2025/7/4 17:37:54

一文理解TCP与UDP

Socket套接字 Socket套接字，是由系统提供用于网络通信的技术，是基于TCP/IP协议的网络通信的基本操作单元。基于Socket套接字的网络程序开发就是网络编程。 Socket套接字主要针对传输层协议划分为如下三类： 流套接字：使用传输层…...

编程日记 2025/7/1 1:16:40

智能指针RAII

引入：智能指针的意义是什么？ RAll是一种利用对象生命周期来控制程序资源（如内存、文件句柄、网络连接、互斥量等等）的简单技术。在对象构造时获取资源，接着控制对资源的访问使之在对象的生命周期内始终保持有效&#…...

编程日记 2025/7/4 18:18:25

AI护航化工：《山西省危化品视频智能分析指南》下的视频分析重构安全体系

化工和危化品行业的AI智能视频分析应用：构建安全与效率新范式一、行业背景与挑战化工和危化品行业是国民经济的重要支柱，但生产过程涉及高温、高压、易燃易爆等高风险场景。传统安全监管依赖人工巡检和固定监控设备，存在效率低、盲区多、…...

编程日记 2025/7/4 16:36:38

GitHub SSH Key 配置详细教程（适合初学者，Windows版）-学习记录4

GitHub SSH Key 配置详细教程（适合初学者，Windows版） 本教程适用于在 Windows 系统下，将本地 Git 仓库通过 SSH 方式推送到 GitHub，适合没有配置过 SSH key 的初学者。 1. 检查是否已有 SSH key 打开 Git Bash 或 Po…...

编程日记 2025/6/29 2:20:59

初识Linux · NAT 内网穿透内网打洞代理

目录前言： 内网穿透和打洞 NAPT表内网穿透内网打洞正向/反向代理前言： 本文算是网络原理的最后一点补充，为什么说是补充呢，因为我们在前面第一次介绍NAT的时候详细介绍的是报文从子网到公网，却没有介绍报文…...

编程日记 2025/6/29 13:16:38

docker-compose使用详解

Docker-Compose 是 Docker 官方提供的容器编排工具，用于简化多容器应用的定义、部署和管理。其核心功能是通过 YAML 配置文件（docker-compose.yml）定义服务、网络和存储卷，并通过单一命令实现全生命周期的管理。以下从核心原理、安…...

编程日记 2025/7/4 17:57:57

使用计算机视觉实现目标分类和计数！！超详细入门教程

什么是物体计数和分类在当今自动化和技术进步的时代，计算机视觉作为一项关键工具脱颖而出，在物体计数和分类任务中提供了卓越的功能。无论是在制造、仓储、零售，还是在交通监控等日常应用中，计算机视觉系统都彻底改变了我们感知…...

编程日记 2025/7/3 23:00:46

并发编程中的对象组合的哲学

文章目录引言对象组合与安全委托实例封闭技术基于监视器模式的对象访问对象不可变性简化委托原子维度的访问现有容器的并发安全的封装哲学使用继承使用组合小结参考引言本文将介绍通过封装技术，保证开发者不对整个程序进行分析的情况下，就可以明确一个类是否是线程安全的，…...

编程日记 2025/7/4 17:22:51

03-Web后端基础(Maven基础)

1. 初始Maven 1.1 介绍 Maven 是一款用于管理和构建Java项目的工具，是Apache旗下的一个开源项目。 Apache 软件基金会，成立于1999年7月，是目前世界上最大的最受欢迎的开源软件基金会，也是一个专门为支持开源项目而生的非盈利性…...

编程日记 2025/6/29 2:21:46

禁忌搜索算法：从原理到实战的全解析

禁忌搜索算法：从原理到实战的全解析一、算法起源与核心思想禁忌搜索（Tabu Search, TS）由美国工程院院士Fred Glover于1986年正式提出，其灵感源于人类的记忆机制——通过记录近期的搜索历史（禁忌表）&…...

编程日记 2025/6/29 8:04:04

从加密到信任|密码重塑车路云一体化安全生态

目录一、密码技术的核心支撑二、典型应用案例三、未来发展方向总结车路云系统涉及海量实时数据交互，包括车辆位置、传感器信息、用户身份等敏感数据。其安全风险呈现三大特征： 开放环境威胁：V2X（车与万物互联&#xff0…...

编程日记 2025/6/29 10:47:32

【ffmpeg】SPS与PPS的概念

PPS（Picture Parameter Set）详解 PPS（图像参数集）是H.264/H.265视频编码标准中的关键数据结构，与SPS（序列参数集）共同组成视频的解码配置信息，直接影响视频的正确解码和播放。以下是…...

编程日记 2025/6/30 6:10:18

Java垃圾回收与JIT编译优化

1. Java中的垃圾回收垃圾回收是Java内存管理的核心，负责自动回收不再被应用程序引用的对象内存，从而防止内存泄漏并优化资源使用。以下详细介绍垃圾回收的机制、算法及优化实践。 1.1 垃圾回收的必要性垃圾回收解决了手动内存管理中的常见问题，如内存泄漏和悬空指针。它…...

编程日记 2025/6/29 11:07:00

mmaction2——tools文件夹下

build_rawframes.py 用法示例 python tools/data/build_rawframes.py data/videos data/frames --task rgb --level 2 --ext mp4 --use-opencv --num-worker 8总结： 只需要 RGB 帧，推荐 --use-opencv，简单高效，无需额外依赖。 …...

编程日记 2025/6/27 23:30:47

论文阅读：Next-Generation Database Interfaces:A Survey of LLM-based Text-to-SQL

地址：Next-Generation Database Interfaces: A Survey of LLM-based Text-to-SQL 摘要由于用户问题理解、数据库模式解析和 SQL 生成的复杂性，从用户自然语言问题生成准确 SQL（Text-to-SQL）仍是一项长期挑战。传统的 Text-to-SQ…...

编程日记 2025/7/2 5:05:29

Devicenet主转Profinet网关助力改造焊接机器人系统智能升级

某汽车零部件焊接车间原有6台焊接机器人（采用Devicenet协议）需与新增的西门子S7-1200 PLC（Profinet协议）组网。若更换所有机器人控制器或上位机系统，成本过高且停产周期长。《解决方案》工程师选择稳联技术转换网关…...

编程日记 2025/6/27 22:55:51

【HTML-5】HTML 实体：完整指南与最佳实践

1. 什么是 HTML 实体？ HTML 实体是一种在 HTML 文档中表示特殊字符的方法，这些字符如果直接使用可能会与 HTML 标记混淆，或者无法通过键盘直接输入。实体由 & 符号开始，以 ; 分号结束。 <p>这是一个小于符号的实体&am…...

编程日记 2025/6/30 0:02:29

MySQL 索引详解与原理分析

MySQL 索引详解与原理分析一、什么是索引？ 索引（Index）是数据库表中一列或多列的值进行排序的一种数据结构，可以加快数据的检索速度。索引类似于书本的目录，通过目录可以快速定位到想要的内容，而不用全书…...

编程日记 2025/7/2 8:41:18

游戏引擎学习第303天:尝试分开对Y轴和Z轴进行排序

成为我们自己的代码精灵α 所以现在应该可以正常使用了。不过，这两周我们没办法继续处理代码里的问题，而之前留在代码里的那个问题依然存在，没有人神奇地帮我们修复，这让人挺无奈的。其实我们都希望有个神奇的“代码仙子”&#…...

编程日记 2025/7/1 18:31:08

javaweb-html

1.交互流程： 浏览器向服务器发送http请求，服务器对浏览器进行回应，并发送字符串，浏览器能对这些字符串（html代码）进行解释； 三大web语言：（1）html&#xff1a…...

编程日记 2025/7/1 18:33:24

3.2.3

# 导入必要的库 import onnx import numpy as np from PIL import Image import onnxruntime as ort # 定义预处理函数，用于将图片转换为模型所需的输入格式 def preprocess(image_path): input_shape (1, 1, 64, 64) # 模型输入期望的形状，这里…...

编程日记 2025/7/3 22:42:44

Redis 8.0 GA，重回开源

在数字化浪潮的推动下，实时数据处理已成为现代应用的核心需求。作为全球广泛使用的 NoSQL 数据库，Redis 8.0 不仅通过 30 余项性能改进重新定义了实时数据处理的速度极限，更通过整合社区资源与开放授权模式，进一步巩固其在开源生态…...

编程日记 2025/7/3 18:03:54

心联网（社群经济）视角下开源AI智能名片、链动2+1模式与S2B2C商城小程序源码的协同创新研究

摘要：在心联网（社群经济）理论框架下，本文构建了开源AI智能名片、链动21模式与S2B2C商城小程序源码的技术协同体系，提出"情感连接-利益驱动-生态裂变"三维创新模型。通过实证分析与案例研究，验证该…...

编程日记 2025/7/3 9:26:44

【图像大模型】Hunyuan-DiT：腾讯多模态扩散Transformer的架构创新与工程实践

Hunyuan-DiT：腾讯多模态扩散Transformer的架构创新与工程实践一、架构设计与技术创新1.1 核心架构解析1.2 关键技术突破1.2.1 多粒度训练策略1.2.2 动态路由MoE 二、系统架构解析2.1 完整生成流程2.2 性能对比三、实战部署指南3.1 环境配置3.2 基础推理代码3.3 高…...

编程日记 2025/6/27 23:30:00

TASK04【Datawhale 组队学习】构建RAG应用

目录将LLM接入LangChain构建检索问答链运行成功图遇到的问题 langchain可以便捷地调用大模型，并将其结合在以langchain为基础框架搭建的个人应用中。将LLM接入LangChain from langchain_openai import ChatOpenAI实例化一个 ChatOpenAI 类,实例化时传入超参数来…...

编程日记 2025/6/27 23:33:41

YOLOv11旋转目标检测Hrsc2016

from ultralytics import YOLOmodel YOLO(/kaggle/input/model-v11-obb/yolo11n-obb.pt) model.train(data/kaggle/input/hrscobb4/HRSC-YOLO/data.yaml, epochs30) 1使用的训练平台为Kaggle 数据集：HRSC的三种形式一级分类：船有水平框版本&…...

编程日记 2025/7/1 1:17:20

安装配置java环境手动安装下载openJDK：openJDK 设置替代项 sudo update-alternatives --install /usr/bin/java java /opt/jdk-21.0.2/bin/java 1 sudo update-alternatives --install /usr/bin/javac javac /opt/jdk-21.0.2/bin/javac 1 sudo update-alternat…...

编程日记 2025/7/1 15:59:09

野火鲁班猫(arrch64架构debian)从零实现用MobileFaceNet算法进行实时人脸识别（四）安装RKNN Toolkit Lite2

RKNN Toolkit Lite2 是瑞芯微专为RK系列芯片开发的NPU加速推理API。若不使用该工具，计算任务将仅依赖CPU处理，无法充分发挥芯片高达6TOPS的NPU算力优势。按照官方文档先拉一下官方代码库，然后通过whl文件安装，因为我是python3.1…...

编程日记 2025/7/1 4:19:55

ElasticSearch导读

ElasticSearch 简介：ElasticSearch简称ES是一个开源的分布式搜素和数据分析引擎。是使用Java开发并且是当前最流行的开源的企业级搜索引擎，能够达到近实时搜索，它专门设计用于处理大规模的文本数据和实现高性能的全文搜索。它基于 Apache Luc…...

编程日记 2025/6/27 23:14:19

【STM32】自定义打印函数

STM32 学习笔记：理解 my_printf 与 va_start 在嵌入式开发中，我们常常需要实现类似标准 C 中 printf 的调试输出功能。为了支持“任意数量参数”的传递，C 语言提供了对可变参数（variable arguments） 的支持。其中&am…...

编程日记 2025/7/1 4:43:40

基于 STM32 的 PC ARGB 风扇控制器设计与实现

一、项目背景最近购入的 X99 系列主板，没有风扇的 ARGB 彩灯接口，并且在 Ubuntu 系统上 4pin 的风扇接口调速也是非常的难用，sensor 扫描不到传感器，于是决定手搓一个风扇控制器，来实现转速自定义和彩灯控制。我控制…...

编程日记 2025/7/2 22:41:09

【软件设计师】计算机网络考点整理

以下是软件设计师考试中计算机网络的核心考点总结，帮助您高效备考： 一、网络体系结构与协议 OSI七层模型 & TCP/IP四层模型各层功能（物理层-数据链路层-网络层-传输层-会话层-表示层-应用层）对应协…...

编程日记 2025/6/27 23:39:09

在 Qt 中实现动态切换主题（明亮和暗黑）

目录步骤 1：准备主题文件步骤 2：将 QSS 文件加入资源系统步骤 3：创建主题管理类步骤 4：在应用程序中切换主题步骤 5：处理自定义控件和动态资源步骤 6：保存用户主题偏好步骤 7：处理图片资源切换…...

编程日记 2025/6/27 22:56:09

JavaEE 初阶文件操作与 IO 详解

一、文件操作基础：File 类作用：操作文件或目录（创建、删除、获取信息）。核心方法： exists()：文件是否存在createNewFile()：创建新文件mkdir()：创建目录delete()：删除…...

编程日记 2025/7/1 5:07:45

基于Qt的app开发第十天

写在前面笔者昨天刚刚收到课设的截止时间要求，距离写这篇博客的时间还有一个月，我从申请自命题课设到今天已经27天了，先用两周时间学Qt，然后就开始做这个项目，现在已经快把基础功能全部实现了。目前的打算是完成基础…...

编程日记 2025/7/4 15:14:31

QT中信号和事件的区别

好的，简单来说，Qt 的信号（Signal）和事件（Event）虽然都用于组件间通信和交互，但它们的机制和用途是不同的： 1. 信号（Signal） 概念：信号是对象发出的…...

编程日记 2025/7/2 4:57:46

AUTOSAR图解==＞AUTOSAR_SRS_PWMDriver

AUTOSAR PWM驱动模块详解基于AUTOSAR 4.4.0 SRS 规范文档目录 1. PWM驱动概述2. PWM驱动架构3. PWM驱动配置4. PWM驱动API接口5. PWM驱动状态管理6. PWM驱动典型应用场景7. 总结1. PWM驱动概述 AUTOSAR PWM驱动是AUTOSAR基础软件中的一个重要组件，属于微控制器抽象层(MCAL)…...

编程日记 2025/7/2 7:33:12

SQL数据处理流程

一、数据处理 1、数据清洗对空值处理：删除/填充为0 -- 用 0 填充 NULL SELECT COALESCE(sales, 0) AS sales FROM orders;-- 删除含 NULL 的记录 DELETE FROM users WHERE email IS NULL; COALESCE(bonus, 0) 相当于IF(bonus IS NULL, 0, bonus)，当…...

编程日记 2025/7/3 7:32:24

Mysql差异备份与恢复

1.练习差异备份差异备份：备份完全备份后，新产生的数据。在192.168.88.50主机完成差异备份步骤一：练习差异备份//周一完全备份 mysql> select * from test.one; --------------------- | name | age | sex | ------------------…...

编程日记 2025/7/1 1:31:32

目标检测 Lite-DETR（2023）详细解读

文章目录迭代高级特征跨尺度融合高效的低层次特征跨尺度融合KDA：Key-aware Deformable Attention 论文翻译： CVPR 2023 | Lite DETR：计算量减少60%！高效交错多尺度编码器-CSDN博客 DINO团队的 （Lightweight Transfo…...

编程日记 2025/6/27 22:55:42

【Java学习方法】类变量

类变量引出关键字：static 又名：静态变量，静态字段，类字段（字段又名属性，成员方法），类属性是什么？ 供该（同一个类）的所有对象共享的变量 &am…...

编程日记 2025/6/27 22:55:41

智能手表为什么需要做 EN 18031 认证？

EN 18031 是欧盟针对电磁兼容性（EMC）中人体暴露于电磁场的安全要求制定的标准，全称为《Electromagnetic compatibility (EMC) - Standards for protective measures against electromagnetic fields with regard to human exposure》&#x…...

编程日记 2025/7/3 5:02:39

牛客网 NC16407 题解：托米航空公司的座位安排问题

题目分析

解题思路

代码详解

算法分析

优化建议

注意事项

总结

相关文章：