RDFZchenyy的博客

博客

提供 NOIP Round #8 T1 的一个奇怪做法

2024-11-26 09:59:59 By RDFZchenyy

首先可以将题面转化为查询 lr 中,有几位上只出现 0 或只出现 1

我们考虑一个朴素的做法,当 m 足够小时,我们 O(nm) 预处理变更位置的前缀和,然后每次遍历 m 位,O(1) 查看是否有变更位置即是否有贡献,这个做法的复杂度为 O(m(n+k)),能通过 m100 的测试点。

从另一方面,n 小时,我们希望可以处理出所有答案。我们研究每一位会给哪些区间做贡献,将其放到数组上,做二维前缀和,这个做法的复杂度为 O(n2+nm+k),能通过 n104 的测试点。

由于 nm106,故有 m100n104 成立,我们做测试点分治即可通过本题。

感觉这个做法挺胡扯的,不过能过...

代码见本人 提交记录

RDFZchenyy Avatar