洛谷题目CF96B Lucky Numbers的分析

2023-05-16

题目描述:
佩佳喜欢幸运数字。每个人都知道,如果正整数的小数表示不包含除4和7以外的数字,那么它们是幸运的。例如,数字47,744,4是幸运的,5,17,467不是。如果幸运数的十进制表示包含相同数量的数字4和7,则幸运数是超级幸运的。例如,数字47,7744, 474477是超级幸运,4,744,467不是。有一天,Petya遇到了一个正整数n。帮助他找到最少的超级幸运数,它不少于n。
输入格式:
唯一的一行包含一个正整数n(1<=n<=10^{9}1<=n<=10 9)。这个数字没有前导零。
输出格式:
输出大于或等于n的最小超级幸运数。请不要使用%lld指定符在C++中读取或写入64位整数.最好使用cin、cout流或%I64d指定符。
思路分析及求解过程说明:
本题使用C++完成。刚拿到这道题的时候,想法就是从n开始判断每一个数的各个数位是不是均由4或7组成,如果是则进一步判断4和7的数量是否一样,在遇到第一个符合条件的数字后停止执行程序。本质是一种枚举,但是在n很大的时候要判断的数比较多,所以可能会超时,然后大致写了一下这种方法的代码,测试样例在本地也确实都过了,但是在提交到洛谷上的时候TLE了,如下图所示:
在这里插入图片描述
然后就要更换思路,首先通过超级幸运数字的特点可以知道输出的数字的数位一定是偶数位,而在前一种方法中会遍历不小于n的奇数位和偶数位数字,故当判断奇数位数字的时候便会大大浪费时间。然后我大概计算了一下所有可能输出的数字的个数,因为n<=10^9,故输出的最大数字为4444477777,再计算八位数以内的数字,共有2+6+20+70=98个,(对于有2n位的数字,由于其有n位为4,另外n位为7,通过运用高中数学知识可知其共有(2n)!/(n!)²种可能情况)所以一共有99个可能输出的数字,所以可以开一个数组,直接把它们按从小到大顺序储存在数组中,然后直接从小到大依次与n比较,直到遇上第一个不小于n的数字为止。最后使用这种方法在洛谷AC了这道题,所用时间为1.30秒,然后我大概翻了八页的提交记录,最快的用时为1.11秒(看来枚举还挺好用的哈)。然后发现题解里面也有用这种方法的,不过那个人把十位数的所有情况也算在内了,所以数组开到了350(所有符合条件的十位数有252个),耗时比我长一点。
在这里插入图片描述
源代码

#include<iostream>
using namespace std;
long long x[99]={47,74,4477,4747,4774,7447,7474,7744,444777,447477,447747,447774,474477,474747,474774,477447,477474,477744,744477,744747,744774,747447,747474,747744,774447,774474,774744,777444,44447777,44474777,44477477,44477747,44477774,44744777,44747477,44747747,44747774,44774477,44774747,44774774,44777447,44777474,44777744,47444777,47447477,47447747,47447774,47474477,47474747,47474774,47477447,47477474,47477744,47744477,47744747,47744774,47747447,47747474,47747744,47774447,47774474,47774744,47777444,74444777,74447477,74447747,74447774,74474477,74474747,74474774,74477447,74477474,74477744,74744477,74744747,74744774,74747447,74747474,74747744,74774447,74774474,74774744,74777444,77444477,77444747,77444774,77447447,77447474,77447744,77474447,77474474,77474744,77477444,77744447,77744474,77744744,77747444,77774444,4444477777};
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<350;i++){
        if(x[i]>=n){
            cout<<x[i]<<endl;
            return 0;
        }
    }
    return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

洛谷题目CF96B Lucky Numbers的分析 的相关文章

  • 如何在 APL 中将数字拆分为数字

    在 APL 中 如何将整数或数字拆分为包含其数字的向量 最简洁 最短 的方法是什么 您可以使用反函数Decode以 10 为底 10 1 since Decode将接收所需数量的数字并对其进行解码 其逆函数将接收一个数字并将其编码为所需数量
  • 如何将 php 中的数字 1,000 格式化为 1k

    我正在尝试格式化 php 中数字的输出 我显示了一定数量的帖子 每个用户旁边是帖子总数 但它显示了实际数量 我希望它以更短的格式显示 实际上 就像他们在 SO 享有盛誉的那样 有任何想法吗
  • JavaScript 中的 Number.sign()

    想知道是否有任何重要的方法可以找到数字的符号 符号函数 http en wikipedia org wiki Signum function 可能比明显的解决方案更短 更快 更优雅 var sign number gt 0 1 number
  • 将随机字节缩放到选定的整数范围

    我有一个真正的随机字节文件 我想要一个返回随机整数的函数在给定的范围内通过从文件中获取一个字节并对其进行缩放 这是正确的词吗 public int getInt int l int h throws IOException int m h
  • 从 NXC 中的文件返回负值

    我将值保存到 NXC 不是 eXactly C 中的 csv 文件 然后在稍后的时间点调用它们 我遇到的问题是 当从单元格中调用任何负值时 它会显示为 0123 而不是 123 这会导致我所有的额外计算失败 当前的代码是 OpenFileR
  • 在java中获取两个日期之间的天数[重复]

    这个问题在这里已经有答案了 您好 有两个日期格式的日期 如何获得两者之间的天数差异 Date date1 Date date2 int numberDays 建议使用 JodaTime API 来处理日期 import java util
  • 如何获取数字小数部分的长度?

    如何找出小数的小数部分的长度或位数 我可以看到一些方法 例如像这样的字符串 public static int getNumberOfFractionDigits Number number Double fractionPart numb
  • 在 DOS/Batch 中,08 小于 1,但 07 大于 1。为什么?

    在 DOS 批处理中 if 08 lss 1 echo true 与 真 相呼应 09也是如此 08和09都小于1 However if 07 lss 1 echo true 不回显任何内容 01至07不小于1 为什么 08年和09年有什么
  • is_numeric() 与 is_float() 与 is_int()

    我的理解是 if is numeric input true 那么要么 is float input true OR is int input true OR input 0 OR input是一个数字字符串 意味着如果没有用引号括起来 它
  • 有没有办法对 unsigned long long A 和 B 执行 (A*B) mod M 而不会溢出?

    我不想经历在 Windows 上安装 GMP 的噩梦 我有两个数字A和B unsigned long longs 最多 10 10 左右的数量级 但即使在这样做时 A M B M M 我得到整数溢出 是否有用于计算的自制函数 A B M对于
  • 仅使用 Y 数即可得出小于 X 的所有可能性?

    假设我有这些数字 2 25 37 54 54 76 88 91 99 这些是随机的 我需要找到小于 100 的数字的所有组合 并非所有数字都必须在这些组合中使用 示例 2 2 25 37 54 25 我怎样才能在 JavaScript 中实
  • 将 css 宽度字符串转换为常规数字

    在尝试计算隐藏元素的宽度时 我发现 jquery width 对于该元素的宽度返回 0 我发现使用 jquery css width 将通过使用声明的样式宽度返回正确的宽度 即使该值与初始样式表不同 问题是 css width 方法返回一个
  • Ruby 中的数字运算(需要优化)

    Ruby 可能不是最适合这种情况的语言 但我很乐意在我的终端中使用它 所以这就是我要使用的 我需要处理从 1 到 666666 的数字 因此我找出包含 6 但不包含 7 8 或 9 的所有数字 第一个数字是6 下一个16 then 26等等
  • 如何在 Erlang 中将数字转换为单词?

    我发现了一个关于将数字转换为 单词 的有趣问题 代码高尔夫 数字到单词 https stackoverflow com questions 309884 code golf number to words 我真的很想看看你如何在 Erlan
  • 将文本字段限制为仅包含数字的最佳方法?

    I m using the following Javascript to restrict a text field on my website to only accept numerical input and no other le
  • 如何在Java中将字符串3.0103E-7转换为0.00000030103?

    如何在Java中将字符串0E 11转换为0 00000000000 我想以非科学记数法显示数字 我尝试过查看 Java 中的数字格式化程序 但是我需要具体说明我想要的小数位数 但我并不总是知道 我只想要原始数字指定的小数位数 显然 正确的答
  • 定点数与浮点数

    我只是无法理解定点数和浮点数 因为在谷歌上很难阅读它们的定义 但我读过的文章都没有对它们的真正含义提供足够简单的解释 我可以通过例子得到一个简单的定义吗 定点数具有为整数部分 小数点左边的部分 保留的特定位数 或位数 和为小数部分 小数点右
  • 如何检查一个数字是否包含在一个范围内(在一个语句中)?

    我正在使用 Ruby on Rails 3 0 9 我想检查某个数字是否包含在某个范围内 也就是说 如果我有一个变量number 5我想检查一下1 lt number lt 10并检索一个布尔值 如果number值包含在该范围内 我可以这样
  • 如何在 Java 中将区域设置格式的数字转换为 BigInteger?

    我搜索了很多 但没有任何帮助 假设我需要将 12 090 129 019 201 920 192 091 029 102 901 920 192 019 201 920 葡萄牙语组分隔符 转换为 BigInteger 值 如何进行转换 我尝
  • JavaScript 中的正则表达式用于验证十进制数字

    我想要 JavaScript 中的正则表达式来验证十进制数字 它最多只允许两位小数 例如 它应该允许10 89但不是10 899 它还应该只允许一个句点 例如 它应该允许10 89但不是10 8 9 尝试使用以下表达式 d d 0 2 如果

随机推荐

  • 由有向图的邻接矩阵生成其可达矩阵

    矩阵是研究图的性质的最有效工具之一 xff0c 可运用矩阵运算求出图的路径 回路和其它性质 有些时候我们需要知道所给的图G中的某两个点之间是否存在边 xff0c 为此前人引入了可达矩阵 定义不再赘述 xff0c 在此给出一个由公式实 现的代
  • 【Android】串口通信的理论与使用教程

    Android系统诞生这十几年以来 xff0c Android开发工程师岗位经历了由盛转衰的过程 xff0c 目前纯UI的Android APP已经鲜有公司愿意花费巨资去开发 xff0c Android APP开发的业务也仅剩游戏 物联网
  • 《自己动手写Docker》书摘之三---Union File System介绍

    Union File System UnionFS unionfs是一种为Linux xff0c FreeBSD和NetBSD操作系统设计的把其他文件系统联合到一个联合挂载点的文件系统服务 它使用branch把不同文件系统的文件和目录 透明
  • 《程序设计基础课程设计》实验报告

    程序设计基础课程设计 实验报告 班 级 xff1a 学 号 xff1a 姓 名 xff1a 完成题目 xff1a 1 2 3 4 5 6 概述 此次六道题目里面第四题是参考某博主的文章后实现的 xff0c 有一些地方仍然不是特别理解 xff
  • C语言实现关系的闭包运算

    问题描述 xff1a 利用矩阵求解有限集上给定关系的自反和对称闭包 输入格式 xff1a 首先输入关系矩阵R的维数 xff0c 回车之后输入矩阵每个元素 xff0c 以空格或回车分开 只能输入0或1 输出格式 xff1a 输出自反闭包关系矩
  • 简单易懂的C语言课程设计图书管理系统

    最近几天一直在做课程设计的作业 xff0c 图书管理系统是其中的第六题 xff0c 和同学交流的时候发现好多人都用了链表去写 xff0c 但是我感觉没必要 xff0c 所以使用的代码比较基础 xff0c 适合初学者借鉴 先看一下题目 xff
  • C语言程序设计——前两道题(判断有效三角形和高精度计算的加减法)

    第1题 1 原题 xff1a 假设平面上有1 N x y 个坐标点 xff0c 编程判断这N x y 个点能组成多少个有效三角形 问题分析 xff1a 本题为一道基本编程题 xff0c 要点就是判断三个点能构成三角形的条件 解决方案 xff
  • C语言程序设计之RLE压缩解压算法

    先介绍一下RLE压缩算法 xff1a 游程编码 xff08 Run Length Encoding RLE xff09 又称行程长度编码或者变动长度编码法 xff0c 在控制理论中对于二值图像而言是一种编码方法 xff0c 对连续的黑 xf
  • 浅析洛谷P4924(一道普及/提高-的题目)的解决方法

    题目描述 xff1a Scarlet最近学会了一个数组魔法 xff0c 她会在n n二维数组上将一个奇数阶方阵按照顺时针或者逆时针旋转90 首先 xff0c Scarlet会把1到n 2的正整数按照从左往右 xff0c 从上至下的顺序填入初
  • 判断图的连通性

    上机系统的判分功能目前还没开放 xff0c 所以以下所给代码仅供参考 xff0c 并不能保证完全正确 xff08 自己分别测试了强连通 xff0c 单向连通 xff0c 弱连通 xff0c 不连通的一个样例 xff0c 都过了 xff09
  • BMP格式详解

    BMP xff08 全称Bitmap xff09 是Windows操作系统中的标准图像文件格式 xff0c 可以分成两类 xff1a 设备相关位图 xff08 DDB xff09 和设备无关位图 xff08 DIB xff09 xff0c
  • 标准数独的求解

    上机题目中有一道题目的要求是通过编程实现数独的求解 xff0c 然后想起了初三去后来所在的高中面试提前录取的时候里面的压轴题便是数独 xff0c 当时做了好长时间也没搞出来 xff0c 我还记得监考老师当时和我说 xff1a 做不出来就别勉
  • 利用定义求解传递闭包的关系矩阵

    题目描述 给定有限集合上二元关系的关系矩阵 xff0c 利用传递闭包的定义式 xff08 不是warshall算法 xff09 求其传递闭包的关系矩阵 源代码 span class token macro property span cla
  • 【Android】解决Expecting member declaration

    问题截图 刚刚安装的android studio安装完成就出现异常错误 原因 新建project的时候 xff0c language项选错了 xff0c 应选java 解决错误的办法 新建一个Project的时候 xff0c Languag
  • 矩阵乘法的实现(一般形式及单个矩阵的n次幂)

    目录 一般矩阵乘法实现矩阵的n次幂的实现 一般矩阵乘法实现 题目描述1 给定m k的布尔矩阵A xff0c 和k n的布尔矩阵B xff0c 求布尔矩阵的乘积AB 源代码1 span class token macro property s
  • 根据给出的关系矩阵,判断该关系所具有的特性

    目录 自反性与反自反性的判断对称性与反对称性的判断传递性的判断 自反性与反自反性的判断 关系R是自反的 xff0c 当且仅当其关系矩阵的主对角线上元素都为1 xff1b 关系R是反自反的 xff0c 当且仅当其关系矩阵的主对角线上元素都为0
  • 输出所有满足条件的关系

    目录 for循环解决简单问题调用库函数解决全排列问题 for循环解决简单问题 题目描述 源代码 span class token macro property span class token directive keyword inclu
  • 按字典序输出给定序列

    上机题目里面有不少挨着的相似的题 xff0c 下面所给的这两道偏简单 xff0c 就介绍一下用python和c实现的代码 题目描述 python实现的代码用到了sorted函数 xff0c 该函数在python3里面有三个参数 xff0c
  • 求给定图中某两点之间某一长度的路径条数

    无向图的一道例题 输出c到d长度为以下长度的路径条数 xff1a 源代码 span class token macro property span class token directive keyword include span spa
  • 洛谷题目CF96B Lucky Numbers的分析

    题目描述 xff1a 佩佳喜欢幸运数字 每个人都知道 xff0c 如果正整数的小数表示不包含除4和7以外的数字 xff0c 那么它们是幸运的 例如 xff0c 数字47 744 xff0c 4是幸运的 xff0c 5 xff0c 17 46