NOIP2018赛前停课集训记(10.24~11.08)

前言

为了不久之后的\(NOIP2018\),我们的停课从今天(\(Oct\ 24th\))起正式开始了。

本来说要下周开始的,没想到竟提早了几天,真是一个惊喜。毕竟明天有语文考试、后天有科学考试,逃过了一劫。

这篇博客记录的便是停课这段时间的经历。

当然,这篇博客中有许多空链接,请谅解。

\(Oct\ 24th\)

上午

一场\(NOIP2018\)线下模拟赛\(AC\)\(T1\)\(T3\)\(T2\)悲惨爆\(0\)... ..

下午

花了一个下午写一道\(KD-Tree\)板子题:【BZOJ2648】SJY摆棋子。一直莫名\(TLE\),最后只好放弃,先去吃饭了。

晚上

继续写这道\(KD-Tree\)题,一直写到\(19:30\),才发现一个很智障的错误。不管怎么说,总算是过了... ...

然后去写了一道点分治:【洛谷2664】树上游戏(居然是一道黑题)。

\(Oct\ 25th\)

上午

早上一来先写了道还算简单的题目:【洛谷2519】[HAOI2011] problem a,是昨天比赛\(T3\)的原题。

然后打了场\(HHHOJ\)上的模拟赛:NOIP2018 模拟赛(二十四),竟得了\(Rank\ 1\),涨了一波\(Rating\)

下午

先写掉了今天早上比赛中T1和T3的原题:【洛谷2152】[SDOI2009] SuperGCD【CF739E】Gosha is hunting

然后写了一道二合一题:【洛谷2468】[SDOI2010] 粟粟的书架,练了一下主席树。

最近做到一道卡树套树题目:【洛谷3157】[CQOI2011] 动态逆序对,于是决定去学一学 CDQ分治,做了一道板子题:【BZOJ3262】陌上花开

晚上

【洛谷3157】[CQOI2011] 动态逆序对做掉了。

学了一下莫(\(meng\))比(\(bi\))乌斯反演,对着题解写了一道题:【洛谷2257】YY的GCD

然后,去做了一道类似的题目(实际上还要稍微简单一点):【BZOJ1101】[POI2007] Zap

\(Oct\ 26th\)

上午

一场\(NOIP2018\)线下模拟赛,第一题被假题面坑死了... ...

下午

写了道树上主席树题:【洛谷2633】Count on a tree

然后写了一下这道题的升级版:【BZOJ3123】[SDOI2013] 森林

好不容易在看完题解后做掉了一道反演题:【BZOJ3994】[SDOI2015] 约数个数和

晚上

今天晚上在家里自己练习,刷了一道动态规划题:【BZOJ1925】 [SDOI2010] 地精部落,这题不是什么纯粹的动态规划,而有一大堆性质,因此做到心态爆炸。

\(Oct\ 27th\)

上午

今天是在家里训练的。

上午补了几篇博客,然后去做一道树套树的题目:【洛谷3759】[TJOI2017] 不勤劳的图书管理员,结果由于这种数据结构题细节太多,一直没做出来。

下午

继续做早上那道题,好不容易才过了。

晚上

学了一下传说中的 BSGS算法,然后去做了道数学模板三合一:【BZOJ2242】[SDOI2011] 计算器

做了一道BSGS的比较板子的题目:【洛谷4884】多少个1?,这题居然会爆\(long\ long\)!害得我调死。

然后又去做了一道莫比乌斯反演的题目:【洛谷2522】[HAOI2011] Problem b

\(Oct\ 28th\)

上午

早上是一场线上比赛:【HHHOJ】NOIP2018 模拟赛(二十五),居然还涨了\(Rating\)

下午

写掉了上午T3的原题:【51nod1743】雪之国度

然后忙着博客搬家... ...

晚上

先写了一道假的莫比乌斯反演题:【BZOJ3930】[CQOI2015] 选数,实际上容斥就能过。

然后去写了一道树套树题:【BZOJ2141】排队\(hl666\)奆佬又是分块水过,吊锤我的树套树)。

\(Oct\ 29th\)

上午

今天是一场线下比赛\(T3\)最后\(40\)分钟改题面,结果来不及写了直接爆\(0\)。最后得了\(130\)

下午

订正了一下上午的比赛,把\(T1\)原题做掉了:【HDU4473】Exam

花了挺多时间,做掉了\(T3\)的原题:【BZOJ4458】GTY的OJ

下定决心去学了一下传说中十分恶心的算法:杜教筛。做了一道板子题:【洛谷4213】【模板】杜教筛(Sum)

然后又是博客搬家... ...

晚上

总算完成了博客搬家(真是一场浩大的工程)!

然后把一道昨天写了很久的题目给A掉了:【BZOJ3720】Gty的妹子树(昨天调了很久没调出来,今天一眼看去就是3个BUG)。

\(Oct\ 30th\)

上午

一场线下比赛\(T1\)为了卡常不小心把代码改\(WA\)了... ...

下午

写了一道比较好的\(Splay\)板子题:【BZOJ1861】[ZJOI2006] Book 书架,又是一个细节写挂了调了很久... ...

\(Oct\ 31st\)

上午

大清早写了一道网络流题:【洛谷2763】试题库问题。这是我第一次用网络流来做网络流24题,以前都只会用最短路、贪心等算法乱搞。

下定决心去学了一下左偏树,做掉了板子题:【洛谷3377】【模板】左偏树(可并堆)。发现其实也不是很难。

中午

写了一道左偏树的例题:【BZOJ2809】[APIO2012] dispatching,没开\(long\ long\)调死... ...

下午

做了道\(Manacher\)算法题:【BZOJ2565】最长双回文串

跟着\(hl666\)奆佬去做了一道二维线段树题:【洛谷3437】[POI2006] TET-Tetris 3D,这题居然卡内存!恶心至极!

写了一道传说中的可持久化Trie树题:【BZOJ3932】[CQOI2015] 任务查询系统。(实际上我写的是主席树... ...)

晚上

去写了一道杜教筛+莫比乌斯反演+狄利克雷卷积的题目:【洛谷3768】简单的数学题

\(Nov\ 1st\)

上午

早上先写掉了一道启发式合并\(Splay\)的题目:【BZOJ2733】[HNOI2012] 永无乡

上午是线上考试:NOIP2018 模拟赛(二十六),又涨了一波\(Rating\)

下午

下午断网... ...写了\(3\)道题目,都没法交。

晚上

下午写了一道需要加懒惰标记的左偏树题:【BZOJ4003】[JLOI2015] 城池攻占,把一些细节改对后就过了。

下午还写了一道很好地利用精度的题目:【BZOJ1011】[HNOI2008] 遥远的行星

\(hl666\)奆佬的教导下做掉了一道很神仙的线段树+二分题:【BZOJ4552】[TJOI2016&HEOI2016] 排序

写了一道网络流:【洛谷2774】方格取数问题,第一次知道神奇的最小割最大流定理。

\(Nov\ 2nd\)

上午

先去学习了一下\(CRT\)\(EXCRT\),做了一道板子题:【洛谷4777】【模板】扩展中国剩余定理(EXCRT)

然后花了将近一个上午去写一道恶心的动态拆点\(Splay\)题:【洛谷3960】列队

下午

今天是一场\(UR\)赛制的线上模拟赛:【HHHOJ】NOIP2018 模拟赛(二十六点五)(我承认这比赛名称真的诡异),今天题目还是比较水的,我这么弱居然\(AK\)了,不过是\(unrated\)... ...

晚上

先做了一道传说中的模拟退火题:【HDU5017】Ellipsoid,结果正解是爬山算法。

学了一下线性基,做了一道板子题:【洛谷3812】【模板】线性基

做了道线性基的例题,还是比较简单的:【BZOJ4568】[SCOI2016] 幸运数字

\(Nov\ 3rd\)

上午

一场线下模拟赛\(T1\)看错题意爆\(0\),结果\(130\),被吊锤了... ...

中午

做掉了上午\(T3\)的原题:【BZOJ2122】工作评估感觉自己在卡评测

去练习了一道斜率优化\(DP\)题:【BZOJ2726】[SDOI2012] 任务安排。是《一本通》上的题目,为一道题目打了\(3\)份代码。

晚上

又是一场线下模拟赛(一天两场真心差评),\(T1\)因为太菜考虑漏了一种情况,结果\(270\)

\(Nov\ 4th\)

上午

早上来先把一道昨天做了一个下午的题目\(A\)掉了:【BZOJ2752】[HAOI2012] 高速公路

一场线下模拟赛\(T2\)做了太久,导致\(T3\)来不及做了... ...

\(T2\)原题过掉了:【BZOJ5102】[POI2018] Prawnicy

下午

匈牙利算法过了一道网络流题:【洛谷2764】最小路径覆盖问题

去刷了两道概率期望题:

【洛谷3830】[SHOI2012] 随机树:比较好的期望\(DP\)题,至少代码很短

【BZOJ3925】[ZJOI2015] 地震后的幻想乡:这题在洛谷上是一道黑题,听说可以用积分去做,但实际上可以写一个比较神仙的状压期望\(DP\)

晚上

去好好学了一下斜率优化\(DP\),做了两道《一本通》上的题目:

【CF311B】Cats Transport:先是一波转化,然后就是比较简单的\(DP\)

【BZOJ1096】[ZJOI2007] 仓库建设:一开始看错题目,死活做不出来。后来发现只能往下走,就可以直接套上斜率优化跑\(DP\)了。

\(Nov\ 5th\)

上午

早上来写了两道斜率优化\(DP\)

【BZOJ1911】[APIO2010] 特别行动队:比较裸的\(DP\),真的简单。

【HDU3507】Print Article:也是一个较水的\(DP\)吧。

然后是一场线下模拟赛,得了\(175\),好像还不错。(\(T1\)随机化\(95\)分)

下午

下午回班看运动会去了... ...

晚上

花一个晚上订正掉了\(T2\)(细节是真的多)。

\(Nov\ 6th\)

上午

一场线下比赛\(T2\)手贱把取模优化写炸了,调了一个多小时没跳出来,白丢了\(60\)分... ...

下午

写了一道斜率优化\(DP\)题:【洛谷4360】[CEOI2004] 锯木厂选址,总算把《一本通》斜率优化\(DP\)部分做完了。

去做了一道往年的\(NOIP\)题:【洛谷1083】借教室,正解据说是二分+差分,没想到我的暴力线段树竟然过了。

做了道假的数位DP题:【BZOJ2425】[HAOI2010] 计数,实际上可以用组合数学来做。

\(Nov\ 7th\)

上午

一场线下模拟赛,这或许是\(NOIP2018\)前最后一次模拟赛了,我花了\(3\)个小时做\(T1\),最后总分\(105\)... ...

下午

订正上午的比赛... ...

晚上

写了一道组合数学的动态规划题:【BZOJ2111】[ZJOI2010] Perm 排列计数

\(Nov\ 8th\):后记

还有两天就\(NOIP\)了!

于是,我决定不做其他题目,开始一心一意刷板子了。

关于我的刷板子计划,可以详见这一篇博客:NOIP2018赛前停课集训记——最后的刷板子计划

最后,祝\(NOIP\ RP++\)

完结。

败得义无反顾,弱得一无是处
原文地址:https://www.cnblogs.com/chenxiaoran666/p/NOIP2018_note.html