CCF 201903

最后一次的认证,事前准备了差不多一个月,都觉得没什么问题了,考的时候还做出了四道题,觉得三百分是稳的。然后一查成绩,居然比第一次基本没怎么准备还低(第一次 270),不甘心,又无奈。

于是等到网上出了题后,把当时提交的题重新做一遍,提交一遍,重新看看问题在哪,写一写题解。也不是想要证明什么,只是觉得努力不应该被白费? 代码链接 点此

小中大

题目为有序序列中找最大值,最小值和中位数,并按大到小的顺序输出。

非常简单,最大最小值直接按索引取值即可,中位数则需要根据个数的奇偶性判断要不要取均值。

然而,第一道题的输入样例就给错了,样例 2 的输入并不是有序的,这就引发了我一个非常关键的问题:最值怎么取?是根据他说的原本有序取两侧,还是取实际的最值?我当时想的是前者,这就又引发出了另一个问题,中位数可能比最大值大或者比最小值小,所以三者又做了额外的排序,耽误了一定的时间。

最后直到我第二题都差不多做完,才通知说题目有误,改了样例。而我上面的代码一样符合它的思路,只是做多了额外功夫,测试了一下新样例就完事了。

最后这题拿了 100 分

二十四点

题目为根据输入表达式判断结果是否等于 24。

对于有着 eval 的 Python 的选手来说,非常简单,处理一下输入调用eval即可。考试时注意到除法为整除,而 Python3 已经将整除变为//所以先用 replace 替换一下除号即可。

然而这道题我拿了 40 分,考后提交发现运行错误。细看题,发现题目中给出的乘号居然是小写字母x来表示。为什么会发现不了?当时因为第一题题目本身有问题,耽误了一点时间,所以做得比较快,而且最关键的是,**这一次全部题面都用了图片,包括输入样例!!!**我们只能一个个手敲输入样例,因为是手敲样例的缘故,自己就直接先入为主当成*号了,发现不了看错题的情况,血崩。

发现问题后对乘法做一个处理,将 x 替换成*,问题解决,100 分。

损坏的 RAID5

麻烦模拟题

待续

消息传递接口

一个比较典型的死锁问题,感觉可以用信号量去解决。

当时跳了这道题没做,现在估计也不会去做。

317 号子任务

多源点最短路径问题

题目要求给出图中每一个点到 k 个特定类型的点的最短路径和。

对于图论题我一直都是抱着能拿分就拿分的态度,超时的话一般都不考虑,于是直接采用最为暴力直接的方法——弗洛伊德算法,直接求出多源点最短路径,复杂度为$O(n^3)$,求出后直接找每个点到特定点的距离,排序后取前 k 个求和即可。

考试时,这道题我得了 0 分,现在重新提交,显示运行超时。运行超时我并不感到意外,但是超时到连第一个样例都过不了???重新看数据规模,发现这里第一档的数据(30%的数据),点的规模就已经到了 500,重新翻了翻以往的图论题,别的单源最短路径或者最小生成树的问题第一档数据规模一般都是$10$, 今年因为放到了第五题,强行通过数据规模提高难度,也是醉了。但是即使如此,现在的模拟提交因为时间只有 1 秒超时,在考试的时候时间上限是 10s,10s 也不能跑完第一档的数据?很奇怪。

换用了 C++重新写了一个 C++版本的弗洛伊德算法,还是超时 0 分。上网搜了一下,相关题解只有 一个,而且也是用弗洛伊德算法。将其直接复制提交,提示错误,这次不超时了,但是时间也接近界限了。一样的方法为什么它可以不超时?我一直贴近它的代码修改我的,可是我的代码还是一直超时,莫得办法。看它的代码,没有考虑重边和自环。修改后还是错误。暂时只能放弃。