NOI online2022 提高组游记

· · 个人记录

比赛开始，先开 T1 ,一看是要维护一个单调栈。我就想了仿照单调队列的做法直接 O(n) 维护。但是，看了一下，居然有 q 组询问，人傻了。分析了大约半个小时，想不出优化，就暂时放弃，看后面的题。
我决定直接开 T3。我看了一下题目给出的函数值的图，发现了一个规律，就是对于图中对角线的部分，f(x,y) = f(x-1,y) + f(x,y-1) - f(x-1,y-1)。
但是，这个规律并不能看出来有什么用，就打了一个 O(n^2) 的暴力走人。
回头来看 T2，题意是给出每个人会做的题，求是否存在有两个人有共同会做的题并且一个人会做的题不完全包含另一个人会做的题。我直接想到了一个思路，就是把每个人会做的所有题的编号状压到一个 int 变量里面。大概就是 problem[i] |= xi(x 是当前人会做的题目)。测了一下样例，发现假了，例如 1,3 这样的数据就能 hack。于是临时换成 bitset来记录。最后这道题最低 0 分，最高 40 分。
回去看 T1，快速打了一个 O(nq) 的暴力走人。

预计最高得分：10+40+10=60 分。
预计最低得分：0+0+0=爆零
等官方数据吧。

UPD:

冥间数据 15+30+10=55分。

UPD:

官方数据 15+30+10=55分。