提供两组 Hack 数据 & 建议管理员考虑是否撤下部分题解
查看原帖
提供两组 Hack 数据 & 建议管理员考虑是否撤下部分题解
145355
wsyhb楼主2021/8/23 23:22

本题数据非常弱——据不少人所说,在本题数据中,起点 SS 到终点 TT 的最短路径至多只有一条。(即 FrenkiedeJong21 题解中提到的“不靠谱的过题办法”)

另外,在本题的限制下,起点 SS 到终点 TT 的最短路径的数量可以达到指数级别。然而,包括 Cyhlnj 和 GNAQ 的题解在内的不少代码却直接使用了 long long 存储最短路径的数量,这显然是错误的。正确的做法是像 FrenkiedeJong21 题解那样,将最短路径的数量对大质数取模。(在本题的限制下,几乎不可能构造出在大质数模意义下相等的情况)

以下的剪贴板链接包含两份 Hack 数据的 generator 及构造说明:

洛谷 P4061 Hack 数据

此处附上题解代码在 Hack 数据下的运行情况:

测试代码#1#2
Cyhlnj 题解中的两份代码WAWA
GNAQ 题解代码ACWA
FrenkiedeJong21 题解中“不靠谱的过题办法”WAWA
FrenkiedeJong21 题解中后两份代码ACAC

个人不清楚添加 Hack 数据会不会出现版权问题,若不会则请求管理员将这两组 Hack 数据加入该题数据。

另外,Cyhlnj 和 GNAQ 的题解请管理员决定是否撤下。

2021/8/23 23:22
加载中...