NOIP2021 简要复盘/题解

Luogu7961

luogu7961.

设 \(f(i, j, k, l)\) 表示考虑前 \(i\) 位,放了 \(j\) 个数,后缀 \(k\) 个 \(1\),状压 \(i\) 及前三位结果为 \(l\) 的权值和(无序),转移平凡,最后分配顺序即可。

Luogu7962

luogu7962.

有经验的选手很快发现等价于交换差分数组,并不难发现差分数组一定是单谷的,证明不会,但想一下方差反应的是 "数据波动性" 就可以猜测出此结论。

考虑从小往大填数(因为是连续的,比从大往小分为两部分好处理),注意到方差经典式子 \(D(x) = E(x^2) - E^2(x)\),而数据又非常小,想到设 \(f(i, j)\) 表示填了前 \(ith\) 此时 \(a\) 对应和为 \(j\) 的 \(E(x^2)\)最小值,转移 \({\cal O}(1)\),状态量是 \(n \times n \times a_i\) 的,但注意到,非 \(0\) 的差分值至多 \(a_i\) 个,于是直接从非 \(0\) 开始填即可,复杂度为 \({\cal O}(n a_i^2)\)。

Luogu7963

luogu7963.

哈哈,哈哈

考场能写出来的都是神仙,至少和人类这种生物不太沾边

可以大概感受我改题的痛苦(雾):record,10k 起步,虽然有巨大头文件就是了,以及我实现可能比较蠢。

code.

放点很困难,考虑时光倒流一个个拿走,用并查集维护 没有棋子的只靠三号边联通块 以及 没有棋子的竖向二号边联通块 以及 没有棋子的横向二号边联通块,考虑能吃的就是把自己删除,然后和周围合并,答案是:三号联通块大小 + 三号周围能吃的 + 二号联通块横竖大小 + 二号继续延伸能吃的点 + 一号四周扫一遍即可。

但是有一个问题,二号联通块横竖向走的空白点,可能会被三号联通块覆盖,而且我们不太清楚三号联通块周围可以吃的点,一号二号没有冲突,但是一号能走的位置也可能被三号覆盖,不过一三冲突和一二冲突本质相同。

先处理冲突,线段树合并维护联通块内具体点,考虑按行编号,此时横向联通块维护的编号连续,那么可以区间查询,考虑再维护一棵,此时按列编号,此时纵向联通块维护编号连续,可以区间查询,这就解决了冲突的问题。

考虑查询三号可吃点,再维护两个线段树,一个表示联通块周围可吃的黑点,另一个表示白点,将等级离散化后,按等级建立线段树,即可快速查询可吃点。

上一篇:時雨のNOIP2021退役记


下一篇:【NOIP2021】报数题解