[uoj#483][NOI2019]I 君的探险

这个傻逼题我模拟赛的时候只想出来了36分,然后做了2天才会正解,还卡了半天常数,说明我太菜了。
方便起见,不妨令$query(T,x)$为从初始状态下仅modify集合T中所有元素后$query(x)$的值。
这道题分成四个部分:

点1 ~ 5(下面代码中的OP1):每次暴力改一个点,然后询问所有点,统计信息即可。

点6 ~ 9(下面代码中的OP2):每次随机取一半的点,然后依次询问另外一半,做完以后可以把点分成3部分,递归下去就可以了,modify和query次数都不超过$n\log_2 n$。

点10 ~ 11(下面代码中的OP4):我感觉这块是最难想的,应该是我太菜了。这可以看作一棵以0为根的树,所有点的父亲都小于这个点的编号。
考虑两个集合$S$,$T$,满足$max(S)<min(T)$。则对于每一个$x\in T$,$S$中是否有x的父亲当且仅当$query(S,x)=1$。
我们知道每个点的父亲这个问题就解决了。
我们可以递归解决这个问题。
用函数$f(S,T)$表示集合T中所有元素的父亲都在集合S中,我们要用这个函数来找到所有T中元素的父亲。
我们最后的答案就是$f(\lbrace 0,1,2,…,n-1 \rbrace,\lbrace 1,2,..,n-1 \rbrace)$
那么我们考虑分治,如果$|S|=1$就可以直接求解了。否则把S分成两个集合$S1$,$S2$,满足$||S1|-|S2||\le 1,S1\cap S2=\emptyset,S1\cup S2=S,max(S1)<min(S2)$(就是前一半和后一半),然后我们现在要把T分成两个集合$T1$和$T2$,使得$T1$的父亲都在$S1$中,$T2$的父亲都在$S2$中,且$T1\cup T2=T$
然后modify掉所有S1中的元素,那么对于每一个$x\in T$,如果$x\le max(S1)$,那么$x\in T1$,否则如果此时$query(S1,x)=1$则$x\in T1$,否则$x\in T2$。
然后分别递归求解$f(S1,T1)$和$f(S2,T2)$
显然modify和query的次数都不超过$n\log_2 n$

点12 ~ 25(下面代码中的OP3):
我们现在没有之前那么好的性质了,而且限制也放宽了。看这个限制就感觉是一个$n\log_2 n$级别的算法,但是常数比较大。
因为这道题在query之前一般都要modify很多东西,这个比较慢,所以必须是一堆东西一起modify之后一堆东西一起询问,那么显然还是要分治。
考虑和上一个包类似的递归方式,令过程$g(S,T)$找出所有边$(x,y),x\in T,y\in S$。
$|S|=1$的时候同样可以直接做。
否则考虑把$S$分为$S1$和$S2$,然后我们希望找出两个集合$T1=\lbrace x|x\in T,\exists y\in S1,(x,y)\in E\rbrace$,$T2=\lbrace x|x\in T,\exists y\in S2,(x,y)\in E\rbrace$。如果对于所有$x\in T$,如果$query(S1,x)\bigotimes \lbrack x\in S1 \rbrack=1$,那么$x\in T1$,对于$T2$同理。但是可以发现如果有一侧为0,那么无法确定是否有边。($\bigotimes$表示异或)
我们发现这个无法做下去了。
那么我们干脆只做一部分,就是令$T3$和$T4$分别为能确定的$T1$和$T2$中的元素,然后只递归$T3$和$T4$。
如果我们只执行这样的一种模式,那么如果x在S中的连边个数是奇数,通过这种方式能找到其中一条边,如果是偶数,有$\frac{1}{2}$概率无法找到任何边,有$\frac{1}{2}$的概率能找到两条边。
然后我们可以用check操作删除已经找到所有出边的点,并且可以记录已经确定的边,在后面的操作中只考虑S1或S2中还没有被确定的边的条数的奇偶性。
然后对于第一层递归随机划分S多做几次,相当于每次通过$O(n\log_2 n)$次modify和query操作,得到期望$O(n)$条边。
我不知道这个期望次数怎么算,总之实测modify和query次数很少就是了。写这个东西递归的时候加点小优化可以直接可以过。(我第25个点还卡了会常数)

发表评论