z3475 的博客

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省二第一是真的难受


2018-11-12 21:26:43 in 未分类