nocriz的博客

苔花如米小,也学牡丹开。

JSOI一轮/12省联考游记

游记

现在是星期三的夜里11:00,我终于有空闲下来写这篇早就应当写的游记了。我的确有许多所想,但囿于现状,恐怕不能够将这些想法都写在博客中。在我退役之后(很可能就在不远的将来,尽管),我将认真地写一篇更加发自真心的文章,从而为我信息学竞赛曲折的学习路程做一个小结。

省选是信息学竞赛中的一个重要节点,对我也当然一样如此。在一年之前参加省选时,我在现场也一样地有着期盼。那当然是一种无谓的希望,或许在未来看现在的我也是如此,可其实即使是无谓的希望,也能够带给人力量,也能使人进步——或许这种希望也并不完全是无谓的。

这篇文章本是一篇游记,对于要在开头扯这些没用的,我深表歉意。那么正文由此开始,既然暂时还没有退役,那么就让我在这里罗列一下我省选的经历吧。

Day -2

众所周知,我是一名摸鱼选手。事实也如此,

我于中午到达了上海。在那里我去参观了中国当代艺术博物馆,欣赏了两个展出,其中一个是画家陈福善的作品展,感觉在七旬仍能进行艺术风格的探索,的确是相当特别了。当代艺术博物馆是由电厂改建的,仍保留着烟囱,从窗户向外看便是长江。

直到下午,我坐上火车抵达了苏州,摸了一晚上的鱼,可能看了两道题。

Day -1

我上午打了一场模拟赛,感觉状态还行,但是其实只会乱搞。下午花时间尝试学习了动态dp,然而似乎并不能够瞬间学会。

晚上看了ICPC World Finals的直播,一个小时之后开始认真看决定做题,在本机有板子的条件下花了20min就连想带写A出了G题,好像还是场外一血。其实真的就是靠之前的板子瞎改的……

晚上后来感觉不大行了做不动题了,就看了一波直播。后来就睡觉了。

Day 0

我乘坐高铁到达了常州,打印了四页模版:其中两页是多项式的模版,两页是广义SAM的模版。

下午试机,试机前就看到各种强校的选手在谈笑风生,我只好在桌子上尝试打了一下昨天的B题,还没打完就进去试机了。我坐在AprilGrimoire大佬左边,花了四十分钟才把NTT打出来,感觉虚的很。和大佬对拍过了,大佬怒喷桌子太矮,其实的确如此,桌子不仅矮,而且宽度只够放键盘的,如果想要打草稿第一步就是要先把键盘靠着显示器摆放,非常不方便。

现场的桌子和NTT板子,我们使用这组数据对拍

晚上抱着写写题的心态做了一个[NOI2015]品酒大会,这是我第二次使用SAM解题,但最终还是结合模版A掉了这道题。做完题我就睡觉了,并没有想太多。

Day 1

江苏省的省选果然是同别处不同的——一进大厅,便是四个候选队大佬在谈笑风声。江苏的A队共五人,去掉一个女选手必占的名额便只剩下了四个,如果谁进了A队便注定有候选队大佬没进……

我携带着一个保温杯,装着热茶便上了考场。看题,T1好像很清新的样子,可是我一看就啥思路也没有。T2是最吸引我的,我一看封面,“string”就觉得不错——昨天晚上我才刚做一道字符串。我看完了T2,稍微想了想感觉还不错,就看了T3。T3其实也是我喜欢的类型,之前我也见过一道类似的题目,只是那道题测试点更多,我害怕这道题同样需要费太大劲,就决定放到最后再写。

我开始肝T2了,我毫不费力就想出来了80分,想出之后我当场以为这是满分做法稳了,就开始写。这是我第三次尝试用SAM做题,于是我各种地方忘记初始化或没写(例如mlen[np] = mlen[fa]+1),再如(fa = np),两个小时才写好。

但是两个小时的时候我并不能够过第一个样例。这其实是因为第一个样例不满足特殊的性质,但我当时不知道我打的是一个80分的做法,于是通过手画调试了半个小时,终于证明了我的算法作为80分算法的正确性和另20分得不到的事实。我觉得另20分似乎有点繁,于是做了一个计划——先做1hT1,再拿1h肝T3.

我花了五分钟想出来T1两个log的做法,但意识到显然是过不去的。然后我口胡了一个

    \[O(n \log_{\log n} n \log_2 10^9)\]

的做法,感觉说不定能卡过去,就开始写了。写了30行之后,我意识到自己根本卡不过去,就写了个暴力跑去肝T3了,这时还有70分钟。

T3我前3个点花掉了不少时间,尤其是以为第三个点开long long 就能解决问题更是浪费时间。直到终于发现要类似高精度的东西,非常费时。

未知模数的点,我写了python求max,盲猜1145141,然后猜对了。

然后我看出了质数,之后很快也看出了mu。我想了想,想出来了正解的打表算法,但是我没有足够的时间了,就写了个埃筛,配上打表拿了质数的18分。

后来Day1共拿了177分,拿个rk 18。好像T1,T2很多人都同时A掉了,而且T1相当简单,我成了T1没A掉的人里面分数最高的,有点难过。不过参加省选要有学习的心态,这次好就好在打出了T2的SAM,这样我就也是会用SAM的选手了,这倒是一个好的收获。张好风由于T2输出了调试信息爆0了,好像有点不稳。我真替他感到遗憾,其实他Day2又翻到不知道比我高多少了。

当时我还挺高兴,觉得不错,觉得Day 2 或许还行。于是我做了做Google Codejam的题,签完到就睡觉了,或许还看了一下多项式的模版——Day1既然考了我打印的其中一个,Day2未免就要考第二个。

Day 2

许多记忆我已经失去,但我知道这一天我的压力其实还是不大的。

我开场看T1,想出来了O(n^2)的状态设计方法,就丢一边看T2了。T2好像很良心,随便打就75分,我就尝试想了想正解(失败了),然后打了个75分。我又去看T3,好像非常不可做的样子。再加上好像大家都在搞T1,于是我也去搞T1了。

T1后来只会m^3了,然而出题人不给活路,除了m^4就是m^2,m = 1000我要跑10秒,我就GG了,只能拿70分。后来去做T3,随便拿了点部分分就是24分。

于是这场比赛就拿了169,坏就坏在前两题一题不会,打了三题暴力。比赛一结束,我和zhf大佬一交流,他前两题都随便A掉了,我就很紧张。事实证明是zhf太强了而不是大家均分200+😄。最后拿了个Rk8,感觉好像还不错。

结果综合排下来发现我还是十好几名,只有把三分之一去掉才勉强在线之内。然而二轮省选我大概也不大行了,于是很可能就退役了。水平还是低,感觉在这轮省选中A出两题甚至三题其实都不是难事,也不要求什么高级的算法。

希望下次加油,只求稳定发挥,会的题现场做出来,不会的题赛后补出来,总之学到就好。

写完游记已经是第二天,没有时间再次一一看了,我便草草的发出来,等以后再加修饰吧!


评论

《“JSOI一轮/12省联考游记”》 有 1 条评论

  1. nocriz 的头像
    nocriz

    你好牛逼啊,我是你的小迷妹

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注