目录
- 度的数量
- 思路
- 代码实现
- 暴力解法
- 数位DP
- 数字游戏
- 代码实现
- Windy数
- 代码实现
- 数字游戏 II
- 代码实现
- 不要62
- 代码实现
- 恨7不成妻
- 代码实现
度的数量
题目描述:
求给定区间 [ X , Y ] [X,Y] [X,Y] 中满足下列条件的整数个数:这个数恰好等于 K K K 个互不相等的 B B B 的整数次幂之和。
例如,设 X = 15 , Y = 20 , K = 2 , B = 2 X=15, Y=20, K=2, B=2 X=15,Y=20,K=2,B=2,则有且仅有下列三个数满足题意:
17 = 2 4 + 2 0 17 = 2^4 + 2^0 17=24+20
18 = 2 4 + 2 1 18 = 2^4 + 2^1 18=24+21
20 = 2 4 + 2 2 20 = 2^4 + 2^2 20=24+22
输入格式:
第一行包含两个整数 X X X 和 Y Y Y,接下来两行包含整数 K K K 和 B B B。
输出格式:
只包含一个整数,表示满足条件的数的个数。
数据范围:
1 ≤ X ≤ Y ≤ 2 31 − 1 , 1 ≤ K ≤ 20 , 2 ≤ B ≤ 10 1 ≤ X ≤ Y ≤ 2^{31} − 1, 1 ≤ K ≤ 20, 2 ≤ B ≤ 10 1≤X≤Y≤231−1,1≤K≤20,2≤B≤10
输入样例:
15 20
2
2
输出样例:
3
思路
利用前缀和的思想求解对应区间符合形式的数的个数。
[ l , r ] ⇔ [ 0 , r ] − [ 0 , l − 1 ] [l, r] ⇔ [0, r] - [0, l - 1] [l,r]⇔[0,r]−[0,l−1]
要使这个数恰好等于 K K K 个互不相等的 B B B 的整数次幂之和,即化为 B B B 进制之后,存在 K K K 个 1 1 1,除 1 1 1 和 0 0 0 之外的数均不可出现。
例如: B = 3 B=3 B=3, K = 2 K=2 K=2,一个符合的数是 12 12 12,把 12 12 12 化为三进制 110
,其中有 2 2 2 个 1 1 1,其余都是 0 0 0。
代码实现
暴力解法
import sys
input = sys.stdin.readlinex, y = map(int, input().strip().split())
k, b = int(input().strip()), int(input().strip())def dfs(cnt, idx, total, up):if total > up:return 0if cnt == k:return 1if pow(b, idx) > up:return 0return dfs(cnt, idx + 1, total, up) + dfs(cnt + 1, idx + 1, total + pow(b, idx), up)print(dfs(0, 0, 0, y) - dfs(0, 0, 0, x - 1))
数位DP
import sys
from functools import cache
sys.setrecursionlimit(1000000)
input = sys.stdin.readlinex, y = map(int, input().strip().split())
k, b = int(input().strip()), int(input().strip())def int_to_base_b(n):if n == 0:return "0"res = ""while n:res = str(n % b) + resn //= breturn res@cache
def dfs(idx, cnt, is_limit, is_num, s):if len(s) == idx:return int(cnt == k and is_num)if cnt > k:return 0res = 0if not is_num:res = dfs(idx + 1, cnt, False, False, s)up = min(1, int(s[idx])) if is_limit else 1for d in range(1 - int(is_num), up + 1):res += dfs(idx + 1, cnt + d, is_limit and d == int(s[idx]), True, s)return resprint(dfs(0, 0, True, False, int_to_base_b(y)) - dfs(0, 0, True, False, int_to_base_b(x - 1)))
数字游戏
题目描述:
科协里最近很流行数字游戏。
某人命名了一种不降数,这种数字必须满足从左到右各位数字呈非下降关系,如 123 123 123, 446 446 446。
现在大家决定玩一个游戏,指定一个整数闭区间 [a,b],问这个区间内有多少个不降数。
输入格式:
输入包含多组测试数据。
每组数据占一行,包含两个整数 a a a 和 b b b。
输出格式:
每行给出一组测试数据的答案,即 [ a , b ] [a,b] [a,b] 之间有多少不降数。
数据范围:
1 ≤ a ≤ b ≤ 2 3 1 − 1 1 ≤ a ≤ b ≤ 2^31−1 1≤a≤b≤231−1
输入样例:
1 9
1 19
输出样例:
9
18
代码实现
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input = sys.stdin.readline@lru_cache(maxsize=None, typed=False)
def dfs(idx, front, is_limit, is_num, s):if idx == len(s):return int(is_num)res = 0if not is_num:res = dfs(idx + 1, 0, False, False, s)up = int(s[idx]) if is_limit else 9for d in range(max(1 - int(is_num), front), up + 1):res += dfs(idx + 1, d, is_limit and d == up, True, s)return restry:while True:a, b = map(int, input().strip().split())print(dfs(0, 0, True, False, str(b)) - dfs(0, 0, True, False, str(a - 1)))except ValueError:sys.exit(0)
Windy数
题目描述:
W i n d y Windy Windy 定义了一种 W i n d y Windy Windy 数:不含前导零且相邻两个数字之差至少为 2 2 2 的正整数被称为 W i n d y Windy Windy 数。
W i n d y Windy Windy 想知道,在 A A A 和 B B B 之间,包括 A A A 和 B B B,总共有多少个 W i n d y Windy Windy 数?
输入格式:
共一行,包含两个整数 A A A 和 B B B。
输出格式:
输出一个整数,表示答案。
数据范围:
1 ≤ A ≤ B ≤ 2 × 1 0 9 1 ≤ A ≤ B ≤ 2×10^9 1≤A≤B≤2×109
输入样例1:
1 10
输出样例1:
9
输入样例2:
25 50
输出样例2:
20
代码实现
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input = sys.stdin.readline@lru_cache(maxsize=None, typed=False)
def dfs(idx, front, is_limit, is_num, s):if idx == len(s):return int(is_num)res = 0if not is_num:res = dfs(idx + 1, front, False, False, s)up = int(s[idx]) if is_limit else 9for d in range(1 - int(is_num), up + 1):if is_num and abs(front - d) < 2:continueres += dfs(idx + 1, d, is_limit and d == up, True, s)return resa, b = map(int, input().strip().split())
print(dfs(0, 0, True, False, str(b)) - dfs(0, 0, True, False, str(a - 1)))
数字游戏 II
题目描述:
由于科协里最近真的很流行数字游戏。
某人又命名了一种取模数,这种数字必须满足各位数字之和 m o d N \mod N modN 为 0 0 0。
现在大家又要玩游戏了,指定一个整数闭区间 [ a , b ] [a,b] [a,b],问这个区间内有多少个取模数。
输入格式:
输入包含多组测试数据,每组数据占一行。
每组数据包含三个整数 a , b , N a, b, N a,b,N。
输出格式:
对于每个测试数据输出一行结果,表示区间内各位数字和 m o d N \mod N modN 为 0 0 0 的数的个数。
数据范围:
1 ≤ a , b ≤ 2 31 − 1 , 1 ≤ N < 100 1 ≤ a, b ≤ 2^{31}−1, 1 ≤ N < 100 1≤a,b≤231−1,1≤N<100
输入样例:
1 19 9
输出样例:
2
代码实现
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input = sys.stdin.readlinea, b, N = map(int, input().strip().split())@lru_cache(maxsize=None, typed=False)
def dfs(idx, total, is_limit, is_num, s):if len(s) == idx:return int(is_num and total % N == 0)res = 0if not is_num:res = dfs(idx + 1, total, False, False, s)up = int(s[idx]) if is_limit else 9for d in range(1 - int(is_num), up + 1):res += dfs(idx + 1, (total + d) % N, is_limit and d == up, True, s)return resprint(dfs(0, 0, True, False, str(b)) - dfs(0, 0, True, False, str(a - 1)))
不要62
题目描述:
杭州人称那些傻乎乎粘嗒嗒的人为 62 62 62(音: l a o e r laoer laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有 4 4 4 或 62 62 62 的号码。例如: 62315 62315 62315、 73418 73418 73418、 88914 88914 88914 都属于不吉利号码。但是, 61152 61152 61152 虽然含有 6 6 6 和 2 2 2,但不是连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照号区间 [ n , m ] [n, m] [n,m],推断出交管局今后又要实际上给多少辆新的士车上牌照了。
输入格式:
输入包含多组测试数据,每组数据占一行。
每组数据包含一个整数对 n n n 和 m m m。
当输入一行为 0 0
时,表示输入结束。
输出格式:
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
数据范围:
1 ≤ n ≤ m ≤ 1 0 9 1 ≤ n ≤ m ≤ 10^9 1≤n≤m≤109
输入样例:
1 100
0 0
输出样例:
80
代码实现
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input = sys.stdin.readline@lru_cache(maxsize=None, typed=False)
def dfs(idx, front, is_limit, is_num, s):if idx == len(s):return int(is_num)res = 0if not is_num:res = dfs(idx + 1, front, False, False, s)up = int(s[idx]) if is_limit else 9for d in range(1 - int(is_num), up + 1):if is_num and d == 2 and front == 6 or d == 4:continueres += dfs(idx + 1, d, is_limit and d == up, True, s)return reswhile True:n, m = map(int, input().strip().split())if n == m == 0:breakprint(dfs(0, 0, True, False, str(m)) - dfs(0, 0, True, False, str(n - 1)))
恨7不成妻
题目描述:
单身!
依然单身!
吉哥依然单身!
D S DS DS 级码农吉哥依然单身!
所以,他平生最恨情人节,不管是 214 214 214 还是 77 77 77,他都讨厌!
吉哥观察了 214 214 214 和 77 77 77 这两个数,发现:
2 + 1 + 4 = 7 2 + 1 + 4 = 7 2+1+4=7
7 + 7 = 7 × 2 7 + 7 = 7 \times 2 7+7=7×2
77 = 7 × 11 77 = 7 \times 11 77=7×11
最终,他发现原来这一切归根到底都是因为和 7 7 7 有关!
所以,他现在甚至讨厌一切和 7 7 7$ 有关的数!
什么样的数和 7 7 7 有关呢?
如果一个整数符合下面三个条件之一,那么我们就说这个整数和 7 7 7 有关:
① 整数中某一位是 7 7 7;
② 整数的每一位加起来的和是 7 7 7 的整数倍;
③ 这个整数是 7 7 7 的整数倍。
现在问题来了:吉哥想知道在一定区间内和 7 7 7 无关的整数的平方和。
输入格式:
第一行包含整数 T T T,表示共有 T T T 组测试数据。
接下来 T T T 行,每行包含两个整数 L L L 和 R R R。
输出格式:
对于每组数据,请计算 [ L , R ] [L, R] [L,R] 中和 7 7 7 无关的数字的平方和,并将结果对 1 0 9 + 7 10^9 + 7 109+7 取模后输出。
数据范围:
1 ≤ T ≤ 50 1 ≤ T ≤ 50 1≤T≤50
1 ≤ L ≤ R ≤ 1 0 18 1 ≤ L ≤ R ≤ 10^{18} 1≤L≤R≤1018
输入样例:
3
1 9
10 11
17 17
输出样例:
236
221
0
代码实现
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
input = sys.stdin.readline@lru_cache(maxsize=None, typed=False)
def dfs(idx, sum_digit, total, is_limit, is_num, s):if idx == len(s):if not is_num or sum_digit % 7 == 0 or int(total) % 7 == 0:return 0return int(total) ** 2res = 0if not is_num:res = dfs(idx + 1, sum_digit, total, False, False, s)up = int(s[idx]) if is_limit else 9for d in range(1 - int(is_num), up + 1):if d == 7:continueres += dfs(idx + 1, sum_digit + d, total + str(d), is_limit and d == up, True, s)return rest = int(input().strip())
for _ in range(t):a, b = map(int, input().strip().split())print(dfs(0, 0, "", True, False, str(b)) - dfs(0, 0, "", True, False, str(a - 1)))