GDKOI 2018

来玩 Mini Metro

Posted by Ghastlcon on January 28, 2018
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 GDKOI 2018

$\text{GDKOI }2018$

再次感觉跟去年的画风完全不同。

资瓷左老师讲课
上去提了下大样例的问题并不知道明年有没有

想看 $\text{Solution}$ 的直接翻 $\text{Catalog}$ 。
(然而事实上并没有写)

本篇就是划水记,随便记点东西。或许等到我真的 $\text{AFO}$ 之后来看,说不定会找到零碎的回忆吧。

$\text{Day }-1$

考完文化课美滋滋

初中只剩下最后半年了呢。

$\text{Day }0$

逃课成功,上午的课结束之后直接跑真刺激。

还是考 $\text{NOIp}$ 的那个地方,见到 $3$ 个月前的景色莫名伤感,或许是回忆起了那点不甘。

由于某些奇奇怪怪的原因跟 $\text{SMSY}$ 的隔开了

晚上依旧浪,或许已经成为日常了吧。外卖被 $\text{GP}$ 拦截了(于是 $\text{JU}$ 和 $\text{Dic}$ 成功吃掉所有)。

$\text{Day }1$

入考场前和众多 $\text{Dalao}$ 相视一笑表示友好问候。

$\text{P1}$ 是什么鬼啊,这题面怎么这么长啊,怎么要我模拟地铁啊,这也太毒瘤了吧,我要写 $400$ 行你们都别拦着我。

$\text{P2}$ 很明显的 $\text{AC}$ 自动机啊(然而我只能从数据范围看出来是而并不会 $\text{AC}$ 机),好像暴力 $\text{KMP}$ 下就有 $40\%$ 了啊,等等我好像不会 $\text{KMP}$ 怎么办啊。

$\text{P3}$ 又是什么鬼啊,这奥妙重重的数据范围(坐标大小)和时间限制估计就是分块$/\text{Bitset}/\text{FFT}$ 的某种了吧。好像大暴力又有 $40\%$ 啊。

$\text{P4}$ 完全不会啊。暴力好像没分啊。


感觉 $\text{P1}$ 要写很久,于是先去拿走 $\text{P2}$ 的 $40\%$ 。

不会 $\text{KMP}$?没事我会 $\text{Suffix Array}$,做个匹配多简单

然后 $O(N^2)$ 暴力把 $\text{P3}$ 的 $40\%$ 拿走了。

这样我就有 $80$ 分了啊。


$2$ 分最短路,玩 $\text{P1}$ 共 $2\texttt{h}$ 。

$\text{STL}$ 套 $\text{STL}$ 套 $\text{STL}$ 感觉很棒棒啊,估计要被卡常。

这种题也没办法对拍,于是手搞数据直到比赛结束。

预计 $100+40+40+0=180$ 。


讲课感觉就是组题人全程口胡……

$\text{P1}$ 居然可以倒着最短路,并没有想到。

$\text{P2}$ 果不其然 $\text{AC}$ 机。

$\text{P3}$ 果不其然 $\text{FFT}$ 。

(然而以上两个我都不会)

$10+40+40+0=90$?$\text{P1}$ 成功写炸。

首次在正式比赛里面想到了却写错呢。

希望这不要是码力不足的预兆才好。


$\text{SMSY}$ 的都被拉回去搞综能了。   (事实上他们被骗了)

想浪起来发现没有什么方法可以啊。

只能发出 $\text{Day 2 Bless all.}$ 的祝福了吧。

$\text{Day }1.5$

讲课日。

日常听不懂左老师在讲什么怎么办啊。

果然 $\text{DP}$ 还是太菜了啊,貌似 $\text{LGJ}$ 都不太重视我们这届的 $\text{DP}$(所以说现在初一的都在恶补 $\text{DP}$,比赛里全是 $\text{DP}$ 题)。

处于十分尴尬的状况,$\text{DP}$ 题,看到弃。

怎么办啊。

于是打开了 $\text{Mini Metro}$,又想起的昨天的题目呢。

$\text{Day }2$

日常送命。

$\text{P1}$ 要求数字和格子匹配,有条件限制,每个匹配还有价值?费用流无误。

看下数据范围。

咸鱼失去梦想

不过我还是可以拿 $60\%$ 的对吧。

$\text{P2}$ 再次奥妙重重,感觉应该跟 $\text{GDOI 2017}$ 相同,估计是乱搞题。

(开场前打的 $\text{Dinic}$ 删掉)开始打费用流,很快就过了样例。

要不要打表找规律啊。

$1\texttt{h}$ 过去后我成功找出了 $k=0$ 时的规律。但我还是 $60\%$ 怎么办啊。

先去把 $\text{P3}$ 的 $20\%$ 大暴力拿走。

$\text{P2}$ 随便写个最短路搞搞?倒着往后退回去看起来很靠谱啊。(然而并没有想到 $2$ 分)

又是瞎搞之后过样例。手搞几个小数据没问题丢旁边去,继续打 $\text{P1}$ 的表。

然后直到结束我都没搞出 $\text{P1}$ 。虽然感觉 $\text{P4}$ 好像有点可做但是最后还是没有管。


忽然发现 $\text{P2}$ 可以 $2$ 分。

然后听说 $\text{P1}$ 只要将 $2$ 维转成 $1$ 维就可以做了。其实这已经是 $\text{NOIp}$ 的常用套路了,但是不知道为什么还是忘记了呢。

决定把套路表放上来。

没听讲课就滚回去了。

$\text{Memories}$

没有什么可回忆的吧。

毕竟这次也没有做过多的准备。划水选手来观光而已。

就这样吧。

$\text{Solution}$

留坑。

还没拿到题面。