ZJOI2017 Day3 滚粗记

私のZJOI

Day3

2017-3-21 07:52:53

今天,考了人生当中的第一次省选(虽然只是普及组三等奖但仍然有幸能体会一下)。据胡老师说,这就是来体验一下被大神虐……真的是这样,听课听不懂,感觉那些大神什么都会的样子,自己连题目都看不懂。所以,金外的学子,如果你现在七年级,那就八年级拿一个普及组省一,初三去拿一个提高组省一吧!就跟伟大的朱江宁一样!(蛤蛤蛤虽然不太可能还是要野心是吧[误])但是这都不是重点,重点是:

int fuck( int your, int mother )

还有试题以及题解

只不过好像有人抄我博客的样子……这也是一种荣幸嘛……好不容易写篇博客然后被抄,也在一种层面上说明我写的博客写得好吧。【逃……

但还是认准我的博客正文链接哦Hash大法好

以下正文

ZJOI2017滚粗记

正如一个大佬说的:听课时候笑嘻嘻,考完省选mmp[迷]。但对于我这种普及组蒟蒻来说,连听课都听不懂啊。

6:20起床,还记得昨天12:00仍沉浸在《舞法天女》的神奇剧情中ZJOI2017 Day3 滚粗记

但是却蜜汁精神饱满。整理行李,下楼吃早饭,便退了房;回头望望,感觉三天的省选这么快就结束,心里或许是将要离别的悲伤,又或者是一些不甘。

坐车前往温州中学,考场被分配到五十一中。谜一样的温中上课铃,足足有一分半钟长,还挺好听???

于是进入考场,据前天的试机经验,为了度过五个小时的无聊时,我可以玩chrome的小恐龙、VB、python,实在不行还能玩cmd……本身太弱,不能做题,只能搞事情。

8:00,开始考试。首先看第一道题,大体的题意是一个图,加几条边 ,然后要使其成为一个仙人图。仙人图是一个连通无向简单图,没有重边存在,并且满足每一条边最多属于一个环。于是我就mmp了。 先跳到第二题。

第二题讲了一个神奇的人,树状数组写错了,在Add和Query中循环的方向搞反了,然后求什么概率???不管了,马上跳过。

第三道题,明显是一道数学题。一个最高次数为n的高次多项式,并且系数都为0和1,算出这个多项式的m次后展开的多项式,并且将系数 mod 2 ,又得到一个系数都为0和1的多项式。然后将这个多项式系数从最高次排序,于是变成了一个由0和1组成的字符串,这个字符串的长度是n * m - 1。再给出一个长度为K的字符串t,问求出的字符串中有几个子串和t一样。

看到这道题目,感觉比前面两道题更好下手,于是就先写了一个暴力。暴力求m次,暴力求子串,后来发现可以用快速幂优化,于是就用了一个快速幂。但是子串仍然只能用O(nm)的复杂度来求,快速幂的复杂度也只能为O(n^2 m^2 logm)所以这个复杂度根本无法恭维,只能过一个点。对于后面m <= 1e18 这种神奇的数据,就只能滚粗了。

回过头来看第一道题,发现有两个点是保证数据是一条链。根据找规律发现,有n个节点时会有 2^( n - 2 )种方案数。其实都不用快速幂,就可以求出来。因为n <= 500000。于是水掉30分,就没有再考虑过第二题。

最后一个小时实在没事情干,于是就玩玩小恐龙,玩玩Python,也就那样。最后交了试题,才猛然醒悟,第一次省选就这样混过去了,不禁还是有一些感慨的——蒟蒻被大神就是这么虐的。

下午还有一个颁奖典礼,看到一个穿着礼服的腿粗的温中妹纸,一些穿着低胸装的温中妹纸——给我们(蛤蛤蛤)表演合唱,还有一个和男生跳双人舞的身材不错的温中妹纸。咳咳,这都不是重点,重点是普及组和提高组本次联赛一等奖的人都去领奖了。他们不知道,台下有一个蒟蒻,不停地在心里骂道:“老子不内存不炸就好了!fuck!!!!!”

于是就这么滚粗了,在回去的列车上写下这篇博客,由此纪念一下初中的最后一场OI比赛吧。

上一篇:一位IT牛人的十年经验之谈


下一篇:CTSC 2017 滚粗记