首页 > 试题广场 >

明七暗七

[编程题]明七暗七

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

今天是个特殊的日子，CSL和他的小伙伴们围坐在一张桌子上玩起了明七暗七的游戏。游戏规则是这样的：

一个人报出一个起始数，接下来按照逆时针的顺序轮流报数，如果碰到数是7的倍数或含有7，则拍手，下一个人接着报数。直到有一个人报错了数字或者没有及时拍手为止。

玩游戏嘛，当然得有惩罚。这么简单的游戏对CSL的学霸小伙伴而言实在是太无脑了，轻轻松松数到上万根本不在话下。但是对于数学是体育老师教的CSL来说，实在是太难了。快帮他算算什么时候应该拍手吧。

输入描述:

输入两个整数m和n。(1 ≤ m, n ≤ 10¹²)

输出描述:

输出一个整数，表示m以后第n个需要拍手的数字。

示例1

输入

30 7

输出

示例2

输入

56 1

输出

算法知识视频讲解

赵和杰

发表于 2020-07-28 18:08:36

代码中有详细解释，cnt要使用long long int(害我找了好久):joy: #include <bits/stdc++.h> using namespace std; typedef long long int ll; ll m, n, cntn, cntx, dp[20][10 展开全文

憕

发表于 2022-11-16 16:47:47

D 明七暗七 +数位dp+二分转变一下题意可以变为求区间内所有满足含有7或者是7的倍数的数，第一个条件数位dp容易枚举，第二个条件需要记录好每位数对7取模的余数，如果余数为0即为倍数。如14，第一位数位10，对7取模的余数维3，第二位为4对7取模余数为4，两者之和对7取模余数为0，故为7的倍数。故展开全文

瑜画

发表于 2020-08-20 22:47:54

根据题目，要求什么设什么。因为题目要求的是m以后第n个符合的数，在数位dp中，求出数的答案个数，总是单调递增的，由此可以分析出需要二分答案。对于dp如何设定状态，由于题目要求一个“明七”，一个“暗七”，那么明七很明显就是有没有某个数位出现7，用一个变量have来表示，“暗七”就在最后算完的时候，看展开全文