洛谷题目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的分析 的相关文章

  • 需要解释“~0”与“2**64”(带和不带“使用整数”)

    我编写了一些测试程序打印的值 0 and 2 64 usr bin perl use warnings use strict use integer print 0 n print 2 64 n Without use integer程序输
  • PHP 中四舍五入到最大千、百等

    我有一个非常简单的 PHP 问题 但我不知道该怎么做 我想根据数据库返回的值四舍五入到最大百或千 以下是我需要的一些示例 DB返回值11 我希望PHP输出20 DB返回值104 我希望PHP输出200 DB返回值1404 我希望PHP输出2
  • C++ - 如何找到整数的长度

    我试图找到一种方法来查找整数的长度 位数 然后将其放入整数数组中 该作业还要求在不使用 STL 中的类的情况下执行此操作 尽管程序规范确实说我们可以使用 通用 C 库 我会问我的教授是否可以使用 cmath 因为我假设 log10 num
  • Oracle 12c - “number”列上的索引比“varchar”列上的索引执行得更快吗?

    假设我在 Oracle 12c 中有一个表 其中包含以下列 create table t1 a number 5 0 b varchar 5 0 d e 然后我在具有相同值的两列中插入 100 000 000 条记录 例如 20151 an
  • 如何计算(A*B)%C? [复制]

    这个问题在这里已经有答案了 有人可以帮我如何计算吗 A B C where 1 lt A B C lt 10 18在C 中 没有big num 只是一种数学方法 从我的脑海中浮现出来 未经广泛测试 typedef unsigned long
  • Java:乘以通用数字而不改变其类型

    Java中有没有办法实现这个方法 public static
  • 从 NXC 中的文件返回负值

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

    这个问题在这里已经有答案了 有没有一种快速的方法来查找字符串是否是实数 而不是一次读取一个字符并执行isdigit 在每个角色上 例如 我希望能够测试浮点数0 03001 如果您将浮点数表示为实数 则这应该有效 def isfloat st
  • 在 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年有什么
  • 可以将 std::numeric_limits 专门用于用户定义的类似数字的类吗?

    的文档std numeric limits
  • 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是一个数字字符串 意味着如果没有用引号括起来 它
  • Insert 语句中的记录数 (Oracle)

    我想报告 Oracle 插入语句中插入的记录数 我是从语句插入的 因此我可以运行两次选择并进行计数 但我宁愿将其全部保留在一个语句中 有办法吗 在 PL SQL 中执行 INSERTSQL ROWCOUNT给出插入的行数 在 C 中执行 I
  • 大于100,000的随机数

    我正在用 C C 编写 我想创建很多大于 100 000 的随机数 我该怎么做呢 和rand 你不会那样做rand 但使用较新的 C 附带的适当随机数生成器 请参见例如cppreference com http en cppreferenc
  • 从数组中打印素数

    我想用方法从数组中打印出所有素数 我可以用一个 int 来完成 但不知道如何从数组中返回某些数字 感谢帮助 public static boolean isPrime int tab boolean prime true for int i
  • Android 数字格式不知为何是错误的,我得到的不是 3.5,而是 3.499999999,为什么?

    我将一些数据存储在数据库中 然后使用游标读取这些数据 所有数据均为 56 45 3 04 0 03 类型 即小数点后两位 现在我想对它们求和 但这似乎并不容易 我得到这些数字c getDouble 3 然后我将它添加到 sum 变量中 如下
  • Ruby 中的数字运算(需要优化)

    Ruby 可能不是最适合这种情况的语言 但我很乐意在我的终端中使用它 所以这就是我要使用的 我需要处理从 1 到 666666 的数字 因此我找出包含 6 但不包含 7 8 或 9 的所有数字 第一个数字是6 下一个16 then 26等等
  • Android 软键盘先显示数字视图

    我的应用程序上有一个登录屏幕 它接受 CPF 作为登录名 CPF 是每个巴西公民都有的唯一号码标识 例如 10546819546 但它也可以接受护照号码作为登录名 并且上面可能有字母 我的问题是我希望键盘在弹出时在默认字母表之前显示数字 符
  • 在 php 中将单词转换为数字 II

    这里有一个很棒的功能在 PHP 中将单词转换为数字 https stackoverflow com questions 1077600 converting words to numbers in php来自埃尔约博 但我有一个问题 字符串
  • JavaScript 数字在内存中的大小都相同吗?

    我正在阅读本书的面向 Web 开发人员的专业 JavaScript 似乎所有 ECMAScript 数字都是 binary64 浮点数 这得到了证实这篇 MDN 文章 https developer mozilla org en US do
  • 如果数字小于 10,则显示前导零 [重复]

    这个问题在这里已经有答案了 可能的重复 JavaScript 相当于 printf string format https stackoverflow com questions 610406 javascript equivalent t

随机推荐

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

    矩阵是研究图的性质的最有效工具之一 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