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

题目描述

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

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

示例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 种可能。
      

提示

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

题解

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

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

如果第 i 位不是 x ,那就说明第 i 位上面已经有数字了。否则的话可以取 09 之间任意数(如果 x 在最高位,排除掉 0)。

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

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

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

代码

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带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

09-29 11:19
门头沟学院 Java
点赞 评论 收藏
分享
10-24 11:10
山西大学 Java
若梦难了:哥们,面试挂是很正常的。我大中厂终面挂,加起来快10次了,继续努力吧。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务