刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

3.数字构造
火山宝打算造一个 n 位的十进制数字出来。
对于 1 到 n 中的每一个 i，火山宝可以从 xi,1, ..., xi,ki 这 ki 个 0-9 的数字中选择一个作为 ai。
在选择结束后，a1a2...an 形成了一个 n 位的十进制数——这就是火山宝造出来的数。
你需要帮火山宝计算他能造出的数中，有多少个是 3 的倍数。
时间限制：1000
内存限制：65536
输入
第一行输入一个整数 n(1 ≤ n ≤ 18)，表示数字的位数。 接下来 n 行，每行第一个整数 ki (1 ≤ ki ≤ 10)，表示第 i 中候选的数字数量。接着是 ki 个两两不同的 0-9 范围内的数字 xi,1, ..., xi,ki。 输入保证 0 不是第一位的可选项。
输出
你需要输出一行一个整数，表示火山宝能造出的数字中，3 的倍数的数量。
样例输入
样例输入1：
2
5 5 6 7 8 9
5 0 1 2 3 4
样例输入2：
5
9 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
样例输出
样例输出1：
9
样例输出2：
30000
提示
样例1能造出来的 3 的倍数有 51, 54,60,63,72,81,84,90, 93。

使用微信搜索喵呜刷题，轻松应对考试！

答案：

略

解析：

【喵呜刷题小喵解析】：本题是一道动态规划问题，可以使用动态规划来解决。首先，定义 dp[i][j] 表示前 i 位数字中，以数字 j 结尾的 3 的倍数的数量。根据题目描述，我们可以得到以下状态转移方程：1. 如果 j % 3 == 0，则 dp[i][j] = dp[i - 1][(j - num) % 10] + 1，表示前 i 位数字中，以 j 结尾的 3 的倍数，可以由前 i-1 位数字中，以 (j - num) % 10 结尾的 3 的倍数加 1 得到。2. 如果 j % 3 != 0，则 dp[i][j] = dp[i - 1][(j - num + 10) % 10]，表示前 i 位数字中，以 j 结尾的 3 的倍数，只能由前 i-1 位数字中，以 (j - num + 10) % 10 结尾的 3 的倍数得到。初始条件为 dp[1][j] = 1，表示只有一位数字时，以数字 j 结尾的 3 的倍数的数量只有 1。最后，输出 dp[n][0]，表示 n 位数字中，以 0 结尾的 3 的倍数的数量，即为题目要求的答案。时间复杂度为 O(n * k * 10)，其中 n 为数字的位数，k 为第 i 位数字的可选数字数量，10 为数字的范围。
创作类型：
原创

本文链接：3.数字构造 火山宝打算造一个 n 位的十进制数字出来。 对于 1 到 n 中的每一个 i，火山

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share