NOIP2018游记

z3475 · 2018-11-12 21:26:43 · 个人记录

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

不着急，先看部分分

$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

诶，这不是约束了状态转移的没有上司的晚会吗?

正解是什么?动态约束?动态DP?想不出来，AFK ### Day 3 Luogu自测似乎100+100+15+100+15+44=374 稳了稳了，省一还是有的，只不过没上400，不过还好一雪去年被China Cheating-money Federation给降五分被卡省一的历史 MD省二第一是真的难受