刷题日记：1道状压DP，又遇到精度问题，拜读jiang神代码！

2024-02-21 13:20:46 浏览数 (2)

大家好！我是小码匠。

早上打完USACO 2024铜组比赛，下午本来想写会作业，又被老码农抓住，继续温习状压DP。

看似一道普及/提高−, 搞了快1小时45分钟。

这道题：[ARC166B] Make Multiples

往往折磨得你死去活来的题目都是好题目

老码农原话。总之，他就喜欢收拾小孩。

题目信息

  • 地址：https://www.luogu.com.cn/problem/AT_arc166_b
  • 题解：https://www.luogu.com.cn/problem/solution/AT_arc166_b

解题过程

看到这题时，最初的思路是贪心，但无奈码力弱，不知道怎么打，就看了洛谷题解区第一位大佬的题解。

看完题解，醍醐灌顶。知道怎么搞了，最后AC的代码基本和第一位大佬一般不二，这不是重点。

重点是解题过程。

先看jiang神的代码
代码语言：javascript复制
#include <bits/stdc  .h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;
    
    i64 a, b, c;
    std::cin >> a >> b >> c;
    
    std::vector<i64> A(N);
    for (int i = 0; i < N; i  ) {
        std::cin >> A[i];
    }
    
    i64 ans = 1E18;
    
    auto get = [&](std::vector<i64> x) {
        if (x.size() > N) {
            return;
        }
        int k = x.size();
        std::vector<bool> vis(N);
        std::vector<std::vector<int>> t;
        for (int i = 0; i < k; i  ) {
            std::vector<int> p(N);
            std::iota(p.begin(), p.end(), 0);
            std::nth_element(p.begin(), p.begin()   k, p.end(),
                [&](int u, int v) {
                    return (x[i] - A[u] % x[i]) % x[i] < (x[i] - A[v] % x[i]) % x[i];
                });
            p.resize(k);
            t.push_back(p);
        }
        
        auto dfs = [&](auto self, int i, i64 sum) -> void {
            if (i == k) {
                ans = std::min(ans, sum);
                return;
            }
            for (auto j : t[i]) {
                if (!vis[j]) {
                    vis[j] = true;
                    self(self, i   1, sum   (x[i] - A[j] % x[i]) % x[i]);
                    vis[j] = false;
                }
            }
        };
        dfs(dfs, 0, 0);
    };
    
    get({a, b, c});
    get({a, std::lcm(b, c)});
    get({b, std::lcm(a, c)});
    get({c, std::lcm(a, b)});
    get({std::lcm(std::lcm(a, b), c)});
    
    std::cout << ans << "n";
    
    return 0;
}

仰慕大神，其实jiang神的代码我也没太看明白，才疏学浅，路漫漫其修远兮，继续努力。

本地OK，提交就挂

太郁闷了，下面这版代码本地测试4个样例都过了，提交到AtCoder上，第4个样例都没过，见鬼了。

  • 样例：3AC 1WA
  • 44AC 38WA
代码语言：javascript复制
#include <bits/stdc  .h>

using namespace std;
const int maxn = 2e5   5;
long long dp[maxn][2][2][2];
struct node {
    long long a, b, c, ab, bc, ac, abc;
} v[maxn];

long long lcm(long long x, long long y) {
    return x * y / (__gcd(x, y));
}

void best_coder() {
    int n, A, B, C;
    cin >> n >> A >> B >> C;
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n;   i) {
        long long x;
        cin >> x;
        --x;
        v[i].a = A - (x % A) - 1;
        v[i].b = B - (x % B) - 1;
        v[i].c = C - (x % C) - 1;
        v[i].ab = lcm(A, B) - (x % lcm(A, B)) - 1;
        v[i].bc = lcm(C, B) - (x % lcm(C, B)) - 1;
        v[i].ac = lcm(A, C) - (x % lcm(A, C)) - 1;
        v[i].abc = lcm(C, lcm(A, B)) - (x % lcm(C, lcm(A, B))) - 1;
    }
    dp[0][0][0][0] = 0;
    for (int i = 1; i <= n;   i) {
        dp[i][0][0][0] = dp[i - 1][0][0][0];
        dp[i][1][0][0] = min(dp[i - 1][0][0][0]   v[i].a, dp[i - 1][1][0][0]);
        dp[i][0][1][0] = min(dp[i - 1][0][0][0]   v[i].b, dp[i - 1][0][1][0]);
        dp[i][0][0][1] = min(dp[i - 1][0][0][0]   v[i].c, dp[i - 1][0][0][1]);
        dp[i][1][1][0] = min({dp[i - 1][1][1][0], dp[i - 1][0][0][0]   v[i].ab,
                              dp[i - 1][1][0][0]   v[i].b, dp[i - 1][0][1][0]   v[i].a});
        dp[i][1][0][1] = min({dp[i - 1][1][0][1], dp[i - 1][0][0][0]   v[i].ac,
                              dp[i - 1][1][0][0]   v[i].c, dp[i - 1][0][0][1]   v[i].a});
        dp[i][0][1][1] = min({dp[i - 1][0][1][1], dp[i - 1][0][0][0]   v[i].bc,
                                                     dp[i - 1][0][0][1]   v[i].b, dp[i - 1][0][1][0]   v[i].c});
        dp[i][1][1][1] = min({dp[i - 1][1][1][1], dp[i - 1][0][0][0]   v[i].abc, dp[i - 1][1][1][0]   v[i].c,
                              dp[i - 1][1][0][1]   v[i].b, dp[i - 1][0][1][1]   v[i].a, dp[i - 1][0][0][1]   v[i].ab, dp[i - 1][0][1][0]   v[i].ac,
                                     dp[i - 1][1][0][0]   v[i].bc});
    }
    cout << dp[n][1][1][1];
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}
什么问题？

瞪屏幕几分钟后，突然又开窍了，莫非是精度问题。

原本第15行

代码语言：javascript复制
    int n, A, B, C;

改成

代码语言：javascript复制
    int n;
    long long A, B, C;

继续提交AC了。

还原现场

a、b、c：

1 <= a, b, c <=10^{6}

所以我定义变量

代码语言：javascript复制
int n, A, B, C;
A_i

:

1 <= A_i <=10^{18}

所以我定义结构体时用的long long

代码语言：javascript复制
struct node {
    long long a, b, c, ab, bc, ac, abc;
} v[MAX_NUM];

但下面有运算逻辑，估计问题应该是出在这里，出现精度丢失，atcoder的评测机和我本地window的C 环境编译器是不同的，所以提交时候直接挂了。

代码语言：javascript复制
    for (int i = 1; i <= n;   i) {
        long long x;
        cin >> x;
        --x;
        v[i].a = A - (x % A) - 1;
        v[i].b = B - (x % B) - 1;
        v[i].c = C - (x % C) - 1;
        v[i].ab = lcm(A, B) - (x % lcm(A, B)) - 1;
        v[i].bc = lcm(C, B) - (x % lcm(C, B)) - 1;
        v[i].ac = lcm(A, C) - (x % lcm(A, C)) - 1;
        v[i].abc = lcm(C, lcm(A, B)) - (x % lcm(C, lcm(A, B))) - 1;
    }
完整代码
代码语言：javascript复制
// 题目: [ARC166B] Make Multiples
// 链接: https://www.luogu.com.cn/problem/AT_arc166_b
// 难度: 普及/提高−
// 题解:
// - 洛谷: https://www.luogu.com.cn/problem/solution/AT_arc166_b
// - atcoder: https://atcoder.jp/contests/arc166/submissions/46377913
// -          https://atcoder.jp/contests/arc166/submissions/46378139
#include <bits/stdc  .h>

using namespace std;
const int MAX_NUM = 2e5   5;
long long dp[MAX_NUM][2][2][2];
struct node {
    long long a, b, c, ab, bc, ac, abc;
} v[MAX_NUM];

long long lcm(long long x, long long y) {
    return x * y / (__gcd(x, y));
}

void best_coder() {
    int n;
    long long A, B, C;
    cin >> n >> A >> B >> C;
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n;   i) {
        long long x;
        cin >> x;
        --x;
        v[i].a = A - (x % A) - 1;
        v[i].b = B - (x % B) - 1;
        v[i].c = C - (x % C) - 1;
        v[i].ab = lcm(A, B) - (x % lcm(A, B)) - 1;
        v[i].bc = lcm(C, B) - (x % lcm(C, B)) - 1;
        v[i].ac = lcm(A, C) - (x % lcm(A, C)) - 1;
        v[i].abc = lcm(C, lcm(A, B)) - (x % lcm(C, lcm(A, B))) - 1;
    }
    dp[0][0][0][0] = 0;
    for (int i = 1; i <= n;   i) {
        dp[i][0][0][0] = dp[i - 1][0][0][0];
        dp[i][1][0][0] = min(dp[i - 1][0][0][0]   v[i].a, dp[i - 1][1][0][0]);
        dp[i][0][1][0] = min(dp[i - 1][0][0][0]   v[i].b, dp[i - 1][0][1][0]);
        dp[i][0][0][1] = min(dp[i - 1][0][0][0]   v[i].c, dp[i - 1][0][0][1]);
        dp[i][1][1][0] = min({dp[i - 1][1][1][0], dp[i - 1][0][0][0]   v[i].ab,
                              dp[i - 1][1][0][0]   v[i].b, dp[i - 1][0][1][0]   v[i].a});
        dp[i][1][0][1] = min({dp[i - 1][1][0][1], dp[i - 1][0][0][0]   v[i].ac,
                              dp[i - 1][1][0][0]   v[i].c, dp[i - 1][0][0][1]   v[i].a});
        dp[i][0][1][1] = min({dp[i - 1][0][1][1], dp[i - 1][0][0][0]   v[i].bc,
                              dp[i - 1][0][0][1]   v[i].b, dp[i - 1][0][1][0]   v[i].c});
        dp[i][1][1][1] = min({dp[i - 1][1][1][1], dp[i - 1][0][0][0]   v[i].abc, dp[i - 1][1][1][0]   v[i].c,
                              dp[i - 1][1][0][1]   v[i].b, dp[i - 1][0][1][1]   v[i].a, dp[i - 1][0][0][1]   v[i].ab,
                              dp[i - 1][0][1][0]   v[i].ac,
                              dp[i - 1][1][0][0]   v[i].bc});
    }
    cout << dp[n][1][1][1];
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

代码风格

jiang神和tourist神的码风是我最喜欢的风格。

我也有点代码洁癖，洛谷上很多题解写的很好，但代码风格都不是我喜欢的。

看起来很难受。

今天就到这里，继续加油。。。

min std 效率 dp int

0 人点赞