codechef AUG16

r_64 posted @ 2016年8月19日 19:11 in 未分类 with tags codechef , 952 阅读

这几天在外面旅游。。看了一下题目感觉好难。。难题都不会做,简单题不都会做,而且还没时间打

玫瑰彩虹大爷又出题了。。看到题目就感受到了深深的恶意。。还有一个题叫GOODPROB是什么鬼

CHCHCL

打表找规律,$nm$是偶数就好

CHEFRRUN

每一个箱子的下一个是确定的,就是一个基环内向森林。把环上的节点都找出来就是了。

MAXGRID

令$f(l)$为第一问的答案,那么二分查找可以求出第二问答案,复杂度乘以一个log。

那么考虑求$f(l)$,枚举$x,y$表示正方形左上角,不过复杂度太高会T。

辣么我们只枚举$x$,令$a_i$为$y=i$时正方形内权值和,发现我们需要求的只是$a_i$的最大值。

$x$递增的时候,一些$a_i$会改变。设老的$x$为$x_0$,对每个$x=x_0$的点$(x_0,y)$,它对$(y-l,y]$有负的贡献,贡献值为点权;对每个$x=x_0+l$的点$(x_0+l,y)$,它对$(y-l,y]$有正的贡献,贡献值也是点权。

我们需要动态维护$a$数组,支持区间加法和全局max。线段树即可。

复杂度$O(n\log n)$。考虑到第二问还有一个二分答案,总复杂度$O(n\log^2 n)$。

CHAHG

只考虑第一种情况的话。。就有$n-1$个一元一次不等式,取解集的交就好。

只考虑第二种情况同理。

然后把两个答案合并,注意一种特殊情况就是两个答案区间相邻的时候要合并成一个。

这题我拍了。

复杂度$O(\sum n)$。

SHAIKHGN

艹,这个题想了很久,我智商捉急啊

对每个$0\le l\le 31$,预处理$f_{l,i}$为一个bitmask表示$i$收到笑话后第$2^l$分钟哪些人收到了笑话。

$f_{0,i}$是$i$的所有出边,$f_{l,i}=OR_{j\in f_{l-1,i}}f_{l-1,j}$。预处理的复杂度是$O(\frac{N^3\log k}{w})$,其中$\frac{1}{w}$表示压位。

询问的时候,设询问$x,k$,那么把$k$二进制分解为$2^{a_1}+2^{a_2}+\dots+2^{a_p}$,询问的时候枚举$i$可以维护$2^{a_1}+2^{a_2}+\dots+2^{a_i}$秒后哪些人$S$收到了笑话。加入一个$2^{a_{i+1}}$的时候,把$S$变成$OR_{j\in S}f_{a_{i+1},j}$。复杂度$O(\frac{N^2\log k}{w})$。

CHEFTRE

制杖题。玫瑰彩虹的代表作(大雾)。

首先考虑序列上的版本,为了应付2操作我们显然需要一个hash。。判断相等就直接看hash是否相等就好。

考虑3操作,直接上可持久化AVL显然是可以的。1操作也就很简单了,2操作也就是维护哈希而已。

问题被搬到了树上,显然是要树链剖分。。只是要多资瓷一个操作,就是翻转一段区间。

然后码码码就好了。复杂度$O(N+Q\log^2 N)$。哦对了还要拍拍拍。。

好怀念上个月的cc,最难题1k,最码题3k。。

ps.这题翻译有问题。。“reverse”被翻成了“取反”。。我当“negate”做了很久。。鈤。。不过这样就只用搞两个询问了,询问$1$直接变成询问$3$,参数为$u,v,v,u$就是。

pps.这题要垃圾回收。。我服了玫瑰彩虹。。不过由于有用的节点其实只有$N$个,所以空间复杂度开到$O(N)$都没事。并且,回收节点的均摊复杂度显然是$O(1)$。

GOODPROB

这么早就说它是好题,会不会给人一种硬点、钦定的感觉?

首先考虑一个问题:要求维护一个多重集,支持

  • 插入一个数,数的范围$[0,2^{2a})$
  • 给出$x(0\le x<2^{2a})$,求集合内有多少个数$p$满足$x\text{ and }p=x$。

令$f[i][j]$表示集合中这样的数的个数:把它看成$2^a$进制的两位数,则高位是$i$,低位$k$满足$k\text{ and }j=j$。插入一个数的时候找出所有满足条件的$j$插入;询问的时候设$x$的高位是$x_0$,低位是$x_1$,枚举$i$满足$i\text{ and }x_0=x_0$,求$f[i][x_1]$的和即可。一次操作复杂度为$O(2^a)$,相当于根号级别。

同理考虑另一个问题:要求维护一个多重集,支持上面两个操作,只是把第二个操作中的$x\text{ and }p=x$改成$x\text{ and }p=p$。令$g[i][j]$表示集合中这样的数的个数:把它看成$2^a$进制的两位数,则高位是$i$,低位$k$满足$k\text{ and }j=k$。剩下的部分跟上面算法几乎完全相同。

考虑笛卡尔树。然后就变成一个点的左子树$T_l$,右子树$T_r$,从$T_l$中选出$L$,从$T_r$中选出$R$使得$L\text{ and }R=L$或$L\text{ and }R=R$求方案数。假设$|T_l|\ge |T_r|$,且已经维护好了$T_l$这个多重集的$f$和$g$,那么把$T_r$中的数一个一个拉出去询问就可以得到答案;为了得到整个子树的$f,g$我们需要把$T_r$中的数一个一个插入$T_l$的$f,g$结构。这样复杂度为$O(|T_r|\sqrt{A})$,其中$A$是数的大小。

这个复杂度就是启发式合并了。。很容易做到$O(N\log N\sqrt{A})$。卡常数秘诀:

  • 我们肯定是用挂链哈希来存所有的$f,g$的值。调整哈希函数(一般用$h(x)=x\bmod p$的话调$p$就好)。
  • 在遍历所有$a\text{ and }b=a$的$a$时候是这样的:
    for (a=b;a;a=(a-1)&b) process(a); process(0);
    遍历所有$a\text{ and }b=b$的$a$也差不多。
  • 反正我卡到随机数据1.6s之后就交了。。cc上好像跑得很快。

CHEFCRUN

假设第一步往左边走,右边同理.。讨论讨论就好。

  • $s$走到$t$,过了$t$之后掉头。我们走过的路程是$s$到$t$的路程加上两倍$t$开始且不到$s$的最小前缀。
  • $s$走到$t$之前掉头,从$t$的后面绕到$t$。可能会经过$t$然后向前走,走到某个地方掉头后回到$t$。我们走过的路程是一整圈的路程加上$s$到$t$的路程减去$s$到$t$的最大连续子段和。

时间复杂度$O(N)$。

TRICONT

首先你要发现一个性质:三角形能包围住房子,当且仅当原点到三角形三顶点的向量满足,任意两个都在剩下那一个的两侧。

对于一个向量$i$,记严格在它左边的向量个数为$l_i$,严格在它右边的向量个数为$r_i$。

然后思考:给出$n$个点怎么求答案。对于每个向量其实只需要记录其极角,极角排序之后二分一下就能求出$l,r$。我们只要求出不存在共线向量的三元组个数(这里其实省略了超级多的细节。。因为后面的柿子并不完全是不共线的,多算了【两个同向共线和一个不共线】这种情况),减去$\frac{1}{2}(\sum_{i=1}^N(\binom{l_i}{2}+\binom{r_i}{2}))$就好。后面那个柿子表示有两个向量在另外那个的同侧的情况,每种情况被算了两遍所以乘以了一个$\frac{1}{2}$。

考虑动态维护这玩意,只要用平衡树以极角序维护向量的顺序,插入一个向量$v$的时候,首先找出逆时针区间$(v,rev(v))$,然后把这个区间的$r$都加$1$,这个区间的大小作为新向量的$l$;然后找出顺时针区间$(v,rev(v))$,把这个区间$l$加$1$,区间大小作为新向量的$r$;最后把$v$插在合适的位置即可。

复杂度如果我没算错应该是$O(N\log N)$,算法是在线的。我还说为什么要强制在线,原来是强迫我们写平衡树。。否则线段树应该是可做的。

EBOLA

这题很良心。。不像有的cha题做都做不得/看都看不懂。。

1.退火。。对答案进行退火

2.退火。。对于一个排列$p$我们贪心,每次给$p$中最靠前的、没接种疫苗也没感染的点进行接种。对$p$退火

2的效果比1要好些吧,如果不好就是写萎了→_→2能拿80+分哦


讲真。。这场比赛的四大天王MAXGRID,GOODPROB,CHEFTRE,TRICONT都是垃圾数据结构题。。TRICONT还好一点,稍微有点思维难度


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter