CFR 499 Solution

比较水的一场CF,好多人都AK了,下午和Vixbob和ZhYiC大佬一起打了下,写一下题解,貌似是水题目二分和$FST$专场。

A. Fly

Vixbob大爷切的,听说是很水的二分,需要注意精度。

B. Rocket

给了60次,直接用30次把$a$数组计算出来(输出$1$或者$m$即可),然后直接二分。

C. Border

如果存在两个数互质,显然在摸意义下可以构造出所有的数。如果不是,构造出的数一定是所有数$gcd$的倍数。对于$i$,要求$x \times gcd=i(mod~k)$。如果要输出方案,则$exgcd$就好了,否则直接算一下$k$和$gcd$的$gcd$,如果这个新的$gcd|k$,那么有解,否则无解。(这个东西是在写NOI2018Day2T1的时候yy出来的,不太会证明,应该是对的。

D. Mars rover

首先计算出原始的答案,然后可以计算出对于$u$,它的改变是否会对它的父结点造成影响,这个直接分类讨论一下,And和Or可能会改,Xor和Not一定会改。最后再$dfs$一次,如果这个点不会产生对父结点的影响,那么子树里面都不会。最后输出叶子的信息即可。

E. Store

画风突变,突然就不会做了,和$Vixbob$和$ZhYiC$讨论了好久。

题解给出的是二位线段树,但是在空间方面我觉得有点虚,而且不太好写。更好写的可以写KDTree或者CDQ分治。

首先可以求出开着的最早时间和开着的最晚时间。类似一个三维立方体。

最多有五层(图中是四层)最里面的是CLOSE,然后是UNKNOWN,OPEN,UNKNOWN,CLOSE。

首先可以判断掉INCORRENT和OPEN,问题在于UNKNOWN和CLOSE。

题目的意思是有一个未知的长方体。告诉你$m$个点一定不在长方体里面,而$n$个点一定在里面,查询一个点是否在里面。

我们可以把最里面的满足OPEN的长方体扩展到包含询问点。满足UNKNOWN当且仅当这个扩展的长方体不包含$m$个点中的任意一个。

就转化为一个三维问题,可以用KDTree或者CDQ等方法解决,KDTree就是利用KDtree结点覆盖的最大点和最小点减枝。(由于CDQ分治太神了,我没打出来,只打了KDTree

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*