数据结构上机实践课程（2018年秋）题解

jxtxzzw edited 6 年前

如果有其他题目需要题解，请在评论区留言。

检索表

医疗调度系统

对于一个给定的队列$1,2,\cdots , n$，在默认情况下，每次都是第一个元素出队且加入到队尾，即依次变成$2,3,\cdots,n,1$，之后是$3,4,\cdots, n-1,n,1,2$……

但是当遇到E 命令时，需要将指定的元素（无论他处在队列的什么位置）强行移动到队首，例如对于上述$3,4,\cdots, n-1,n,1,2$情况下，如果要求E 5，那么元素$5$移动到队首，队列变成$5,3,4,6,\cdots, n-1,n,1,2$，下次要求出队的时候，应该是$5$出队并且移动到队尾。

写一个程序实现这个过程，并针对输入数据模拟输出出队的每一个元素。

需要注意的是E命令只是强行移动到队首，不需要输出，只有N命令需要输出。

可能会有连续的E命令操作多个人到队首，或者连续E同一个人（甚至就已经是队首的人）。

具体的实现上，当遇到N命令时，输出队首元素。

int x = queue.peek();
queue.pop();
queue.add(x);

当遇到E指令时，将给定元素移动到队首。

int index_of_element = queue.find(x);
queue.delete(index_of_element);
queue.addToFront(x);

由于每个人的编号是唯一的，所以可以很容易地找到需要提前的人现在在什么位置，然后将它提前到队首。

如果是用链表实现的，找到这个人以后，直接修改前后元素的指针即可。

x->prev->next = x->next
x->next->prev = x->prev
head->next = x
x->prev = head

如果是用数组实现的，找到这个人以后，将他移动到队首，一种方法是移动数组剩下所有的元素，另一种方法是用$0$来表示这种情况，当遍历到数组元素值为$0$时，跳过即可。

while(que[pos] == 0)
    pos++;

for(int j = BEGIN; j < END;j++)
    if(que[j] == X)
        que[j] = 0;

不少同学在第5组测试数据错误，注意这组数据只有$2$个人，在一系列E和N操作后，不少同学把$2$号居民弄丢了，只剩下了$1$号居民。

银行排队夹塞

理解题意以后，发现和 $1010$ 其实是类似的，也是一个可以让某些元素提前的队列。

这里模拟的是一个银行排队的队列，正常情况下，每次队首的元素出队，办理业务以后这个元素就没有了。

但是，后面的 $B$ 可以找到在他前面的、是自己朋友的人 $A$ 帮忙办事情，那么，当 $A$ 办理完自己的业务的时候，会顺便把 $B$ 的事情一起办完。

这时候，可以认为， $B$ 从队列后面某个位置，插队到了 $A$ 的后面， $A+B$ 办理业务的时间是他们两个人各自办理业务的时间的和，办理业务后两个人同时消失。

那么，处理的逻辑就是，每次队首元素出队，表示队首这个人已经办理完毕，接下来从队列后面某个位置找一个人，把他提前到队首。

这个人，默认情况下应该是当前队首出队前，队列中的第二个元素，由于此人已经办理业务（元素出队），所以原来队列中的第二个元素自动成为队首，是下一个办理业务的人。

但是现在考虑“夹塞”，那么这个人就应该是当前队首出队这个人的朋友，他要在队列中找一个到达时间不晚于自己离开时间的自己的朋友，把他提前到自己的后面，如果找不到这样一个朋友，就按顺序找自己后面这个人。

不断循环，直到队列为空。

核心代码以及需要注意的地方如下：

for(i = 0 to n) { // 寻找一个到达时间不晚于自己办理结束时间的朋友
    if(visited[i]) continue; // 已经办理过的人
    if(arrive[i] > last) break; // 后面的人都是自己办理完业务才会到达的
    if(friend) { // 例如HashMap一一对应，或者数组、映射、count等都可以
        // 入队，标记为已处理;
        // 更新数据
        sum += last - arrive[i];
        last += process[i];
        break;
    }
}
// 如果没找到朋友，则取下一个人
sum += max(0, last - arrive[i]); // 等待时间可能为 0（窗口空闲一段时间）

GPS 数据处理

因为本题是实际生活中的情况，所有数据都是完全真实的，所以不可避免的会有各种可能的情况（例如 GPS 传输时候少了两个 ,，例如不同的设备终端在时间的处理上对秒的精度不同……）。

所以 it is your responsibility to 处理输入，而不是由出题人事先准备好完美是数据就等着你去推导数学公式去做，这与算法竞赛的数据不同。

那么对于本题来说，我特意提醒了 3 次，请再次注意：每个字段的大小（长度）不一，并不能认为字段的大小就如上述例句一样。

对于部分同学提出的意见，要求题干中基于全局的字段3和5的描述应换为『整数部分.小数部分』就不会理解错了，我给出如下答复。

我确实在出题之初就考虑过这个问题，是不是要给一组样例提醒同学们，但是后来经过查阅资料，发现确实按照无线电通讯标准GPRMC的要求，是hhmmss.sss，只是部分终端在实现的时候并没有严格按照这个标准。由此，我并没有修改题面。

但是本题的数据来源是 100% 真实的，所有的数据都是真实的 GPS 传输的数据，所以，你可能会遇到hhmmss.ss的情况。

同时，有些字段未必会在所有的终端中被统计，或者，就算本地统计了，也未必会发送到 GPS 数据上，因此，你会遇到很多字段为空，即两个,中间并不是如预期那样有信息，而是会出现,,,,的可能。

同时，有可能，有些数据传着传着就丢了。

那么，这道题应该怎么做呢？

所以，首先你应该判断这是不是一条$GPRMC，即判断字符串是不是以$GPRMC开头。

然后，你要去看看字段的个数是不是满足要求，即,的个数是不是满足要求。

取出各个字段唯一的方法，是用,分隔，而不能用加上一个长度来获取。

对于正确取出各个字段之后的结果，你要去看是不是已定位的，即是不是A，然后计算校验值。

for (int i = 2; i <= st.lastIndexOf('*') - 1; i++)
    tmp = tmp ^ st.charAt(i);

检查校验值是不是正确。

if (Integer.parseInt(st.substring(st.lastIndexOf('*') + 1), 16) == (tmp % 65536))

如果以上步骤都成立，取出表示时间的那个字段，然后换算成北京时间。

System.out.printf("%02d:%s:%s\n", (Integer.parseInt(ans.substring(0, 2)) + 8) % 24, ans.substring(2, 4), ans.substring(4, 6));

更多信息可以阅读讨论区

网址的替换

因为本题是实际生活中的情况，与 GPS 那题类似，所有数据都是完全真实的，所以不可避免的会有各种可能的情况（例如 GPS 传输时候少了两个,，例如用户输入网址的时候懒得前后加空格……）。

所以 it is your responsibility to 处理输入，而不是由出题人事先准备好完美是数据就等着你去推导数学公式去做，这与算法竞赛的数据不同。

本题题面描述已经非常清楚了，只要按照题目要求一步步做，提取出难度，然后按照格式输出就可以了。

如果是完全正常的数据，那么，只要取出难度字段和题目编号，然后，按照给定网址的格式，格式化输出对应的题目编号和难度，之后照抄即可。

但是，往往会有人不按照标准格式写文档。

（现在知道为什么文档格式一定要严格按照规范了吧，你会给很多人带来成倍成倍的工作量）

对于更多特殊情况的处理，请阅读讨论区。

Comments

Kevin_K

6 年，1 月前

炸表*2

回复 2 0

爱吃烤肉的派大星

3 年，9 月前

1010医疗调度系统样例4完整版能发一下吗为什么我总是runtimeerror

回复 2 0

LUSTRE

6 年，2 月前

[已删除]

jxtxzzw

6 年，2 月前

这种情况一定是你的本地环境的问题，如果你输出答案正确，那只是凑巧正确，因为本题只要求输出yes或者no。

OJ环境一定是没问题的。

看你的代码

for(; pin<n; pin++)
{

    if(stack[top-1]==in[pin])
    {
        pop();
        pin++;
    }
    else
        break;
}

例如，4321，你会先做if，然后pin++，然后到了for循环的自增，pin++

这里的pin++加了 $2$ 次显然是错误的

可以输出看看

printf("current pin = %d\n", pin);
if(pin==n)
    printf("yes\n");
else
    printf("no\n");

$6$ 不等于 $4$， 于是输出的是 no。

请再次检查你的本机环境，因为这个pin值你是可以用手动推导的，画张图，只有四列火车，还是很容易发现问题的。

回复 1 0

John_Snow

6 年，1 月前

求问助教1049三元组稀疏矩阵相加的魔鬼test2数据是啥

回复 0 0

jxtxzzw

6 年，1 月前

7881 + 7454 = 11557 ????
加法都错了估计程序有大问题，发给你们助教去检查吧

回复 0 0

John_Snow

6 年，1 月前

那最后一组数据是不是输出三元组的数量很多啊，10^10都满的话也太大了

回复 0 0

jxtxzzw

6 年，1 月前

很多。
100000 100000 1000000

回复 1 0

John_Snow

5 年，11 月前

请问1080朋友圈的case3咋整，开的邻接矩阵不到30000就溢出。

回复 0 0

deerbean

6 年，3 月前

发生啥事……

回复 0 0

LUSTRE

6 年前

[已删除]

jxtxzzw

6 年前

这题已经给过题解了。

回复 0 0

Kevin_K

6 年，3 月前

表炸了。emm~

回复 0 0

John_Snow

5 年，12 月前

[已删除]

jxtxzzw

5 年，12 月前

没有要注意的地方，大规模数据。如有疑问问助教。

回复 0 0

ultmaster

6 年，5 月前

置顶提示。

回复 0 0

LUSTRE

6 年前

求助！！1068第一组数据

回复 0 0

jxtxzzw

5 年，12 月前

大规模随机数据,注意可能多行.

回复 0 0

LUSTRE

5 年，12 月前

有注意到多行的问题 还是没有通过第一组 设想了很多情况但还是找不到问题 求助！！

回复 0 0

jxtxzzw

5 年，12 月前

问助教

回复 0 0

LUSTRE

5 年，12 月前

好的！

回复 0 0

Zoey

6 年前

请助教大大帮忙看一下1066 第33个数据点是为什么出错了呢23333

回复 0 0

jxtxzzw

6 年前

大规模随机数据，这组数据不是特殊数据，不予公开。如有疑问请携代码联系助教。

回复 0 0

Zoey

6 年前

哦好的。谢谢

回复 0 0

LUSTRE

6 年，2 月前

[已删除]

jxtxzzw

6 年，2 月前

大规模完全随机的数据，不是特殊情况

回复 0 0

CatFlowers

6 年，2 月前

请问做过1054的最后一组数据有什么玄机吗，心塞ing，最后一组过不去，呜呜呜

回复 0 0

jxtxzzw

6 年，2 月前

没有特殊情况。该题考察的是归并排序。需要注意得分相同的考生按照考号顺序递增输出。你的代码在处理得分相同的考生时输出顺序有误。

回复 0 0

Saitama

6 年，2 月前

建议修改1040测试数据或时限，说是要用kmp，直接用朴素也a得过去。

回复 0 0

jxtxzzw

6 年，2 月前

感谢你的建议，我会处理的。本题数据用的就是朴素方法那组数据。但不是要求输出失败链接值了，朴素不能输出失败链接值吧？这相当于只能用kmp了。

回复 0 0

10175102204

6 年，3 月前

请问1005第12组测试数据究竟有什么玄机
过不去啊

回复 0 0

Kevin_K

6 年，3 月前

末尾的空格……吧？

回复 2 0

10175102204

6 年，3 月前

的确是末尾的空格....

回复 0 0

jxtxzzw

6 年，3 月前

现在首尾的空格和换行都不会测了。
之前应该是数据本身的问题，已修复，1005稍后会全部重测。

回复 0 0

Phenom

5 年，11 月前

六度空间这个题的数据好松啊。。说的N=10^4结果floyd就能过了

回复 0 0

jxtxzzw

5 年，11 月前

可能是测评机的性能太强了

回复 0 0

6324upup

6 年前

求问1058二维数组排序的输出格式有什么特别么，我自己测试的都没问题但是第一个测试点就过不去。

回复 0 0

jxtxzzw

6 年前

没有特别的格式。你就是排序错了。

回复 0 0

6324upup

6 年，1 月前

请问下1030字串排序的第六组数据除了长度是满的还有什么特别的么，一直过不去啊。。

回复 0 0

jxtxzzw

6 年，1 月前

没有什么特别。
你输出了奇怪的东西a12345678qwertyuioplkjhg

回复 0 0

10175102138

6 年，1 月前

请问助教，1017题我的代码在取高校数为1时是错误的，怎么却AC了

回复 0 0

jxtxzzw

6 年，1 月前

有可能数据里面根本就没有高校数为1的情况。如有疑问请找助教。

回复 0 0

6324upup

5 年，11 月前

请问下助教1091公村路路通test4一直过不去，是哪里出错了啊，是连通性判断错了还是路径和哪边算错了。

回复 0 0

jxtxzzw

5 年，11 月前

output
3717
answer
3716
checker’s comment
wrong answer: line 1 differ - expected: ‘3716’, found: ‘3717’

回复 0 0

LUSTRE

6 年前

求助1063树的双亲存储 之前test12之后的数据超时了
于是换了种方法
但是现在test2过不了 请问下test2的数据

回复 0 0

jxtxzzw

6 年前

你自己比原来的那个代码啊，那个不是都过了test12了吗

回复 0 0

LUSTRE

6 年前

主要两个代码思路完全不一样的 新的这个第二组是runtime error 估计是有什么特殊情况

回复 0 0

jxtxzzw

6 年前

并不是什么特殊情况呀，要是特殊情况早就给你提示了，它就是完全随机的数据 –b
964 -1 932 652 637 729 269 316 794 190 881 674 ……
这是前面若干，后面还有很多，贴不出来的，也没有什么规律……

回复 0 0

LUSTRE

6 年前

好滴！我再看看

回复 0 0

徐梓翔Justinn

5 年，11 月前

求助学长，可以帮忙看下我的1102第三组数据错在哪里了么

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

徐梓翔Justinn

5 年，11 月前

可以麻烦学长提供一下1102的第三组数据嘛，测试总是对的，自己查错难度稍稍有点大

回复 0 0

jxtxzzw

5 年，11 月前

加我QQ或者发我邮箱，数据太大没法贴在评论这里

回复 0 0

jxtxzzw

5 年，11 月前

输出少了，你只是输出了6->11，这只是其中一个，还有其他的关系

回复 0 0

徐梓翔Justinn

5 年，11 月前

好的 谢谢 我再看一下

回复 0 0

6324upup

6 年，1 月前

[已删除]

6324upup

6 年，1 月前

好的终于过了。多谢提醒

回复 0 0

jxtxzzw

6 年，1 月前

字符串处理的地方错了，你仔细想想，\0是应该在max_length吗？还是？

回复 0 0

LUSTRE

6 年前

求助助教！！1059第五组数据 显示runtime error
（我知道这道题给过解析 sorry 但是卡在瓶颈找不到bug 需要帮助）

回复 0 0

jxtxzzw

6 年前

古诗碎片数
1 1

例如数据
1 1
12345

这类特殊情况需要考虑

回复 0 0

LUSTRE

6 年前

好的 谢谢谢谢 搞定了

回复 0 0

LUSTRE

6 年前

求助！1066目录树第四组数据

回复 0 0

jxtxzzw

6 年前

非特殊数据，可考虑所有文件同级的情况，如有疑问请问助教。

回复 0 0

LUSTRE

6 年前

1066修改了之后现在又卡在第26组数据了。。
还有一个问题 是1053选择排序构造 提示里说3607可以买判决书 但是现在买不了了
谢谢！！

回复 0 0

jxtxzzw

6 年前

应该一直可以买……

回复 0 0

LUSTRE

6 年前

就是我点那个购买完整测评报告，它会跳转到一个访问受限的页面。

回复 0 0

jxtxzzw

6 年前

请向管理老师反馈

0 0

CatFlowers

6 年，2 月前

请问1010的第二组测试数据是什么啊…

回复 0 0

jxtxzzw

6 年，2 月前

不提供完整的数据。第二组数据是人数非常多（例如100000000）但是操作数非常少的情况，请自行检查。

回复 0 0

妈耶

6 年，2 月前

1001第八组数据总是过不了

回复 0 0

jxtxzzw

6 年，2 月前

cmd==1&&cnt<10000

你的cnt<10000是想干嘛？操作数的值为$1$就直接往里插入。
线性表又没有最大长度，$n$指的是线性表初始大小。
对于第8组数据，完全可以长度为10000的线性表，先执行5000个插入，再执行删除。

回复 0 0

jxtxzzw

6 年，2 月前

第8组数据是，长度为10000的线性表，一上来先执行若干个插入操作，随后再进行删除。

回复 0 0

Kevin_K

6 年，2 月前

你好!我想请教一下我1078#构造Huffman树第一个点为什么会没有通过验证函数.
当然考虑到输出顺序的原因,我没有先把树建好,而是输出与树分开操作,所以我写了一个dfs函数来验证自己的树,但依然不知道问题所在.
上文中提到的输出验证结果和验证程序全都在我最近一发提交的注解里.
我想问一下我哪里弄错了,谢谢!(注:程序中怕撞变量名(现在想想好像不可能撞)加了前缀,前缀可以直接统一删了)

回复 0 0

jxtxzzw

6 年，2 月前

已修复。原 Special Judge 在处理 “当这是非叶子节点你可以自行定义（不关心非叶子节点的值）” 时欠考虑了。抱歉浪费了你不少的时间。我的锅。（当然你可以让助教背锅，他没验题……）

回复 0 0

LUSTRE

6 年，2 月前

[已删除]

jxtxzzw

6 年，2 月前

1018铁路调度，第一组数据即样例数据

回复 0 0

jxtxzzw

6 年，2 月前

4 4321 显然输出结果应该是 yes ，但是你输出的是 no。你测试出来对的？你本地有问题吧。

回复 0 0

10175102224

6 年前

请问助教1057最后一个测试点，测不出出了什么问题

回复 0 0

jxtxzzw

6 年前

不是特殊情况只是一组大规模随机数据

回复 0 0

宅男不十分H

6 年，2 月前

我就是不太懂那个等待时间到底是怎么算的
就是帮朋友做事情的这个人的等待时间是他的事务处理时间与他所有能帮到的朋友的时间之和吗？
被帮的朋友的事情一旦完成之后就立即离开队伍了是吗？

回复 0 0

jxtxzzw

6 年，2 月前

办理完业务你还留着干嘛......完成之后就离开队伍。
对于”等待”时间，你的理解出现严重偏差，生活经验严重不足。
甲到了，办理30分钟业务，则等待0分钟，办理30分钟。乙第10分钟到，则他需要等待甲办理完他才能办理，所以等待时间是20分钟。
我不认为这个上面存在理解上的歧义，不知道你到底哪里没想明白？

回复 0 0

宅男不十分H

6 年，2 月前

还有就是办理事物所花费的时间算不算自己的等待时间呢？

回复 0 0

酱饼

4 年，12 月前

请问1086 最短路径的test12是哪里出错了

回复 0 0

jxtxzzw

4 年，12 月前

点A到点B的直接相连的路径不止一条，且长度不一定相等

回复 0 0

酱饼

4 年，12 月前

多谢！原来一直以为只要在输入时更新最小权值就行，原来计算路径数也要考虑到这个条件。。

回复 0 0

宅男不十分H

6 年，2 月前

请问助教这个银行排队加塞不是可以一个人帮多个朋友办事情吗？

回复 0 0

jxtxzzw

6 年，2 月前

可以，一个人可以帮所有朋友办事，需要注意朋友必须在他（他们）办理完业务离开银行之前到达银行。

回复 0 0

酱饼

5 年前

[已删除]

jxtxzzw

5 年前

大规模随机数据，应该没包含什么特殊的边界值

回复 0 0

徐梓翔Justinn

5 年，11 月前

求助助教学长 1087最短路径那一题的最后一组数据一直过不了 可以麻烦你帮我看一下问题出在哪里吗

回复 0 0

jxtxzzw

5 年，11 月前

最短路径条数错了

回复 0 0

徐梓翔Justinn

5 年，11 月前

吼的 谢谢你

回复 0 0

10175102204

5 年，11 月前

求解1094 test4卡住了.. 请帮忙看一下 谢谢~

回复 0 0

jxtxzzw

5 年，11 月前

与楼上6324upup提出的问题一致，以后请先阅读评论区再发问题。

output
3717
answer
3716
checker's comment
wrong answer: line 1 differ - expected: '3716', found: '3717'

回复 0 0