Codeforces Round #698 (Div. 2) - B. Nezzar and Lucky Number 题解_problem a. lucky numbertimelimit : 2second, memory

Codeforces Round #698 (Div. 2)-B. Nezzar and Lucky Number

传送门
Time Limit: 1 second
Memory Limit: 512 megabytes

Problem Description

Nezzar’s favorite digit among $1,\dots ,9$ is $d$. He calls a positive integer lucky if $d$ occurs at least once in its decimal representation.

Given $q$ integers $a_1,a_2,\dots ,a_q$, for each $1\le i\le q$ Nezzar would like to know if $a_i$ can be equal to a sum of several (one or more) lucky numbers.

Input

The first line contains a single integer $t$ ($1\le t\le 9$) — the number of test cases.

The first line of each test case contains two integers $q$ and $d$ ($1\le q\le 10^4$, $1\le d\le 9$).

The second line of each test case contains $q$ integers $a_1,a_2,\dots ,a_q$ ($1\le a_i\le 10^9$).

Output

For each integer in each test case, print “YES” in a single line if $a_i$ can be equal to a sum of lucky numbers. Otherwise, print “NO”.

You can print letters in any case (upper or lower).

Sample Input

2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60
1
2
3
4
5

Sample Onput

YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
1
2
3
4
5
6
7
8
9
10
11
12
13

Note

In the first test case, $24=17+7$, $27$ itself is a lucky number, $25$ cannot be equal to a sum of lucky numbers.

题目大意

Nezzar的幸运数字是d，一个十进制数中任何一位出现了d就是lucky number。问一个数n能不能拆成lucky number的和。

例：假如Nezzar的幸运数字d=3，那么3，13，32等都是lucky number。

---

解题思路

首先不难发现，当n≥10*d时，一定是lucky number。

因为一个n可以拆成10*d+(k) + d+d+…+d (k<10）。
看不懂没关系，举个例子：

假如Nezzar的幸运数字是7，那么70≤n≤79时，n直接就是lucky number（十位数含7）；
当n>=80时，n可以拆成七十几加j个7。
如：83 = 76 + 7；138 = 75 + 7 + 7 + … +7。

关键就在于n<10*d时，能不能拆成lucky number的和。

–

接下来只考虑n<10*d的情况。
对于一个特点的d，首先d的倍数是一定可以拆成几个d的和的。
用 can[d][n]来记录幸运数字是d时n能不能拆成lucky number。

初始值bool can[10][91]={false};，之后对于每一个d∈[1,9]，d的倍数全为true。

for (int d = 1; d <= 9; d++)
{
    for (int k = 1; k <= 10; k++)
    {
        can[d][d * k] = true;
    }
}
1
2
3
4
5
6
7

然后，我们可以发现，对于d=3， 13和23也是lucky number。
那么13加上3的倍数也是lucky number。
23加上其他lucky number也是lucky number。

同理，对于d=8， 18、28、38…88都是lucky number。
它们加上其他lucky number也都是lucky number。

for (int d = 1; d <= 9; d++)
{
    for (int k = 1; k <= d; k++)  //例如d=3，那么就需要把13、23变成true
	{
		int thisOne = k * 10 + d; //13、23
		can[d][thisOne] = true; 
		for (int j = 1; j + thisOne <= d * 10; j++) //这个数加上所有的lucky number都是lucky number，枚举所有考虑范围内的数
		{
			if (can[d][j])
			{
				can[d][j + thisOne] = 1;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

至此，我们已经获得了所有≤10*d的lucky number了。

万事俱备，只欠东风。
给一个数n，如果n<10*d，就看看can[d][n]是否为true就行了。

AC代码

#include <bits/stdc++.h>
using namespace std;
bool can[10][91] = {0};
void init()
{
	for (int d = 1; d <= 9; d++)
	{
		for (int k = 1; k <= 10; k++)
		{
			can[d][d * k] = true;
		}
	}
	for (int d = 1; d <= 9; d++)
	{
		for (int k = 1; k <= d; k++) //例如d=3，那么就需要把13、23变成true
		{
			int thisOne = k * 10 + d; //13、23
			can[d][thisOne] = true;
			for (int j = 1; j + thisOne <= d * 10; j++) //这个数加上所有的lucky number都是lucky number，枚举所有考虑范围内的数
			{
				if (can[d][j])
				{
					can[d][j + thisOne] = 1;
				}
			}
		}
	}
}
int main()
{
	init();
	int N;
	cin >> N;
	while (N--)
	{
		int n, d;
		cin >> n >> d;
		for (int i = 0; i < n; i++)
		{
			int t;
			scanf("%d", &t);
			if (t >= d * 10)
				puts("YES");
			else
				puts(can[d][t] ? "YES" : "NO");
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49