设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › 求构造一组 Hack 数据，指出错误之处最好
返回列表 发新帖
查看: 1110|回复: 10

[已解决]求构造一组 Hack 数据，指出错误之处最好

[复制链接]
zhangjinxuan
发表于 2023-7-18 22:05:34 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 zhangjinxuan 于 2023-7-18 22:06 编辑

题目：https://atcoder.jp/contests/abc137/tasks/abc137_e

友好翻译（来源洛谷）：

有一个有向图，点的编号为 1~N，有 M 条边，每条边为 a i →b i ，这条边上有 c i  枚硬币。

您从节点  1 开始移动，初始硬币为 0，你需要抵达 N，经过每条边耗时 1 分钟，每次经过一条边你都能收获硬币，无论重复多少次。

当您抵达 N 节点时，你可以结束游戏，也可以继续游戏，但是当你结束游戏的时候，你需要支付  T×P 枚硬币 （T表示时间），当您的硬币少于这个值时，你需要支付全部的硬币。

你的分数就是在付款后所拥有的硬币数量，如果可以确定能获得一个最大分数，你需要输出可以获得的分数的最大值。


主要思路：

DP，感觉很奇怪。

你先别急，让我先急，首先，因为答案会减去 T * P，也就是说，走一步就会减去 P 的金币，那就把所有边权都减 P。

然后，定义状态 f j,i 表示使用 j 步走到 i 节点的最大收益。

转移就是使用 j - 1 步到达所有可以到达 i 的边 + 这条边权。

特判没有走到的情况。

处理 -1 的情况就是，如果当前走了 n 以上的步仍然在更新 f[][n] 的值，就说明不存在最大值。



码量不多，下面是我的代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;

  4. int n, m, x, y;
  5. long long f[5001][2501], ans = -1ll << 60, p, z;
  6. struct Edge {
  7.         int to;
  8.         long long l;
  9. };
  10. vector<Edge> edges[2501];

  12. int main() {
  13.         scanf("%d%d%lld", &n, &m, &p);
  14.         while (m--) {
  15.                 scanf("%d%d%lld", &x, &y, &z);
  16.                 edges[y].push_back({x, z - p});
  17.         }
  18.         memset(f, 128, sizeof(f));
  19.         f[0][1] = 0;
  20.         for (int j = 1; j <= n + n; ++j) {
  21.                 for (int i = 1; i <= n; ++i) {
  22.                         for (auto k : edges[i]) {
  23.                                 if (f[j - 1][k.to] == f[0][0]) continue;
  24.                                 f[j][i] = max(f[j][i], f[j - 1][k.to] + k.l);
  25.                         }
  26.                         if (i == n && f[j][i] > ans) {
  27.                                 if (j >= n) {
  28.                                         puts("-1");
  29.                                         return 0;
  30.                                 }
  31.                                 ans = f[j][i];
  32.                         }
  33.                 }
  34.         }
  35.         printf("%lld\n", max(ans, 0ll));
  36.         return 0;
  37. }
复制代码


结果：https://atcoder.jp/contests/abc137/submissions/43729012

After Contest 全 WA，而且通过特殊方法，我发现 After Contest 全是 -1，是 -1 这一块没有处理好吗？
最佳答案
月排行榜 / 总排行榜
isdkz
2023-7-18 22:06:22
你的代码有一个小问题，主要在处理存在负环的情况上。由于负环可以无限制地提供硬币，因此在存在负环的情况下，应当输出 -1。

然而，你的代码只在 j（步数）达到或超过节点数（n）时判断是否存在负环，这并不正确。因为这样的话，可能会漏掉一些步数少于 n，但是已经形成了负环的情况。

你的负环判断应该在对每个 j 进行动态规划时都检查。如果在一个状态的硬币数量比前一个状态的硬币数量多，并且该状态所在的步数大于或等于 n，那么就可以判断存在负环。

你可以尝试将你的代码修改如下：
  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int n, m, x, y;
  5. long long f[5001][2501], ans = -1ll << 60, p, z;
  6. struct Edge {
  7.     int to;
  8.     long long l;
  9. };
  10. vector<Edge> edges[2501];
  12. int main() {
  13.     scanf("%d%d%lld", &n, &m, &p);
  14.     while (m--) {
  15.         scanf("%d%d%lld", &x, &y, &z);
  16.         edges[y].push_back({x, z - p});
  17.     }
  18.     memset(f, 128, sizeof(f));
  19.     f[0][1] = 0;
  20.     for (int j = 1; j <= n + n; ++j) {
  21.         for (int i = 1; i <= n; ++i) {
  22.             for (auto k : edges[ i]) {
  23.                 if (f[j - 1][k.to] == f[0][0]) continue;
  24.                 f[j][ i] = max(f[j][ i], f[j - 1][k.to] + k.l);
  25.             }
  26.             if (i == n) {
  27.                 if (j >= n && f[j][ i] > f[j - 1][ i]) {
  28.                     puts("-1");
  29.                     return 0;
  30.                 }
  31.                 ans = max(ans, f[j][ i]);
  32.             }
  33.         }
  34.     }
  35.     printf("%lld\n", max(ans, 0ll));
  36.     return 0;
  37. }
复制代码

这个修正的代码中，每个状态都将被检查是否存在负环，只要在步数 j 大于等于 n 的状态中，如果发现当前步的硬币数量比上一步的硬币数量多，就可以判断存在负环，并输出 -1。如果没有负环，将像原来的代码一样，输出最大的硬币数量。

希望这个答案可以帮助到你，如果你还有其他问题，欢迎继续提问。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

陶远航
发表于 2023-7-18 22:06:02 | 显示全部楼层
根据题目描述和代码分析，该问题是一个动态规划（DP）的最优路径问题。代码中使用了二维数组 f[j][i] 来表示使用 j 步走到 i 节点的最大收益。但在代码中，对 f 数组进行初始化时，使用了 memset(f, 128, sizeof(f))，将 f 数组的值都设置为一个很小的负数。

问题出现在这里，因为后续代码中将 f[j][i] 的值与其他数相加，并且使用 max 函数进行比较，如果初始值太小，可能会导致最终结果的比较出错。另外，题目中要求输出的是最大分数而非最小收益，所以初始值应设为一个很小的负无穷大。

要解决这个问题，你需要将代码中的初始化部分修改为 memset(f, -1, sizeof(f))，将 f 数组的初始值设为 -1，表示还没有计算。

修改后的代码如下所示：
  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int n, m, x, y;
  5. long long f[5001][2501], ans = -1ll << 60, p, z;
  7. struct Edge {
  8.     int to;
  9.     long long l;
  10. };
  12. vector<Edge> edges[2501];
  14. int main() {
  15.     scanf("%d%d%lld", &n, &m, &p);
  17.     while (m--) {
  18.         scanf("%d%d%lld", &x, &y, &z);
  19.         edges[y].push_back({x, z - p});
  20.     }
  22.     memset(f, -1, sizeof(f));
  23.     f[0][1] = 0;
  25.     for (int j = 1; j <= n + n; ++j) {
  26.         for (int i = 1; i <= n; ++i) {
  27.             for (auto k : edges[i]) {
  28.                 if (f[j - 1][k.to] == -1)
  29.                     continue;
  30.                 f[j][i] = max(f[j][i], f[j - 1][k.to] + k.l);
  31.             }
  32.             if (i == n && f[j][i] > ans) {
  33.                 if (j >= n) {
  34.                     puts("-1");
  35.                     return 0;
  36.                 }
  37.                 ans = f[j][i];
  38.             }
  39.         }
  40.     }
  42.     printf("%lld\n", max(ans, 0ll));
  43.     return 0;
  44. }
复制代码

通过这样的修改，可以解决初始值设置不当导致的错误。希望这能解决你的问题，如果还有其他疑问，请随时提问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

isdkz
发表于 2023-7-18 22:06:22 | 显示全部楼层    本楼为最佳答案   
你的代码有一个小问题，主要在处理存在负环的情况上。由于负环可以无限制地提供硬币，因此在存在负环的情况下，应当输出 -1。

然而，你的代码只在 j（步数）达到或超过节点数（n）时判断是否存在负环，这并不正确。因为这样的话，可能会漏掉一些步数少于 n，但是已经形成了负环的情况。

你的负环判断应该在对每个 j 进行动态规划时都检查。如果在一个状态的硬币数量比前一个状态的硬币数量多，并且该状态所在的步数大于或等于 n，那么就可以判断存在负环。

你可以尝试将你的代码修改如下：
  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int n, m, x, y;
  5. long long f[5001][2501], ans = -1ll << 60, p, z;
  6. struct Edge {
  7.     int to;
  8.     long long l;
  9. };
  10. vector<Edge> edges[2501];
  12. int main() {
  13.     scanf("%d%d%lld", &n, &m, &p);
  14.     while (m--) {
  15.         scanf("%d%d%lld", &x, &y, &z);
  16.         edges[y].push_back({x, z - p});
  17.     }
  18.     memset(f, 128, sizeof(f));
  19.     f[0][1] = 0;
  20.     for (int j = 1; j <= n + n; ++j) {
  21.         for (int i = 1; i <= n; ++i) {
  22.             for (auto k : edges[ i]) {
  23.                 if (f[j - 1][k.to] == f[0][0]) continue;
  24.                 f[j][ i] = max(f[j][ i], f[j - 1][k.to] + k.l);
  25.             }
  26.             if (i == n) {
  27.                 if (j >= n && f[j][ i] > f[j - 1][ i]) {
  28.                     puts("-1");
  29.                     return 0;
  30.                 }
  31.                 ans = max(ans, f[j][ i]);
  32.             }
  33.         }
  34.     }
  35.     printf("%lld\n", max(ans, 0ll));
  36.     return 0;
  37. }
复制代码

这个修正的代码中，每个状态都将被检查是否存在负环，只要在步数 j 大于等于 n 的状态中，如果发现当前步的硬币数量比上一步的硬币数量多，就可以判断存在负环，并输出 -1。如果没有负环，将像原来的代码一样，输出最大的硬币数量。

希望这个答案可以帮助到你，如果你还有其他问题，欢迎继续提问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-7-18 22:09:02 | 显示全部楼层
isdkz 发表于 2023-7-18 22:06
你的代码有一个小问题，主要在处理存在负环的情况上。由于负环可以无限制地提供硬币，因此在存在负环的情况 ...

很好，After Contest（子任务） 通过，但是 All 子任务 WA 了 14 个测试点。

https://atcoder.jp/contests/abc137/submissions/43729232

我虽然知道你是 ChatGPT，但还是希望能通过你来解决问题。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-7-18 22:10:02 | 显示全部楼层
陶远航 发表于 2023-7-18 22:06
根据题目描述和代码分析，该问题是一个动态规划（DP）的最优路径问题。代码中使用了二维数组 f[j] 来表示使 ...

WA的次数更多了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

sfqxx
发表于 2023-7-18 22:12:53 | 显示全部楼层
zhangjinxuan 发表于 2023-7-18 22:10
WA的次数更多了

让我的gpt试一试
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

sfqxx
发表于 2023-7-18 22:17:23 | 显示全部楼层
zhangjinxuan 发表于 2023-7-18 22:09
很好，After Contest（子任务） 通过，但是 All 子任务 WA 了 14 个测试点。

https://atcoder.jp/cont ...

  1. #include <bits/stdc++.h>
  2. using namespace std;

  4. int n, m, x, y;
  5. long long f[5001][2501], ans = -1ll << 60, p, z;
  6. struct Edge {
  7.     int to;
  8.     long long l;
  9. };
  10. vector<Edge> edges[2501];

  12. int main() {
  13.     scanf("%d%d%lld", &n, &m, &p);
  14.     while (m--) {
  15.         scanf("%d%d%lld", &x, &y, &z);
  16.         edges[y].push_back({x, z - p});
  17.     }
  18.     memset(f, 128, sizeof(f));
  19.     f[0][1] = 0;
  20.     for (int j = 1; j <= 2 * n; ++j) {
  21.         for (int i = 1; i <= n; ++i) {
  22.             for (auto k : edges[i]) {
  23.                 if (f[j - 1][k.to] == f[0][0]) continue;
  24.                 f[j][i] = max(f[j][i], f[j - 1][k.to] + k.l);
  25.             }
  26.             if (i == n && f[j][i] > ans) {
  27.                 if (j >= 2 * n) {
  28.                     if (f[j][i] > f[j - 1][i]) {
  29.                         puts("-1");
  30.                         return 0;
  31.                     }
  32.                 }
  33.                 ans = f[j][i];
  34.             }
  35.         }
  36.     }
  37.     printf("%lld\n", max(ans, 0ll));
  38.     return 0;
  39. }
复制代码


我的比他强，11个
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-7-18 22:18:44 | 显示全部楼层
sfqxx 发表于 2023-7-18 22:17
我的比他强，11个

寄
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

sfqxx
发表于 2023-7-18 22:20:00 | 显示全部楼层
zhangjinxuan 发表于 2023-7-18 22:18
寄

啥？
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-7-18 22:35:02 | 显示全部楼层
isdkz 发表于 2023-7-18 22:06
你的代码有一个小问题，主要在处理存在负环的情况上。由于负环可以无限制地提供硬币，因此在存在负环的情况 ...

GPT的思路是正确的，代码错了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

sfqxx
发表于 2023-7-18 23:05:31 | 显示全部楼层
zhangjinxuan 发表于 2023-7-18 22:35
GPT的思路是正确的，代码错了

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-10 11:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表