GDOI2016：4.28~5.1：东道主之战，第一次GDOI之旅

随着最后一份成绩单发下，我的第一次GDOI就这样草草收场了。今天我在嗟叹之余来总结一下这几天以来的日程。

4.29：

由于是东道主我们并不用乘车，直接在自己的学校考就好了，实话说这个时间有点蛋疼，因为刚考完期中= =虐的我要吐了，还要马上来这么刺激的事，承受不能啊。

别校的小伙伴大伙伴五点半左右到场，我回家，没打算怎么去准备。

4.30 Day 1

早上7点出发前往学校，买了两根士力架，领取参赛证（一袋东西），由于不知道发生了啥，8:20开考。

解压密码意思大概是题目有毒2333 = =b 卖的一手好萌啊

打开PDF，心潮澎湃啊。

第一题，初中生数学题←这就是题目，我没记错的话题目大概是这样的：

输入k p0 n0

求当n = [n0 - pk] 时，n * (p - p0)的最大值。[x]为不超过x的整数（暂且理解为floor吧）。

有两个输出的，我只记得第一个输出了，第二个输出的话就是求分别设定两个p值p1, p2时，n * (p - p0)的最大值。

其中 n1 = [n0 - pk], maxp1 = n * (p - p0), 然后 n2 = [n0 - pk], maxp2 = (n - n1) * (p - p0);

貌似 k p0 n0 都是实数？忘了。

这个题目是有部分分的。也就是说，他要求输出两个答案，对一个，就可以拿到该测试点的一半分。

我的做法（对于第一个答案）：

既然要求 n = [n0 - pk], 那么对于pk可以组成的最大值，肯定是p = no / k。

那么我用一个for循环，i = 0 to n0，然后根据 p = i / k，计算记录最大值后输出不就行了吗？

数据范围 n <= 10^7 我这个是O(n)做法了，明显。

其实当时并不知道可不可以A..然后正解的话，待会说到讲题会讲到。

第二题，没错是可爱的字符串题。嗯嗯...

给定两个串S, T和k个区间，这K个区间对应在T串上的位置，表示在T串的这个位置，串的顺序可以任意改变，求：改变顺序后，S与T的LCS.区间可以利用多次。

懒（不）得（会）打暴力，因为第一个测试数据是 k = 1, n <= 10.用暴力水分的话时间复杂度是O(n! * n * m)的...哭哦

这题没做.

Yeah.

第三题，密室解谜题：

猜解密码。有K个槽，数字范围是0 ~ n？忘了，然后填进去后有三种提示：

你填对了

你没填对但真正的密码包含这个数字

你真的没填对

输入n, k，求期望最小步数。密码各位都不相同。

数学期望是啥？该买数论看看了...

还是不做。

第四题，%#￥%#&%￥%￥#%&……&题：

日哦题目描述太复杂了，我来简化一下：

输入一个图。

输入每个图的点的初始值。

然后，有三种操作：

给 x -> y 的最短路径经过的点加上一个值；

（嗯..在说第二个操作前我先来说说初始值的作用吧:初始值其实就是每个点每个单位时间“生成”一样东西的数目，然后如果A到B存在一条边，那么你从A直接走到B，就会浪费一单位的时间，注意，只有当你走到那个点时，这个点才会开始并一直每单位时间生成一定量的东西，直到你走完整条路为止）求从 x -> y 的最短路径经过时，能生成的“产品”数量；

恢复到第N次修改时的状态。如果N = 0则变为初始值。

我靠，我是直接跳到了这题打算用最短路径做这题的。

然后因为我SPFA不熟，我选择了dijkstra...................

还要把dis[]用了bool储存..白白调试浪费30分钟

写出来了大概是(n^3)做法...

历史版本？直接开数组储存了...

当时估计是能过两个点的...

12:20 第一场比赛结束。

放饭，讨论。

15:30 开始讲题。

坑爹的事情开始了。

第一题正解：

数型结合，利用几何分析。

我的第一个答案思路和讲题人差不多..分析出来时全场小伙伴都惊呆了，好吧只是我惊呆了。

第一个答案，O(n)做法，无须多说。

第二个答案！！！！！！！！！

O(1)做法！！！！！！！！！！

貌似是直接把第一个答案乘上某个数，输出！（好像是3/2）

卧槽！！！！！！！！！！！！

牛逼了...

第二题正解：

10%的数据肯定是暴力啦。

正解是用DP，递推式略长...没看懂，好吧。

注意区间合并。

第三题正解：

DP!

四维数组DP！我靠逆元是什么鬼？？？

坚定了我要买数论的决心。

递推式两行，不说了。

第四题正解：

暴力做法20%啦。

正解是动态树做法。树链剖分 + 可持久化 + 强制在线....

日了，根本不会动态树...

持续懵逼中...

17:30 发下成绩单

第一题 50 分...果然...

第四题：

超内存！！！！！

沃日！！！！！

3000*50000*4/1024/1024 = 572.20 > 512 靠！！

做人不能太贪心啊！！！！

爆零！！！！

总分50，实话说对于我这种渣渣...我还是有点开心的，毕竟第一次参加这么难得比赛...

Day1 总结：

内存！

算法熟练程度！（然而第二天，我马上就吃了这个亏了...）

5.1 Day2

五一劳模节。七点十分起床了..

校牌不见了，只好在机房找到了借书证顶替一下...

没买巧克力...

8:00 开考，解压密码：不要帅(甩？)锅~~

第一题：

给出一个有向图，允许当 A->B，B->C时，直接连通A->C，代价修改为某个值，修改操作为lim个。

我的思路：

我！！艹！！

又是最短路！！！！！！！为什么昨晚没复习SPFA啊！！！！！

晕哦，只好dijkstra了，还是用邻接矩阵存的图，哭哦

只暴力计算lim = 1的情况，其余要么贪心，要么输出-1.

嗯。为水题而奋斗。

第二题：

给出一个含有起点终点的图，输出一条哈密顿回路的路径。数据保证有解。n<10.

图的元素：起点终点，障碍，桥（分桥上桥下，=这样的，在桥上不可以上下走，在桥下不可以左右走）

我的思路：

DFS啊..赤裸裸的搜索题..

于是三四题都不看了。

第一次在比赛写搜索题，写了两个小时。

样例过了，手写数据也过了。

但是！！！

最后15分钟，我写出了错误数据（桥的标记及其处理没判断好，不知道是走过了桥上，还是走过了桥下！！！）！！

沃日！！！！！

最后15分钟，无力，无力回天了。

祈祷着能过两个点。

第三题：没看

第四题：

给出一个只包含0和1的图和一个值len，你可以把任意的0换成1，但完成所有修改后条件如下;

所有的0必须连通；

所有的1必须连通；

得出1连通块的周长（与0或边界接触的）至少有一半是原1的周长；

用无限个这个1的连通块可以不重叠无空隙地覆盖满无限大的平面；

不记得了。

没有6.

要输出的就是周长=给定的len时，把0转换成1的最小次数。

我的做法：

printf("NO");

嗯。很暴力对吧？

待会你就知道了。

12:20 第二场考试结束，楼下因为跳闸加时20min（可怜的孩子...）

15:00 讲题。

第一题：