我来了,我出锅了,我走了——NOIp2018游记

Day (不想算)

将RP耗尽在了初赛QwQ

Day 0

教练说这天Openday,随便打游戏,于是上午随手把最大流、费用流、树剖三个听说可能会考的板子给敲了一遍于是就去跟同学颓了一天的LOL

Day 1

来到学车中学,开考前随便跟同学奶了奶算法

照例解压,深吸一口气,打开题目。

看到T1,第一眼:卧槽这是什么玩意儿

第二眼:完了这是D1T1吗我要爆零了

第三眼(仔细一看):这题好像有点眼熟?

第四眼:这不是我们模拟赛做过的某题的弱化版吗?

然而由于我太蒻了,我不会模拟赛的那道神仙题,于是找起了规律

我觉得可能跟差分有关系,于是就试着把数组的差分数据加起来,结果发现除了样例什么都过不了

于是我试着把最后一位加了上去,然后发现所有数据都大了一倍

于是我把答案除了个2,不管怎么证明,就去看T2了

看完题目,我开始大胆猜测:答案肯定是原先给出的集合的子集

然后xjb推了一番,采用显然法,得出一个数可以去掉当且仅当它可以被比他小的数表示出来

于是打了个好像是背包的奇怪DP,乱搞了一通,水过了大样例,就去看T3了

瞅了一眼T3,想到了一个O(n2)O(n^2)的做法,结果正准备开始写的时候发现把题目重新看了一遍,卧槽,这路径不能重合的啊

之后,花了大概半个小时左右敲了m=1m = 1的找直径和一条链的二分答案

估计得分 100 + 100 + 40 = 240 pts

Day 2

保持心态,一路上只是奶奶算法而已

正当大家奶的正欢时,一道响亮的声音划过长空

杨英豪:“我奶今年T1动态仙人掌,T2树链剖分套主席树套珂朵莉树,T3动态DP!”

大家也只是笑笑,没当真

进考场

开考,照例解压,看T1

看了看,先花了10分钟把树的情况贪心敲完了

接下来开始想基环树

于是我画了一草稿纸的基环树

终于发现其实只要枚举断那条边其实就可以了

看T2,一看,n这么小,m这么大,理所当然想到对每一列进行状压,于是画了30min敲了一个状压

然后一看,卧槽,除了n=2n = 2的数据啥都过不了

接下来头铁手玩杠了一波n=m=3n = m = 3的样例,结果发现状压就是过不了的

(手玩 + 找状压错误原因花费40min)

结果发现在n3n \geq 3,会出现这种毒瘤情况:

恩,我没办法解决,敲暴力……

这暴力还真是难敲……

敲完暴力,顺手打了几个表,离考试结束只有一个小时多一些了

然后开始写T3,一看

世界沉默了。。。

这TM不就是动态DP吗!!!

(心中开始疯狂诅咒杨英豪)

手速爆发写了个O(n2)O(n^2)树状DP

瞪了一眼数据约定,写了个只有一个深度\leq 300且其中一个询问为1 1的从询问点向根更新的O(深度)O(\texttt{深度})算法,打文件,交卷。

估计得分 100 + 50 + 52 = 202 pts

Day 3

开始讨论题目,发现

卧槽D1T2我的统计方案数是阶乘级的?会挂?

卧槽D1T3其实二分 + 树状DP其实就能过了?

卧槽D2T1我的复杂度会变成O(n2logn)O(n^2 \log n)

各种爆炸之后……

luoguluogu估分 100 + 70 + 40 + 76 + 55 + 52 = 393 pts

作为一个初三党,第一次参加NOIp,感觉心态上还是出了点问题……

明年再战吧

1
Dilute.zibi = true;

Day 11

成绩出了……

CCFCCF数据竟然有100 + 90 + 40 + 88 + 50 + 52 = 420 pts

这次CCFCCF真的是用脚造的数据啊QwQ


QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动,使用 Azurus 作为主题。