主页 / 问题 / 1418083
Accepted
Thwrani
Asked:2022-08-08 15:07:38 +0000 UTC2022-08-08 15:07:38 +0000 UTC

任务：“有趣的数字”

  • 772

索菲亚发现一个数字很有趣，如果它的数字是非递减顺序的。例如，数字 123、1111 或 888999 很有趣。

索菲亚对存在多少有趣的正数感兴趣，这些正数存在于从 L 到 R 的范围内。这个数字对于大的 L 和 R 来说可能非常大，所以 Sofia 想要找到这个数字除以 10^9+7 后的余数。

需要编写一个程序，在给定 L 和 R 的情况下，确定 L 到 R（包括 L 到 R）范围内的有趣数字的数量，并显示该数字除以 10^9+7 后的余数。

限制：1 <= L <= R <= 10^100

示例：输入：1\n100 输出：54

我用python写了这段代码：

def f(n):
    res, min_num = 0, 0
    for i, j in enumerate(n):
        j = int(j)
        if j < min_num: 
            return res
        elif j > min_num:
            res += sum(a[len(n) - i][9 - x] for x in range(min_num, j))
            min_num = j
    return res + 1
L = input()
R = input()
p = 10 ** 9 + 7 
s = len(R)
a = [[0] * 10 for _ in range(s + 1)]
a[0][0] = 1
for k in range(1, s + 1):
    for i in range(10):
        a[k][i] = sum(a[k - 1][j] for j in range(i + 1))
print((f(R) - f(str(int(L) - 1))) % p)

这是相同的算法，仅在 C++ 中：

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <numeric>
using namespace std;
const long long p = pow(10, 9) + 7;
string decrease(string str)
{
    //Уменьшает число в строке на 1
    int l = str.length();
    if (str[l - 1] == '0')
    {
        int i = l - 1;
        while (str[i] == '0' && i > 0)
        {
            str = str.substr(0, i) + "9" + str.substr(i + 1, l);
            i--;
        }
        str = str.substr(0, i) + to_string(str[i] - '0' - 1) + str.substr(i + 1, l);
        return str;
    }
    else
        return str.substr(0, l - 1) + to_string(str[l - 1] - '0' - 1);
}
long long f(string n, vector<vector<long long>> a)
{
    long long res = 0; long long min_num = 0;
    for (int i = 0; i < n.length(); i++)
    {
        int j = n[i] - '0';
        if (j < min_num)
            return res;
        else if (j > min_num)
        {
            vector<long long> tmp (0);
            for (int x = min_num; x < j; x++)
                tmp.push_back(a[n.length() - i][9 - x]);
            res = (res + accumulate(tmp.begin(), tmp.end(), 0)) % p;
            min_num = j;
        }
    }
    return res + 1;
}
int main()
{
    string l; string r;
    cin >> l;
    cin >> r;
    long long s = r.length();
    vector<long long> tmp (10, 0);
    vector<vector<long long>> a (s + 1, tmp);
    a[0][0] = 1;
    for (int k = 1; k <= s; k++)
    {
        for (int i = 0; i < 10; i++)
        {
            vector<long long> tmp (0);
            for (int j = 0; j <= i; j++)
                tmp.push_back(a[k - 1][j]);
            a[k][i] = accumulate(tmp.begin(), tmp.end(), 0) % p;
        }
    }
    cout << (f(r, a) - f(decrease(l), a)) % p;
}

Python 代码通过了所有测试，但 C++ 代码将在 0 秒后的第一次测试中崩溃（给出错误答案）。请帮忙，C++代码有什么问题？（我不知道测试数据） C++ 代码已更改。将 to_str(stoll(l) - 1) 更改为执行相同操作的函数，但将 l 保留为字符串。它仍然无法正常工作......

python c++

3 个回答

  1. 该算法正在运行。两个程序（在 C++ 和 Python 中）的答案是相同的。
    我只发现了 1 个错误：
    获得了除法余数的 3 次res % p- 在函数f()中，在main(). 在 python 代码中，这在最后完成了 1 次。只要数组中的数字小于 不影响结果p，但是对于较大的值可能会出现计算错误，因为。将数字的数量输入到数组中，并在程序结束时计算两个数字之间的差异。如果你在除法的余数之间产生差异，那么你甚至可以得到一个负数。

    long long f(string n, vector<vector<long long>> a)
{
  ...
            res = (res + accumulate(tmp.begin(), tmp.end(), 0)) % p;
    return res + 1;
}
int main()
{
        for (int i = 0; i < 10; i++)
        {
            a[k][i] = accumulate(tmp.begin(), tmp.end(), 0) % p;
        }
    cout << (f(r, a) - f(decrease(l), a)) % p;
}

    好吧，程序中的一些注释：
    在循环中main()和f()计数时，您不需要创建一个临时向量，添加一些东西然后总结它。你可以马上总结。

    long long f(string n, const vector<vector<long long>>& a)
{
        if (j >= min_num)
        {
/*            vector<long long> tmp (0);        // вместо этого 
            for (int x = min_num; x < j; x++)
                tmp.push_back(a[len - i][9 - x]);
            res = (res + accumulate(tmp.begin(), tmp.end(), 0)) % p;
*/
            for (int x = min_num; x < j; x++)  // написать вот так
                res += a[len - i][8 - x];

            min_num = j;
        }
}

    最好通过常量引用将参数传递给函数。

    long long f(const string& n, const vector<vector<long long>> &a)

    最好在函数中创建一个f()值，因为 它是数组中的一个索引，它的值范围是0到9min_numint

    long long f(string n, vector<vector<long long>> a)
{
    long long min_num = 0; // это индекс, он изменяется от 0 до 9

    有趣的数字以至少有 1 位数字的数字开头。因此，可以减少行数。零线 - 个位数的有趣数字的数量。但另一方面 - 它工作正常！

    • 1
  2. Best Answer

    如果你删除循环中的中间向量，它会给出与 python 相同的结果。怀疑函数accumulate()执行不正确。

    #include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <numeric>
using namespace std;
const long long p = pow(10, 9) + 7;

long long f(string n, vector<vector<long long>> &a)
{
    long long res = 0; 
    int min_num = 0;
    for (int i = 0; i < n.length(); i++)
    {
        int j = n[i] - '0';
        if (j < min_num)
            return res;
        else if (j > min_num)
        {
            for (int x = min_num; x < j; x++)
                res += a[n.length() - i][9 - x];
            min_num = j;
        }
    }
    return res + 1;
}

int main()
{
    string l = "91111111119111111111911111111191111111119111111111"; 
    string r = "9111111111911111111191111111119111111111911111111191111111119111111111";
    
    
    int s = r.length();
    cout << s << "\n";
    cout << decrease(l) << "\n";
    
    vector<long long> tmp (10, 0);
    vector<vector<long long>> a (s + 1, tmp);
    a[0][0] = 1;
    for (int k = 1; k <= s; k++)
    {
        for (int i = 0; i < 10; i++)
        {
           for (int j = 0; j <= i; j++)
                a[k][i] += a[k - 1][j];
        }
    }
    
   
    long long rv = f(r, a);
    long long lv = f(decrease(l), a);
    
    cout << rv << "\n";
    cout << lv << "\n";
    cout << rv - lv << "\n";
    cout << (rv - lv) % p;
}
    • 1

  3. C++。int：表示一个整数。根据处理器的架构，它可以占用 2 个字节（16 位）或 4 个字节（32 位）。限制值的范围也可以分别从 -32768 到 32767（2 个字节）或从 -2 147 483 648 到 2 147 483 647（4 个字节）变化。

    也许这就是问题？

    • 0

相关问题