洛谷P8599 [蓝桥杯 2013 省 B] 带分数

[蓝桥杯 2013 省 B] 带分数

题目描述

100 100 100 可以表示为带分数的形式: 100 = 3 + 69258 714 100 = 3 + \frac{69258}{714} 100=3+71469258

还可以表示为: 100 = 82 + 3546 197 100 = 82 + \frac{3546}{197} 100=82+1973546

注意特征:带分数中,数字 1 1 1 ~ 9 9 9 分别出现且只出现一次(不包含 0 0 0)。

类似这样的带分数, 100 100 100 11 11 11 种表示法。

输入格式

从标准输入读入一个正整数 N ( N < 1 0 6 ) N(N<10^6) N(N<106)

输出格式

程序输出数字 N N N 用数码 1 1 1 ~ 9 9 9 不重复不遗漏地组成带分数表示的全部种数。

注意:不要求输出每个表示,只统计有多少表示法!

样例 #1

样例输入 #1

100

样例输出 #1

11

样例 #2

样例输入 #2

105

样例输出 #2

6

提示

原题时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛

暴力做法

要保证1~9这每个数都要出现,且仅出现一次,可以联想到AcWing 842. 排列数字该暴力解法,就是在排列数字的基础上,将9个数的自由排列先求出来,然后根据式子
n = a + b c n = a + \frac{b}{c} n=a+cb
的基础上,枚举每一个a, b的位数,双重循环,c的位数可以由9 - a - b求出,通过get_value函数将每个求出来,再验证式子是否正确,由于c++中的除法是取整后的结果,所以要转换成乘法在进行验证。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;const int N = 15;int path[N];//九个数的自由排列结果
bool st[N];
int n, res = 0;int get_value(int k, int c){// k为起始下标,c为总位数int res = 0;for (int i = 0; i < c; i ++){res += path[k + i] * pow(10, c - i - 1);}return res;
}void dfs(int k){if (k == 9){for (int i = 1; i < 9; i ++){int a = get_value(0, i);if (a > n) break;//a如果大于n就一定等式不成立,提前剪枝for (int j = 1; j < 9 - i; j ++){int k = 9 - i - j;if (k <= 0) break;else{int b = get_value(i, j);int c = get_value(i + j, k);if (n * c == a * c + b ){//这里必须要变形成乘法形式,因为除法是取整除法会导致答案过多res ++;}}}}return;}for (int i = 1; i <= 9; i ++){if (!st[i]){st[i] = true;path[k] = i;dfs(k + 1);st[i] = false;}}
}int main(){scanf("%d", &n);dfs(0);printf("%d", res);return 0;
}

在这里插入图片描述
要开 O 2 O_2 O2优化,不然超过1s了TLE

嵌套dfs

首先通过传入参数的形式将a, c的值求出来,减少了多次求的运算过程,通过先dfs_a, 中嵌套dfs_c,枚举所有结果,用check进行剪枝,来加快处理速度。
b = n( 1 0 6 10^6 106) * c(10^6) 爆int( 1 0 10 10^{10} 1010)了,所以要用 l o n g l o n g long long longlong来存b

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 20;
typedef long long LL;bool st[N], backup[N];
int n, res = 0;bool check(int a, int c){//判断当前a, c是否满足题目的要求LL b = n * (LL)c - a * c;if (!a || !b || !c) return false; //当a, b, c为零时不满足,边界特判memcpy(backup, st, sizeof st);//由于b中的数字可能重复,所以需要改变st中的值判断重复,但这影响了st,所以要先复制while (b){//将b中的每个数字都抠出来int x = b % 10;b /= 10;if (!x || backup[x]) return false; backup[x] = true;}for (int i = 1; i <= 9; i ++){if (!backup[i]) return false;}return true;
}void dfs_c(int k, int a, int c){if(k == n) return;if (check(a, c)) res ++;//当前c不满足,也要接着后面代码找下一个c,不能returnfor (int i = 1; i <= 9; i ++){if (!st[i]){st[i] = true;dfs_c(k + 1, a, c * 10 + i);st[i] = false;}}
}void dfs_a(int k, int a){if (a > n) return;dfs_c(k, a, 0);for (int i = 1; i <= 9; i ++){if (!st[i]){st[i] = true;dfs_a(k + 1, a * 10 + i);st[i] = false;}}
}int main(){scanf("%d", &n);dfs_a(0, 0);//枚举到第几位,a的值为多少printf("%d\n", res);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/250044.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Prompt Learning 的几个重点paper

Prefix Tuning: Prefix-Tuning: Optimizing Continuous Prompts for Generation 在输入token之前构造一段任务相关的virtual tokens作为Prefix&#xff0c;然后训练的时候只更新Prefix部分的参数&#xff0c;PLM中的其他参数固定。针对自回归架构模型&#xff1a;在句子前面添…

Django模型(八)

一、修改数据 先获取对象,通过对象属性更新数据,再保存 (更新单一数据)通过QuerySet的update函数更新数据 (更新多条数据) #单条记录修改 save c = Cook.objects.get(pk=1) c.name = 安妮 c.save()# 更新多个值 update Cook.objects.filter(sect=粤菜).update(level=5)1.1、…

SD-WAN如何解决企业网络面临的问题?

企业网络在不断增长和发展的同时&#xff0c;所面临的问题也越来越多。SD-WAN作为一项崭新的网络技术&#xff0c;正迅速成为企业的首选。究竟SD-WAN在解决企业网络问题上有何独特之处呢&#xff1f; 优化网络性能与带宽利用率 传统广域网常常面临多地点数据传输时的高延迟、低…

【深蓝学院】移动机器人运动规划--第3章 基于采样的路径规划--作业

0. Assignment T1. MATLAB实现RRT 1.1 GPT-4任务分析 RRT伪代码&#xff1a; 任务1即使用matlab实现RRT&#xff0c;结合作业所给框架&#xff0c;简单梳理&#xff0c;可结合1.2代码理解&#xff1a; 设置start&#xff0c;goal&#xff0c;near to goal threshold Thr&am…

MySql主从同步,同步SQL_ERROR 1032解决办法

1.登录从库 mysql -u root -p 2.输入命令查看状态 SHOW SLAVE STATUS\G; 3.找到对应的错误数据位置 Slave_IO_Running: YesSlave_SQL_Running: NoReplicate_Do_DB: app_push_centerReplicate_Ignore_DB: Replicate_Do_Table: Replicate_Ignore_Table: Replicate_Wild_Do_Tabl…

github连不上

github连不上 错误提示解决方案steam 采用Hosts加速 错误提示 fatal: unable to access ‘https://github.com/Ada-design/qianduan.git/’: Failed to connect to github.com port 443 after 21073 ms: Couldn’t connect to server 解决方案 下载steam https://steampp.ne…

Flutter的安装与环境配置

一、下载安装Futter&#xff1a; 1、Flutter中文文档&#xff1a; 安装和环境配置 - Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 2、下载 Futter SDK&#xff1a; Flutter中文文档 里面有&#xff0c;下载完成之后找个文件夹解压出来&#xff0c;最好不要将 Flu…

专业数据治理:数据中台系统塑造企业未来的数字化运营管理新秩序

随着信息化进程的快速推进&#xff0c;数据已然成为企业最为宝贵的资产。对于众多企业而言&#xff0c;如何有效整合、治理以及充分利用这些数据&#xff0c;使之成为推动业务发展的引擎&#xff0c;成为当前难题。数据中台应运而生&#xff0c;它被认为是企业数字化转型的至关…

深度解读NVMe计算存储协议-3

在NVMe计算存储架构中&#xff0c;Copy命令用于在不同类型的命名空间之间进行数据复制&#xff1a; Memory Copy命令&#xff1a;定义于SLM&#xff08;Subsystem Local Memory&#xff09;命令集&#xff0c;主要用于从非易失性存储命名空间&#xff08;NVM namespaces&#x…

“IT行业的黄金证书:你必须了解的顶级认证“

文章目录 每日一句正能量前言一、网络方向&#xff1a;思科认证/软考二、华为认证三、系统方向&#xff1a;红帽认证四、数据库方向&#xff1a;Oracle认证五、信息安全方向&#xff1a;CISP/CISSP认证六、管理方向&#xff1a;PMP认证IT行业证书的价值和作用后记 每日一句正能…

XML传参方式

export function groupLoginAPI(xmlData) {return http.post(/tis/group/1.0/login, xmlData, {headers: {Content-Type: application/xml,X-Requested-With: AAServer/4.0,}}) }import {groupLoginAPI} from "../api/user"; function (e) { //xml格式传参let groupX…

前端JavaScript篇之let、const、var的区别

目录 let、const、var的区别 let、const、var的区别 let、const和var是JavaScript中用于声明变量的关键字&#xff0c;它们之间有一些区别。 首先&#xff0c;var是在ES5中引入的关键字&#xff0c;而let和const是在ES6中引入的。在ES6之前&#xff0c;我们只能使用var来声明…

双非本科准备秋招(13.1)—— 力扣 栈、队列与堆

1、103. 二叉树的锯齿形层序遍历 昨天做的二叉树的层序遍历&#xff0c;把代码直接拿过来。 这个题要求的是一个Z型遍历&#xff0c;如下图。 用一个变量f记录正反顺序&#xff0c;然后使用LinkedList记录答案&#xff0c;下图可以看到LinkedList继承了Deque&#xff0c;所以…

【开源】JAVA+Vue.js实现电子元器件管理系统

目录 一、摘要1.1 项目简介1.2 项目录屏 二、研究内容三、界面展示3.1 登录&注册&主页3.2 元器件单位模块3.3 元器件仓库模块3.4 元器件供应商模块3.5 元器件品类模块3.6 元器件明细模块3.7 元器件类型模块3.8 元器件采购模块3.9 元器件领用模块3.10 系统基础模块 四、…

C++学习Day01之namespace命名空间

目录 一、程序及输出1.1 命名空间用途&#xff1a; 解决名称冲突1.2 命名空间内容1.3 命名空间必须要声明在全局作用域下1.4 命名空间可以嵌套命名空间1.5 命名空间开放&#xff0c;可以随时给命名空间添加新的成员1.6 命名空间可以是匿名的1.7 命名空间可以起别名 二、分析与总…

02.PostgreSQL运算符

1. 算术运算符 算术运算符 描述 示例 + 加法运算符 SELECT A+B - 减法运算符 SELECT A-B * 乘法运算符 SELECT A*B / 除法运算符 SELECT A/B % 取余运算符 SELECT A%B 1.1 加法与减法操作符 SELECT 100,100+11,100-11,100+23.0,100-23.0 运算结果 由此得出结论: 一个整数加上…

微服务-微服务Alibaba-Nacos 源码分析 (源码流程图)

客户端流程 客户端心跳与实例往服务端注册

Linux部署幻兽帕鲁服务器,PalWorld开服联机教程,保姆级教程

------另一个号申请积分-------- Linux系统搭建PalWorld私服&#xff0c;幻兽帕鲁开服联机教程&#xff0c;保姆级教程 最近这游戏挺火&#xff0c;很多人想跟朋友联机&#xff0c;如果有专用服务器&#xff0c;就不需要房主一直开着电脑&#xff0c;稳定性也好得多。 幻兽帕…

单细胞scRNA-seq测序基础知识笔记

单细胞scRNA-seq测序基础知识笔记 scRNA-seq技术scRNA-seq 分析流程数据预处理聚类标准化数据筛选有用的数据数据降维聚类 Clustering 注释细胞类型 scRNA数据分析结尾 该笔记来源于 B站up 江湾青年 scRNA-seq技术 首先是如何测序&#xff0c;上图瓶中有很多细胞&#xff0c;…

npm 和 yarn 的使用

安装 yarn npm i yarn -g查看版本 npm -v yarn --version切换 npm/yarn 的下包镜像源 // 查看当前的镜像源 npm config get registry// 切换淘宝镜像源 // 新的淘宝源&#xff0c;旧的淘宝源已于2022年05月31日零时起停止服务 npm config set registry https://registry.…