CSDN每日一练:小豚鼠搬家
题目名称:小豚鼠搬家
时间限制:1000ms内存限制:256M
题目描述
小豚鼠排排坐。 小艺酱买了一排排格子的小房子n*m,她想让k只小豚鼠每只小豚鼠都有自己的房子。 但是为了不浪费空间,她想要小房子的最外圈尽量每行每列都有一只小豚鼠居住。 小艺酱想知道自己有多少种方案安排小豚鼠。
输入描述:
输入整数n,m,k。(1<=n,m<=20,0<=k<=n*m)
输出描述:
输出方案数,答案对1e9+7取模。
示例
示例1
输入
3 3 2
输出
2
提示
无
用例里有两个比较特殊,一个是没有豚鼠的用例,[3, 4, 0],这个如果用递归的话,需要避免这个用例,豚鼠数字小于2,就返回0,笼子就1个格,返回1
另一个就是真正的算法考验的用例了 [5, 5, 12],返回结果是 4704606…我在本地跑了一下,最土的递归用了一分半钟左右才得出这个结果
先放第一版的
def s(row,col,num,start,pos):#result = []result = 0if num == 1:for i in range(start,row*col):t = pos + [i]if len([_ for _ in t if _ // col == 0])>0 and len([_ for _ in t if _ % col == 0])>0 and len([_ for _ in t if _ // col == row-1])>0 and len([_ for _ in t if _ % col == col - 1])>0:#result.append(pos + [i])result += 1return resultelse:for i in range(start,row*col-num+1):result += s(row,col,num-1,i+1,pos+[i])return resultn,m,k = [4,4,14]
result = s(n,m,k,0,[])
于是就想起来,好像看到过某个文章里讲解了这个题目怎么算,完全不用递归组合什么的,就是数学公式,最后找了半天也没找到之前看到的文章,但还是搜索出了一个类似的,讲解的也比较清楚的文章
https://www.cnblogs.com/pengwill/p/7367030.html
文章的意思就是用最大组合减去不合要求的组合,再加上遗漏的组合,再减去遗漏组合中不合要求的组合。。。嗯,用循环完成的,叫什么容斥原理。。。原谅老顾没上过学。。。。

具体为什么程序这么写倒是没搞明白,尤其是中间用到位运算,怎么就和这总计的16项(最大集合,及15个容斥原理对应内容)

最后还是列了个输出信息才弄明白,哪些是加的,哪些是减的,分别加了多少减了多少。。。。嗯,只需要一个阶乘函数,一个组合函数就够了
n,m,k = [5,5,12]total = 0for i in range(16):idx = 0row = ncol = mif i & 1: # 对应集合 A,最上边一行无小鼠col -= 1idx += 1if i & 2: # 对应集合 B,最下边一行无小鼠col -= 1idx += 1if i & 4: # 对应集合 C,最左边一列无小鼠row -= 1idx += 1if i & 8: # 对应集合 D,最右边一列无小鼠row -= 1idx += 1print('i:',i,i&1,i&2,i&4,i&8,'idx:',idx,idx & 1,'row:{},col:{}'.format(row,col))if idx & 1:total -= int(X(row*col,k))else:total += int(X(row*col,k))print(total)
准备自己时常复习一下,争取把这个公式弄明白,加油,老顾
弄这么个文章,主要是搜不到“小豚鼠搬家”这个题目的题解,百度出来的,都没有具体算法,好伤心
相关文章:
CSDN每日一练:小豚鼠搬家
题目名称:小豚鼠搬家 时间限制:1000ms内存限制:256M 题目描述 小豚鼠排排坐。 小艺酱买了一排排格子的小房子n*m,她想让k只小豚鼠每只小豚鼠都有自己的房子。 但是为了不浪费空间,她想要小房子的最外圈尽量每行每列都有…...
Dockerfile命令及实践构建一个网站
dockerfile用于构建docker镜像的,部署一个用于运行你所需的容器环境。相当一个脚本,通过dockerfile自己的指令,来构建软件依赖、文件依赖、存储、定制docker镜像的方式有两种:手动修改容器内容,导出新的镜像基于Docker…...
[VMware]Ubuntu18.04 网络图标消失
Ubuntu 18.04 网络图标消失运行环境问题解决NO.1 执行 sudo systemctl stop network-managerNO.2 执行 sudo rm /var/lib/NetworkManager/NetworkManager.stateNO.3 执行 sudo systemctl start network-managerNO.4 vi /etc/NetworkManager/NetworkManager.confNO.5 执行 sudo …...
国产C2000,P2P替代TMS320F280049C,独立双核32位CPU,主频高达400MHz
一、特性参数 1、独立双核,32位CPU,单核主频400MHz 2、IEEE 754 单精度浮点单元 (FPU) 3、三角函数单元 (TMU) 4、1MB 的 FLASH (ECC保护) 5、1MB 的 SRAM (ECC保护&…...
二十五、Gtk4-多线程分析
1 回顾 1.1 Gnome相关 首先回顾一下GLib,GObject,GIO,Gtk的不同,因为下面会涉及到这些概念里面的函数。 所有这些都是由Gnome项目开发的库,一般都用于Gnome环境相关的应用程序。 Gtk:GUI界面库。GLib&a…...
JVM基础学习
JVM分为两个子系统,两个组件一个子系统是Class loader类装载系统,另一个子系统是Execution Engine执行引擎一个组件是Runtime data area 运行时数据区,Native Interface 本地接口Class loader:根据给定的全限定类名来装载class文件到运行时数…...
ASML逆袭史:人、资金、技术,缺一不可
前言 近年来,由于众所周知的原因,荷兰ASML(阿斯麦)公司的先进半导体制造设备——光刻机,进入普通大众视野,成为人们茶余饭后谈论的焦点话题之一。 1月底,“美日荷三方谈判达成协议,可…...
MongoDB 覆盖索引查询
MongoDB 覆盖索引查询 官方的MongoDB的文档中对覆盖查询做了说明: 所有的查询字段是索引的一部分所有的查询返回字段在同一个索引中 由于所有出现在查询中的字段是索引的一部分, MongoDB 无需在整个数据文档中检索匹配查询条件和返回使用相同索引的查询…...
Flink Checkpoint 中的Aligned Checkpoint 和 Unaligned Checkpoint
文章目录知识点反压CheckpointBarrierAligned CheckpointUnaligned Checkpoint核心思想实现原理UC同步阶段UC异步阶段知识点 反压 反压是流式系统中关于处理能力的动态反馈机制,并且是从下游到上游的反馈,一般是在实时数据处理的过程中,上游…...
C++快速入门
本章内容我将结合C语言一起,初步学习了解c,与大家一起快速入门这门语言。当然鉴于c本身属于一门中级语言,大家对编程有一定了解之后来学习这门知识会更加得心应手。简介C 被认为是一种中级语言,它综合了高级语言和低级语言的特点。…...
ubuntu18.04 network有线网络图标缺失解决记录
先按照博客1安装驱动 博客1链接:Ubuntu安装 Realtek R8125 驱动_Lwang2018的博客-CSDN博客_瑞昱8125 for ubunt 安装完成后,遇到问题:ifconfig -a显示的有线网接口(名字以en开头)没有ip地址…...
java对象克隆和面向对象的设计原则
java进阶注解内置注解元注解自定义注解对象克隆浅克隆深克隆java设计模式建模语言类之间的关系依赖关系关联关系单向关联双向关联自关联聚合关系组合关系继承关系实现关系面向对象设计原则单一职责开闭原则里氏替换原则依赖倒置接口隔离迪米特原则组合/聚合复用原则注解 java注…...
传透式血氧仪设计方案
该方案一种检测方式是选择使用光敏二极管接收光信号,采用传统穿透式夹指测量;另一种是使用光谱传感器接收光信号,采用反射式测量。该传感器可将光信号直接转换成数据信息给主控端进行处理,从而节省了用户将光信号转换成模拟信号&a…...
让逆向工程师们头疼的代码混淆,就像永远也走不出的“浪浪山”
目录 代码混淆究竟是什么? 如何做代码混淆? 代码混淆不等于加密 App 加固非一时之功 “我想离开浪浪山。” 在数次尝试破解某个App 时,某个逆向工程师无奈感慨道。 逆向工程师顾名思义就是把一个个完整的软件逆推,还原成一段段…...
【拓展】基于机器学习的心脏病预测方法(14)——心脏病数据集补充
目录 前言1、数据集11.1 数据集介绍1.2 数据集属性2、数据集22.1 数据集介绍2.2 数据集属性3、数据集33.1 数据集介绍3.2 数据集属性4、下载地址前言 在实际研究过程中,前文所述数据集由于尺寸过小(仅有303份数据和13个属性信息)或数据集单一(仅有一个数据集,不具备普适性…...
深度解读Webpack中的loader原理
一、前言 webpack 是一个现代 JavaScript 应用的静态模块打包器。那么 webpack 是怎样实现不同种类资源模块加载的呢? 没错就是通过 loader。loader 用于对模块的源代码进行转换。loader 可以使你在 import 或加载模块时预处理文件。 我们带着下面几个问题&#…...
2023年全国最新二级建造师精选真题及答案
百分百题库提供二级建造师考试试题、二建考试预测题、二级建造师考试真题、二建证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 一、单选题 1.关于法人在建设工程中的地位的说法,正确的是(࿰…...
为什么现代企业发展离不开CRM系统的助力
如今的CRM系统对于任何企业来说都重要,因为它能帮助企业收获新客户,保留现有客户,并且将不同部门的信息全部汇集,实时提供关于每位客户整体全面的看法。因此,销售、市场营销和客户支持等领域的客户直接服务员工能够做出…...
vb.net计算之.net core基础(1)-获取农历和天气
目录 .net core 简介创建hello,world应用程序获取天气和农历.net core 简介 .NET Core是适用于 Windows、Linux 和 macOS 的免费、开源托管的计算机软件框架。 它是微软开发的第一个官方版本,具有跨平台能力的应用程序开发框架 (Application Framework),未来也将会支持 Free…...
设计模式之代理模式详解和应用
目录1 代理模式定义2 代理模式的应用场景3 代理模式的通用写法4 从静态代理到动态代理5 静态模式在业务中的应用6 动态代理在业务中的应用7 手写JDK动态代理实现原理7.1 JDK动态代理的实现原理7.2 CGLib动态代理容易踩的坑8 CGLib代理调用API及原理分析9 CGLib和JDK动态代理对比…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
