【游记】NOI2020 半退役记

Day 0

笔试非常简单,尽管有一些不在题库里面的。但是查成绩的时候就很有意思了,查成绩的时间定在了 15:05,但是我卡着时间点开,看到了全部都是 ( ext{Wrong}),每题的得分都是 (0/1)!!什么!!我笔试爆零了?答案没交上QAQ?

问了问对面的同学能否看成绩,他说”能啊,直接点开就看到了“,我的脑袋一懵,我不会在 NOI 笔试爆零了吧。

退出去重新登,诶不错,笔试阿克了。

试机得知今年有 C++11,试机还有一道交互题。(然而最后并没有交互)

Day 1

开场看了 T1,觉得是一个很明显的矩乘,然后用一些经典操作优化一下,大概就 (mathcal O((wn)^3log T)) 了,感觉能过就写了,有点紧张,写完大概 1h 左右。

后面看完 T2、T3,感觉 T3 这种数据结构题比较适合搞分(之前没做过区间逆序对,所以没意识到)。大概搞了 (52) 分也过去了挺长时间的。

T2 想了半天才想到 40 的容斥怎么做,之前一直只会 24,后面的树形 DP 感觉思路已经来了,但是时间并不够,因此就只有 (100+40+52=192) 了。

中午的时候翻了翻群,突然发现 T1 要判 (-1),我整个人又懵了 qwq,不过看了看应该卡 (5) 分这样(丢了个密码条)。15:00 准时出了成绩,发现是 (95+40+64=199),不错 T3 多卡了 (12),反向挂分可还行,良心 lxl。

出来问了问全世界都会 T2,整个树形 DP 加个线段树合并优化就过了。包括参加国家队选拔的高三集训队,前 (50) 大概在 (240) 这样,感觉今天确实 T2 拉了分,技不如人,明年再来。

Day 2

尽管昨天差了挺多的,但是今天还是抱着拼尽全力的心态打。

开场看完题发现什么都不会,开始有点慌张了,输出了 T3 的 (-1) 和 T2 的 (max h) 就先不管了。

搞了 2h T1,一直没有什么思路,后面仔细观察才发现,(m geq n-1) 的时候直接每次删掉最小的来贪心,是完全正确的。

那么 (m=n-2) 怎么做呢?一直在想有一步操作恰好删去了两个数这个条件,但是一直没有正确思路。后来画了画才发现大概是要选出 (t(t<n)) 个数使得和是 ((t-1)k),仔细想想发现就是分成两个集合,每个集合都满足 (sum (d_i-k)=-k),然后每个集合套一个 (m=n-1) 的做法。

那么就是求这样的集合划分方案了,有一个很显然的背包 DP,用 bitset 能优化。但问题是我算了算 (mathcal O(frac{nmk}{omega})) 的复杂度根本开不下空间,只能勉强开到 (nleq 100),一直想不到什么更优秀的方法,于是写了 (n leq 100) 然后卡了卡常(最后得分 (80))。

做完这个已经 3h 多了,后面一直想 T2,心态有点很崩了,想法假了很多次,时间不够什么也搞不出来。

出来问了问,主流选手 (130sim 140),牛逼选手 (200+),感觉没有翻盘的希望了,所以今天一整天都比较坦然,就只关心自己最后的排名了。出分咕了亿会(15:00 咕到了快 17:00),最后得分 (80+16+5=101)

总分 (100+199+101+0=400),刚好凑了个整,rk82。

队线 (447),不甘心,明年再来。

其他人

FJ 省今年考得很好,nealchen 和 Lagoon 都 500+ 前 25 了,slz 同学也 480+ 进队,lh 450+ 也进了。

有点惨的就是 PinkRabbit 446,差了个 D2T3 输出 (-1) 的分数,如果写了就稳了,但是高一的国家队 IOI Au 然后他进队还是很有希望的。

xyz32768 就非常惨,有着前十的水平,但是 Day1 原地爆炸,Day2 心态崩盘,导致最后也只有 Ag,为他感到非常可惜,祝他好运。

小结

今年从 NOIP 打到 FJOI 再打到 NOI,一条命在最后没了,明年只能再开一个档,加油。

这次比赛自己整体发挥是比较正常的,但是有些分是触手可及的,却没有拿到:

  • D1T1 的 5 分。
  • D1T3 的 8~12 分,其实四维莫队早就会了,一直不会算复杂度,在那边一直假,最后真的没时间了。
  • D2T1 的 20 分,这个就非常显然,是自己太傻了,明明在处理 (m=n-2),还把 (m) 的范围当成 (5000) 开数组。
  • D2T2 的 8 分,最后发现自己一直在想的做法假了,但是直接暴力也能过 (max h leq 5)

这些分加上也差不多碰到队线了,但是考场确实不一定能发挥全部水平,而且还有可能挂分(挂分这种东西,确实应该写完多检查、对拍、造极限数据啥的来避免),因此确实是水平不如人,D1T2 差太远了。

目标要远大一点,不能只研究队线附近的问题,比如这次的 D1T3、D2T2、D2T3,就是很高水平的体现,平时就应该多研究研究这种题,遇到的时候做出一题也能救命了。

明年再来还有一个先决条件是进省队,FJOI 属实坑人,但是水平足够高也不会怕这种比赛(比如像 Lagoon),而且因为 FJ 省队水平想搞的人不是很多,所以 FJOI 压力也不会很大,希望明年能顺利吧。

接下来可能就得多读读书了,一直搞 OI 确实效率不高。要多做题了,高深问题也要积极研究,加油吧。

原文地址:https://www.cnblogs.com/cyx0406/p/13532518.html