• 欢迎光临~

CF1681D Required Length

开发技术 开发技术 2022-10-16 次浏览

CF1681D Required Length - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

注意到,选用 (0)(1) 这两种数位相乘的操作是没有任何用处的,所以下面的操作直接过滤掉这两种情况。

(N = 10^n)。每次操作后的结果一定可以分解为 (x times 2^alpha times 3^beta times 5^gamma times 7^delta)。而 (2^alpha, 3^beta, 5^gamma, 7^delta < N),因此操作结果最多有 (log_2N times log_3 N times log_5N times log_7N) 种, 算一算是 (63 times 39 times 27 times 22 approx 1.5 times 10^6)。因此,直接 bfs 即可。

怎么记忆化判重?传统 vis 数组就不太行了,因为值域有 (10^{19}),那么这里有两种写法:

  • 四维:(vis(alpha,beta,gamma,delta)) 表示 (x times 2^alpha times 3^beta times 5^gamma times 7^delta) 是否访问过。这样所需空间也是 (1.5 times 10^6)
  • 把访问过的数丢 set 里面。

我采用了第二种,这样代码更好写。不过这样会自动带一个 (log)

时间复杂度 (mathcal{O}(w(log w + n))),其中 (w = log_2N times log_3 N times log_5N times log_7N)(N = 10^n)

小细节:

  • long long 取值范围是 (9.2 times 10^{18}),装不下最大的 (19) 位数 (10^{19} - 1)。因此应选用 unsigned long long。
  • 一次操作位数最多增加 (1)。因此当 bfs 到当前状态的 (num) 大于等于 (10^{n-1}) 直接输出 (num) 即可,不用判断会不会超出去。

目前最优解 46 ms,在我之上的两位评测时只有三个数据点(样例)所以不算。但事实上这份代码还有挺多常数优化空间的(不过没必要)。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-10-17 00:50:58 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-10-17 01:04:49
 */
#include <bits/stdc++.h>
#define int unsigned long long

inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}

typedef std :: pair <int, int> pii;

bool hav[11];

std :: set <int> vis;

signed main() {
    int n = read(), x = read();
    int l = 1;
    for (int i = 1; i < n; ++i)
        l *= 10;

    std :: queue <pii> q;
    q.emplace(x, 0);

    while (!q.empty()) {
        int x = q.front().first, step = q.front().second;
        q.pop();
        
        if (x >= l) {
            printf("%llun", step);
            return 0;
        }
        
        std :: memset(hav, false, sizeof(hav));

        int t = x;
        while (t) {
            hav[t % 10] = true;
            t /= 10;
        }

        for (int i = 2; i <= 9; ++i) if (hav[i]) {
            if (vis.count(x * i))
                continue;
            q.emplace(x * i, step + 1);
            vis.insert(x * i);
        }
    }

    puts("-1");
    return 0;
}
程序员灯塔
转载请注明原文链接:CF1681D Required Length
喜欢 (0)