每日算法系列【kentln供题】模糊的数字

godweiyang

发布于 2020-03-24 11:05:04

3330

发布于 2020-03-24 11:05:04

文章被收录于专栏：算法码上来

题目描述

感谢 kentln 供题，题目的出处已经不记得了，只能凭印象描述一下题意。

大致意思就是给你一个字符串，表示一个正整数，但是有些位已经模糊了（用表示）。现在知道它一定能被整除，求表示的正整数一共有多少种可能？注意，不允许出现前导。

示例1

输入：
8x4171x 5
输出：
20
解释：
第一个 x 可以取 0 到 9 一共 10 个数，第二个 x 只能取 0 或者 5 ，所以一共有 10 * 2 = 20 种可能。

示例2

输入：
x9953xx 1
输出：
900
解释：
第一个 x 可以取 1 到 9 一共 9 个数，后面两个 x 随便取，所以一共有 9 * 10 * 10 = 900 种可能。

提示

输入数据可能不止一组，请输入到文件结束为止
数据组数

题解

这题最暴力的方法就是枚举所有的数，然后判断每个数是否是倍数就行了，时间复杂度是，最大可以达到级别，无法接受！

那么我们从的最低位（也就是第 0 位）开始考虑，假设当前已经考虑到了第位。我们用数组表示前面位表示的所有数字中余数为可能有几种，初始的时候，其它都为（因为一位都没有的话，就当作处理）。

如果第位不是，那就说明第位上面已经有数字了。否则的话可以取到之间任意数（如果在最高位，排除掉）。

假设第位取，那么第位上面的数字在整个数字中的大小就是。假设它对取模结果是，那么对于前位来说，余数为的答案有种。加上第位之后，余数变成了，所以前位余数为的答案要加上。

最后整个的可能情况种数就是。

时间复杂度为，极限情况下会达到级别，还可以接受。

代码

c++

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    int n;
    while (cin >> s) {
        cin >> n;
        vector<int> c(n, 0);
        c[0] = 1;
        int pow = 1;
        for (int i = s.size()-1; i >= 0; --i) {
            int lb = 0, rb = 9;
            if (s[i] != 'x') {
                lb = rb = s[i] - '0';
            } else if (!i) {
                lb = 1;
            }
            vector<int> tc(n, 0);
            for (int j = lb; j <= rb; ++j) {
                int q = (j * pow) % n;
                for (int k = 0; k < n; ++k) {
                    tc[(q+k)%n] += c[k];
                }
            }
            c = tc;
            pow *= 10;
        }
        cout << c[0] << endl;
    }
    return 0;
}

评测

因为这题忘了出处了，所以评测的话得靠自己运行，然后和正确答案比较。

输入数据和标准输出在 公众号后台回复【kentln-0】 下载，步骤如下：

首先在你的 c++ 程序 main 函数开头加上如下两句：

freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);

作用就是重定向输入输出，从 in.txt 读入数据，输出答案到 out.txt 中。

编译你的 c++ 程序 g++ 代码文件名.cpp -o test ，并运行 ./test 。
然后比较你的输出和标准输出区别，采用命令 comp ans.txt out.txt 。

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-03-01，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自算法码上来微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

c++

登录后参与评论

0 条评论

热度