NOIP2018游记

### Day -1 明天打打模板，一中集训完成心态也不错。考试冷静，仔细分析，我的代码能力还是挺好的。~~练工业代码还是效果不错~~ ### Day 0 模板的话， - P3367 【模板】并查集 - P3379 【模板】最近公共祖先（LCA） - P3369 【模板】普通平衡树 - P3374 【模板】树状数组 1 - P1177 【模板】快速排序 - P4779 【模板】单源最短路径（标准版） - P3371 【模板】单源最短路径（弱化版） - P1226 【模板】快速幂||取余运算 - P3372 【模板】线段树 1 - P3368 【模板】树状数组 2 - P3366 【模板】最小生成树 - P3383 【模板】线性筛素数 除了线性筛和LCA倍增的常数优化，其他都在5min搞完。 还有百行工业替罪羊平衡树，也在20min无调试一遍A 心态持续良好 ### Day 1 考前某校教练似乎对ZN OI事业很感兴趣??? ~~他：ZN啥时候这么NB了~~ 我：.... #### T1 T1?似乎做过?诶，这个[1,6]怎么出现了两次是[1,6]的最小值? 然后区间被划分成了[1,2]和[4,6],[3]不就是2吗? 分治+ST表区间最小值优化,$O(nlogn)$AC -45min #### T2 这题怎么和小凯的疑惑好像，都是组合，但不是质数? 等等，组合，方案，累加，不就是方案数多重背包吗? $O(Tn*max\{a_i\})$ 估计数量在50000000左右，没上一亿，AC -1h #### T3 不着急，先看部分分 $b_i=a_i+1$很好想，原题，数列分成n块使着每块之和最小值最大，二分即可 $a_i=1$也很好想，如果$2*m\ge n-1$就对边排个序取第m个小的边，不然就是排个序取第m个小的边+第m+1个小的~~似乎错了~~ $m=1$就没想出来了，~~弱啊~~，似乎枚举起始点可行?但是没时间打了 -1h30min #### 考后 然后我就回家了，luogu自测100+100+15，似乎挺稳 CCF竟然考原题也是醉了，不过自己实力还是在的，没做也A了，批评一下被这题卡退役的人。电子竞技，菜是原罪啊... ### D2 正常开局。~~一戒三红~~ #### T1 一开始以为这是一个图，一看数据范围...50%树,50%基环树 先想树的，题目意思就是求最小dfs序，简单，先dfs(1)，扩展时先不扩展，记录数组，按编号排序，依次dfs即可，$O(n)$ 环?跑DAG去边，剩下的节点都是环，枚举去边就是个树，跑上述过程即可$O(n^2)$ 似乎会被全是环的数据卡?随机化+减枝在AMD老APU上跑了3s，8700k应该能过 什么?T1就是这种题????CCF什么时候出过基环树了?????画风变化这么快的吗??? #### T2 woc什么题啊，看都看不懂，打表，打表，向考场ACDalao低头 #### T3 诶，这不是约束了状态转移的没有上司的晚会吗? $O(nm)$50pts 正解是什么?动态约束?动态DP?想不出来，AFK ### Day 3 Luogu自测似乎100+100+15+100+15+44=374 稳了稳了，省一还是有的，只不过没上400，不过还好 一雪去年被China Cheating-money Federation给降五分被卡省一的历史 MD省二第一是真的难受