洛谷 1025.数的划分
这道题用的知识点是DFS+剪枝。难的不在DFS上,而是在剪枝上如何选择。
思路:这道题我们看到是按照字典序排的,但是,我们注意到,看似是全排列的递归,实则不是。
我们前面也了解过,全排列的数字大小是没有规则的,当然指数型也不可能,这并不涉及到选与不选的问题。而且,我们看到,这些数字有点像升序排列的,所以可能会是组合型递归。但是呢,我们又发现,它们的数字并不是严格单调的,而是有相同的数字在里面排序。这怎么办呢?
改进方法已经在代码里了,就是在进行下一次dfs的时候我们只需要写上i就行,而不是i+1,如果是i+1就会严格单调了。
只是这样写起来,会有数据点TLE。这是为什么呢?因为有些地方是需要剪枝的。那么这里我们怎么剪枝呢?如果你想说在求出来的和不是n的时候剪枝,那也是在全部数字枚举出来的时候才会判断的,仅仅是这样并不能完全剪枝。那该怎么办呢?这里,我们直接在循环里剪枝,也就是在枚举的过程中进行剪枝。怎么剪枝呢?举个例子:
当我们n=7,k=4时,这个时候假如我们已经列举到1,3了,现在正在第三个位置的dfs当中,这个时候按照我们的写法下一个数字肯定是3,最后一个数字也是3,这是对于自己编写的程序的理解。
我们看,如果这几个数字加起来是不是已经超过7了?也就是说,第四个位置我们根本不需要考虑了,前面已经=7了,后面再加就不行了,这里我们直接让循环不去dfs了,而是进行下一次循环。这就省了一次dfs函数的调用!那么,怎么实现这种想法呢?
我们在循环中改进循环条件就行,这和上几次的剪枝是不一样的,这里的剪枝涉及到的是对于在枚举过程中的剪枝,而不是对于全部枚举完之后的剪枝,这里是不同点。在上面的例子中,我们看到,其实知道了第三个数字我们也就知道了第四个数字了。所以,我们只需要循环到第二个位置后,判断后面两个位置的和与前面我们已经计算了的sum相加是不是<=n就行了,这就是优化的地方。
注意:这里的dfs有三个变量,第一个是位置,第二个是从哪个数开始枚举,第三个则是累加的数用来记录的。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 100010
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int arr[MAX];
LL n, m, counts, num;
void dfs(int u,int st,int sum) {if (u > m) {if (sum<n || sum>n)return;else {counts++;}return;}for (int i = st; sum+(m-u+1)*i <= n; i++) {arr[u] = i;dfs(u + 1,i,sum+i);arr[u] = 0;}}
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n >> m;dfs(1,1,0);cout << counts << endl;return 0;
}
相关文章:
洛谷 1025.数的划分
这道题用的知识点是DFS剪枝。难的不在DFS上,而是在剪枝上如何选择。 思路:这道题我们看到是按照字典序排的,但是,我们注意到,看似是全排列的递归,实则不是。 我们前面也了解过,全排列的数字大…...
MySQL实战:SQL优化及问题排查
有更合适的索引不走,怎么办? MySQL在选取索引时,会参考索引的基数,基数是MySQL估算的,反映这个字段有多少种取值,估算的策略为选取几个页算出取值的平均值,再乘以页数,即为基数 查…...
加密与安全_使用Java代码操作RSA算法生成的密钥对
文章目录 Pre概述什么是非对称加密算法?如何工作?示例:RSA算法特点和优势ECC:另一种非对称加密算法 Code生成公钥和私钥私钥加密私钥加密私钥解密 ( 行不通 )私钥加密公钥解密公钥加密和公钥解密 (行不通)保…...
Spring Boot中实现图片上传功能的两种策略
🌟 前言 欢迎来到我的技术小宇宙!🌌 这里不仅是我记录技术点滴的后花园,也是我分享学习心得和项目经验的乐园。📚 无论你是技术小白还是资深大牛,这里总有一些内容能触动你的好奇心。🔍 &#x…...
07.axios封装实例
一.简易axios封装-获取省份列表 1. 需求:基于 Promise 和 XHR 封装 myAxios 函数,获取省份列表展示到页面 2. 核心语法: function myAxios(config) {return new Promise((resolve, reject) > {// XHR 请求// 调用成功/失败的处理程序}) …...
【Linux】第四十一站:线程控制
一、Linux线程VS进程 1.进程和线程 进程是资源分配的基本单位线程是调度的基本单位线程共享进程数据,但也拥有自己的一部分数据:线程ID一组寄存器(上下文)栈errno信号屏蔽字调度优先级 2.进程的多个线程共享 同一地址空间,因此Text Segment、…...
ChatGPT提示词工程:prompt和chatbot
ChatGPT Prompt Engineering for Developers 本文是 https://www.deeplearning.ai/short-courses/chatgpt-prompt-engineering-for-developers/ 这门课程的学习笔记。 ChatGPT提示词工程:prompt和chatbot 文章目录 ChatGPT Prompt Engineering for DevelopersWhat …...
java算法
常见的七种查找算法: 数据结构是数据存储的方式,算法是数据计算的方式。所以在开发中,算法和数据结构息息相关。 1. 基本查找 也叫做顺序查找 说明:顺序查找适合于存储结构为数组或者链表。 基本思想:顺序查找也称…...
铭文资产是比特币生态破局者 or 短暂热点?
比特币作为加密货币的鼻祖,一直以来都扮演着数字资产市场的引领者角色。最近几年,随着 BRC20 项目的兴起,我们看到了更多与比特币相互关联的创新。在比特币生态中,BRC20 项目不仅仅是数字资产的代表,更是一种对于区块链…...
Java基础 - 8 - 算法、正则表达式、异常
一. 算法 什么是算法? 解决某个实际问题的过程和方法 学习算法的技巧? 先搞清楚算法的流程,再直接去推敲如何写算法 1.1 排序算法 1.1.1 冒泡排序 每次从数组中找出最大值放在数组的后面去 public class demo {public static void main(S…...
gRPC-第二代rpc服务
在如今云原生技术的大环境下,rpc服务作为最重要的互联网技术,蓬勃发展,诞生了许多知名基于rpc协议的框架,其中就有本文的主角gRPC技术。 一款高性能、开源的通用rpc框架 作者作为一名在JD实习的Cpper,经过一段时间的学…...
Node.js是什么?
概念:Node.js1运行在服务器端的js,用来编写服务器 特点:单线程、异步、非阻塞、统一API 是一个构建在V8引擎之上的js运行环境,它使得js可以运行在浏览器以外的地方,相对于大部分的服务器端语言来说,Node.J…...
java SSM厂房管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计
一、源码特点 java SSM厂房管理系统是一套完善的web设计系统(系统采用SSM框架进行设计开发,springspringMVCmybatis),对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S…...
uniapp实现---类似购物车全选
目录 一、实现思路 二、实现步骤 ①view部分展示 ②JavaScript 内容 ③css中样式展示 三、效果展示 四、小结 注意事项 一、实现思路 点击商家复选框,可选中当前商家下的所有商品。点击全选,选中全部商家的商品 添加单个多选框,在将多选…...
Java:List列表去重有序和无序
目录 待去重列表HashSet去重(不保证顺序)TreeSet去重(不保证顺序)LinkedHashSet去重(保证顺序)遍历List去重(保证顺序)Java8中Stream流处理(保证顺序)参考文章 待去重列表 // 列表 …...
Python绘图-12地理数据可视化
Matplotlib 自 带 4 类别 地理投影: Aitoff, Hammer, Mollweide 及 Lambert 投影,可以 结 合以下四 张 不同 的 图 了解四 种 不同投影 区别 。 12.1Aitoff投影 12.1.1图像呈现 12.1.2绘图代码 import numpy as np # 导入numpy库,用于…...
NineData与OceanBase完成产品兼容认证,共筑企业级数据库新生态
近日,云原生智能数据管理平台 NineData 和北京奥星贝斯科技有限公司的 OceanBase 数据库完成产品兼容互认证。经过严格的联合测试,双方软件完全相互兼容、功能完善、整体运行稳定且性能表现优异。 此次 NineData 与 OceanBase 完成产品兼容认证…...
旅游专业VR虚拟仿真情景教学实训
一、生动的情景模拟 VR技术能够创建出高度逼真的虚拟环境,使学生能够身临其境地体验旅游场景。无论是古色古香的古代建筑,还是充满异国情调的热带雨林,亦或是繁华的都市风光,VR都能一一呈现。这种沉浸式的体验,使得学…...
解决方案TypeError: string indices must be integers
文章目录 一、现象:二、解决方案 一、现象: PyTorch深度学习框架,运行bert-mini,本地环境是torch1.4-gpu,发现报错显示:TypeError: string indices must be integers 后面报字符问题,百度过找…...
【论文阅读】Segment Anything论文梳理
Abstract 我们介绍了Segment Anything(SA)项目:新的图像分割任务、模型和数据集。高效的数据循环采集,使我们建立了迄今为止最大的分割数据集,在1100万张图像中,共超过10亿个掩码。 该模型被设计和训练为可…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
