• 【hack】浅浅说说自己构造hack的一些逻辑~

    怎么说呢，相信很多考过竞赛的同学都会在平时的练习/考试中遭遇过100分但没有AC的情况，结果一看评测结果：subtask的数据点没过！

    这时候就是遇到hack数据了，如果被这类数据卡住，说明你的代码可能还存在一些潜在的BUG，需要你细心分析。

    在这里猫猫就以自己的一道题目来简要说说hack数据的构造有什么思路：

    【本题来源：比特山】

    16: 猫猫和狐狸在迷宫里的赛跑~ 较难

    作者/来源：白风（题目提供）

    题目背景

    （天洛是狐狸、白风是猫猫）

    为了整治一下天洛这只懒狐狸不愿意动的习惯，猫猫不由分说的把天洛扔到了一个迷宫里：“嗷呜！放我回去！！”

    面对着天洛的哀嚎，白风笑着晃了晃手中的杯子：“看看这是什么w~”

    “这是……暴打柠檬茶？！”看着朝自己扑过来的屑狐狸，猫猫只是轻轻一躲便是闪了过去：“想喝吧？w来追我呀~追到我就给你w”

    “嗷呜！~”

    题目描述

    现在狐狸和猫猫身处一个迷宫之中，记性不好的猫只能记得眼前的分支中最短的一条路径，比如对于节点A、B、C，若从A到B的距离短于从A到C的距离，猫就会选择从A节点往B节点移动。

    狐狸有地图，但是猫猫没有地图。

    狐狸拿到地图之后，可以选择路线穿过一个个房间，最终堵住猫猫的去路，拿到他爪中的柠檬茶。

    现在请你帮天洛规划路线。

    接矩阵第1行第2列的意思是：从输入顺序的第一个节点（很显然就是1）到输入顺序的第二个节点（就是2）的距离】

    【比如输入#1中邻接矩阵第1行第2列的意思是：从输入顺序的第一个节点(很显然就是1)到输入顺序的第二个节点(就是2)的距离为1】

    1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0

    上面的图对应的样子如下图所示：

    若1为起点，4为终点，那么红色就是狐狸追的路径，绿色是猫猫逃跑的路径

    红色路径比绿色路径短，就成功抓到了。

    测试图1.png

    而你要实现的功能就是：找出所有可以到达出口的路线中总体最短的路线，在猫猫到达出口之前，抢先一步到达出口，以此来堵住猫猫的去路。

    注意，若同时到达，由于猫猫比较灵活，此时狐狸还是追不上猫猫的，这种情况下也为无解

    加油！狐狸能不能喝上柠檬茶就看你了！

    交互格式说明

    输入

    第一行：数字N，代表着节点个数

    第二行：有N个数字，代表着节点编号

    接下来：是一个NxN的邻接矩阵，用空格分隔，其中无法到达的用-1表示

    最后1行有2个数字，分别代表起点编号和终点编号

    输出

    如果存在解：

    第一行为一个整数，代表最短路径距离

    接下来几行为行动顺序，从当前节点开始，依次输出路线中各个节点的编号，1行1个

    若不存在解【即猫猫一定能比狐狸先一步到达出口】，请输出-1

    交互格式样例

    样例输入#1

    5
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 4

    样例输出#1

    3
1
3
4

    样例输入#2

    5
1 2 3 4 5
0 1 2 -1 -1
1 0 3 -1 2
2 3 0 1 -1
-1 -1 1 0 1
-1 2 -1 1 0
1 5

    样例输出#2

    -1

    提示

    数据保证，最短路径只有一个

    同时，猫猫为了让狐狸多跑几圈，特意设计了几个环，允许狐狸在一个房间里兜圈子

    注意，此题中各个节点之间的距离一定为非负整数

    如果存在相同距离的点，那么猫猫和狐狸都会选择未探索节点中节点编号最小的那条路线，比如如果有两条距离相同的路线：

    路线A：1→2→5→7→9→…

    路线B：1→2→3→7→12→…

    则最终选择为路线B

    若存在猫猫无法到达终点的情况，输出依然按照有解情况进行

    同理，若存在狐狸无法到达终点的情况，输出依然按照无解情况进行

    纵使迷宫千奇百怪，真相永远只有一个……

     猫猫の解读

    认真读一下题目，基本上思路其实就有了。

    猫猫选择的很明显是一种“贪心”的思想，也就是所谓的贪心算法。

    而狐狸则是选择了最短路径，我们可以使用Dijkstra最短路径算法得出答案。

    是不是感觉这一题很简单？但是……小心细节w

    猫猫在一番折腾后，一共提交了5组数据点：

    第一组（正常数据，用于测试你的程序是否能按要求完成任务）：

    race1.in

    5
1 4 2 6 7
0 1 1 -1 3
1 0 1 1 1
1 1 0 2 -1
-1 1 2 0 1
3 1 -1 1 0
1 7

    race1.out

    2
1
4
7

    平平无奇，并没有什么特别的。

    第二组（正常数据，但是相对节点数较多，作为大数据测试）：

    race2.in

    race2.out

    1
1
100

    这个数据相对大一点，但其实也问题不大【只要你的程序没写太拉也能过】

    不过，下面几组数据可就没这么简单了w~

    第三组（hack数据，出现自环情况，可以在同一个节点兜圈子，如果使用贪心算法可能出现最后程序无法结束导致TLE）：

    race3.in

    12
1 2 3 4 5 6 7 8 9 10 11 12
1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
3 1 1 2 3 -1 -1 -1 -1 -1 -1 -1
-1 1 1 1 -1 95 17 -1 -1 -1 -1 -1
-1 2 1 1 2 3 4 5 -1 -1 -1 -1
-1 3 -1 2 1 -1 2 99 -1 -1 -1 -1
-1 -1 95 3 -1 1 -1 -1 96 15 -1 -1
-1 -1 17 4 2 -1 1 1 21 5 43 -1
-1 -1 -1 5 99 -1 1 1 -1 27 99 -1
-1 -1 -1 -1 -1 96 21 -1 1 1 -1 -1
-1 -1 -1 -1 -1 15 5 27 1 1 1 3
-1 -1 -1 -1 -1 -1 43 99 -1 1 1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 1
1 12

    race3.out

    16
1
2
5
7
10
12

    这组数据就是检查你读题到底有没有读完了，如果没有读完没看到最后的提示……哼哼，这个点可能分就没了。

    不过相信应该大多数人不至于在这个点上被卡住……（bushi）

    第四组（hack数据，在编号映射和数据大小上分别针对int和long long的存储范围进行hack，如果没有注意到题目中没有给出数据范围这个点很容易被忽视）

    race4.in

    3
1 3 5
2147483648 2147483649 2147483650
2147483647 4200000000 4100000000
4611686018427387904 4611686018427387905 2147483648
1 5

    race4.out

    2147483650
1
5

    这组数据说实话属实有点***钻，主要是谁会想到还会对long long这种类型进行hack呢……

    【当然比赛场上一般不会选择这样hack，毕竟比赛的时候谁都不想写高精度……xwx】

    第五组（hack数据，对编号映射针对long long进行hack，而且给出的是单节点图，很容易被人忽视）

    race5.in

    1
9223372036854775807
18446744073709551617
9223372036854775807 9223372036854775807

    race5.out

    -1

    说实话，这组数据真的很容易被忽视，因为他整张图只有一个节点……

    所以说细节决定成败，如果真的没注意的话很容易被hack掉……

    总结

    读到这里有人就想问了，那你是怎么想到这种hack数据呢？

    emm……首先，在假设你对题目所用的算法了解的话，你需要做的就是理解题目中隐藏的信息。

    就比如本题中题目中有一句：“注意，若同时到达，由于猫猫比较灵活，此时狐狸还是追不上猫猫的，这种情况下也为无解”

    这句话作用是什么？

    这不是明摆着告诉你有数据点能卡这个嘛……

    说白了，所谓的hack数据只是为了保证你的代码具有能真正解决问题的能力，而不是会被一些特殊数据给hack掉。

    所谓的“hack数据”，何尝不是对你题目理解能力的考察吗？

    只要题目读透了，不读错题目【有时候猫猫会想当然结果最后爆0】

    区区hack数据能奈我何？

    【这里还有一些有意思的聊天记录.jpg】

    ⌬白风-Cryflmind⌬ 2023/7/27 10:40:57
    说起来上面那个图论题我用map映射一下节点编号会不会方便处理一些？

    Mathematica 2023/7/27 10:41:52
    我用数组映射的

    ⌬白风-Cryflmind⌬ 2023/7/27 10:42:14
    owo桶喵？

    Mathematica 2023/7/27 10:42:23

     

    Mathematica 2023/7/27 10:42:50
    话说编号可以hack我

    ⌬白风-Cryflmind⌬ 2023/7/27 10:43:12
    w编号写大点这样写就给你写RE了


    Mathematica 2023/7/27 10:43:20
    哈哈哈哈哈对

    Mathematica 2023/7/27 10:44:14
    可以加强数据

    ⌬白风-Cryflmind⌬ 2023/7/27 10:44:23
    是的w

    ⌬白风-Cryflmind⌬ 2023/7/27 10:45:08
    回来洛谷原题我再扔个Hack上去

    ⌬白风-Cryflmind⌬ 2023/7/27 10:46:30
    幸好这个题不在codeforces上.jpg

    Mathematica 2023/7/27 10:47:05
    笑死

     后记

    顺带一提，其实这个题目里面还能提出新的hack数据，我提交的数据集其实并不是完美的。

    所以，或许你可以试试自己构造一组hack？

    给你个提示吧，我前面给的所有图都是个连通图w~

    多动手，多思考，自然就水到渠成了喵~

     

  • 相关阅读:
    CentOS 7 下升级 OpenSSL + OpenSSH【在线 yum 安装依赖】
    shell脚本之数组
    ubuntu20.04 安装cudnn
    Open Inventor 10.12 Crack
    电脑入门：路由器访问控制列表基础知识
    小小Python编程故事-小小的成绩单（1）
    Oracle查询最大连接数和当前连接数
    uniapp地图导航
    一文详解 requests 库中 json 参数和 data 参数的用法
    (SCA)正弦余弦算法SCA: A Sine Cosine Algorithm（代码可复制粘贴）
  • 原文地址：https://www.cnblogs.com/cryflmind/p/17589937.html