前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >刷题日记：1道状压DP，又遇到精度问题，拜读jiang神代码！

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

作者头像
小码匠
发布于 2024-02-21 13:20:46
1100
发布于 2024-02-21 13:20:46
举报
文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好！我是小码匠。

早上打完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神的码风是我最喜欢的风格。

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

看起来很难受。

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

本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2024-02-17，如有侵权请联系?cloudcommunity@tencent.com 删除
min
std
效率
dp
int

本文分享自 小码匠和老码农 微信公众号，前往查看

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

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

min
std
效率
dp
int
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 题目信息
  • 解题过程
    • 先看jiang神的代码
      • 本地OK，提交就挂
        • 什么问题？
          • 还原现场
            • 完整代码
            • 代码风格
            领券

            腾讯云开发者

            扫码关注腾讯云开发者

            扫码关注腾讯云开发者

            领取腾讯云代金券

            热门产品

            热门推荐

            更多推荐

            Copyright ? 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有?

            深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059?深公网安备号 44030502008569

            腾讯云计算（北京）有限责任公司 京ICP证150476号 | ?京ICP备11018762号 | 京公网安备号11010802020287

            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

            Copyright ? 2013 - 2024 Tencent Cloud.

            All Rights Reserved. 腾讯云 版权所有

            登录 后参与评论
            http://www.vxiaotou.com