YALI_NOI2019

雅礼NOI2019集训

Day1

早上\(8:00\sim 13:00\)是模拟考试。第一题预计\(59\)分,第二题预计\(57\)分,第三题预计\(33\)分。后来因为第二题常数比较大所以一部分点\(\text{TLE}\)了,实际三题总得分\(128\)分。

下午一开始是出题人讲了一下早上的模拟赛大部分思路还是比较相似的。

后来是难题选讲,一部分可以听懂,剩下的一些是平时不怎接触的,还需要继续研究研究。

Day2

今天安排了一天的讲课。上午讲的是有数和数据结构。基本上还是一些比较常见的东西,大部分还是了解过的,并且了解了一些优秀的算法。

下午讲得是关于图论的进阶知识。前面的一些比较基础的还是跟得上讲师的思路的,但是后面有一些没有学过定理和算法所以后半部分听的有点吃力。总得来说还是比较有收获的!

Day3

今天上午是考试。

第一题算是比较熟悉的类型但是在考场上最终还是没有把它\(A\)掉,最后只打了一个\(78\)的部分分。

第二题不太会打了一个\(16\)分就没管了。

第三题还算是比较有思路,在考场上也思考了很久但是一直手玩不过\(n=8\)的样例。直到最后下考还是没能调出来。

最后得分就是\(78+16+0=94\)。下午是考试讲题和难题分享。

讲题的时候发现第三题思路错了。后来难题分享听得有点吃力,大部分还是一些没有接触过的。

晚上自由安排。

Day4

上午考试。

第一题考试的时候真的不会做,直到下考也没有打。

第二题是个交互题,不太熟悉,打了一个\(30\)分的部分分就没管了。

第三题,这道题整场考试花了很久的时间,本以为可以得一个高分,结果最后因为没有考虑精度只有\(45\)

后来发现这场考试大部分人都过了第一题,我第三题卡一卡精度也可以过掉。

下午是考试讲题和难题选讲。

难题选讲讲了好几道容斥题,最近还算是接触的比较多。

Day5

上午考试。

第一题考试的时候只打了\(O(n\log^2 n)\)\(45\)分部分分,可能是因为没有仔细分析性质吧,后来发现其实挺简单的。

第二题是个数据结构体,先打了\(O(nm)\)\(44\)分暴力后打算攻克\(16\)的有特殊性质的\(Subtask\)但是后来没有调出来。

第三题考场上还算比较有思路,就是一个最短路\(+\)状压\(dp\)。考场上过掉的人还是挺多的。

最后出分,第一题的\(45\)分挂掉了,莫名其妙的\(RE\)了。最后只有\(144\)分,感觉每天的排名都不太靠前。

下午是考试讲题和难题选讲。

让我认识到还是要多打一点码农数据结构题!

Day6

今天是讲课日。

今天上午讲的是概率和期望。大部分题都是和\(dp\)结合在一起的。

其中涉及了一些做概率题的小技巧和例如高斯消元是未知数过多的时候我们可以将若干个数看做主元,然后将其他变量用主元表示以达到减少主元降低时间复杂度的目的。

其中也涉及了一些积分的知识,这都是我不太熟悉的知识,还要进一步研究研究。

下午讲得是数据结构,大部分都是见过的一些东西吧。

晚上的时间安排的是难题选讲。

Day7

今天早上做题。

第一题算是比较可做的题,但是由于状态设计的有一点问题,导致无法像题解一样用\(\text{FWT}\)优化复杂度,所以最终只有\(60\)分。

第二题是一道\(\text{Min_25}\)筛的题目,由于之前完全没有了解过,所有只打了一个线性筛,可以获得\(20\)分。

第三题是一道容斥加\(dp\),但是关于题解中提到的\(n^2\log C\)\(dp\)是这道题的基础,如果没有想到这个这道题的复杂度始终和\(C\)有关,而\(C\)\(10^{18}\)级别的。所以最终只能拿一个\(20\)分的暴力。

最终得分\(60+20+20=100\)

下午是讲课和难题选讲。

难题选讲显示以为石家庄二中的同学分享了两道比较优秀的计数题吧,之前的题一般都是以多项式作为正解,而今天他却只是将多项式做法作为一档较优的部分分,并且需要进一步去挖掘题目中的性质已到线性或更优的复杂度。这还是让我收获良多的。

Day8

今天讲课。

上午讲的是\(dp\)专题,从\(dp\)的定义,到\(dp\)状态的设计。然后介绍各种常见的\(dp\)模型,并给我们讲了一些例题。再从优化\(dp\)的角度讲,有转移优化,状态设计优化,分治优化\(dp\),数据结构优化\(dp\)。像我这种对\(dp\)掌握的不太熟练的选手还是很有收获的。

下午是杂题选讲。主要的是\(CodeForce,Topcoder,AtCoder\)的题目,主要以思维题为主,可能在暗示\(NOI\)的命题风格也在向这方面转变,还是很有收获的。