9
11
2017
0

codechef SEPT17

这一场我参与了出题,还混了一个Editorialist。

不过当Editorialist其实挺不爽的,不能像博客里面一样瞎几把写题解,还不能喷出题人

另外打一波广告,cc缺题啦!有好玩的hard或challenge请访问这个页面投题,或者直接联系problems@codechef.com。

CHEFSUM

求最小值第一次出现的位置

MINPERM

答案是$2\ 1\ 4\ 3\dots\ n-1\ n-2$($n$为偶数),$2\ 1\ 4\ 3\dots\ n-2\ n-3\ n-1$($n$为奇数)

顺便吐槽一下我出的cakewalk好像不太受萌新们欢迎?怎么回事啊

CHEFPDIG

大模拟

SEACO

维护$cnt_i$表示command $i$的执行次数,初始时等于$1$。倒着做所有询问,碰到第$i$个询问是$2\ l\ r$的话就把$[l,r]$的$cnt$都加上$cnt_i$。最后对每个$1\ l\ r$你知道了$cnt$,就可以很轻松地还原数组。复杂度可以做到线性。

FILLMTR

其实只要考虑$A_i=0$或$1$的情况即可,就相当于每个已经填了的元素$(i,j,B_{i,j})$是一条边,$B_{i,j}=0$的用并查集缩起来,$B_{i,j}=1$的搞二分图判定。

当然也可以不用并查集,直接搞棵生成树染染色。

WEASELTX

每个答案都是点权的线性组合。设点$x$的深度为$d$(根的深度为$0$),那么$x$对答案的贡献就是$\binom{d+\Delta-1}{d}\bmod 2$。由Lucas定理我们知道这玩意等于$1$当且仅当$(\Delta-1)\mathrm{\ and\ }d=0$。把深度一样的点的权值异或起来,然后做个and的前缀异或和即可。复杂度$O(N\log N)$。

SUMCUBE

其实求的是:对每个长度为$k$的边的序列,设这些边占用的点数为$p$,求$2^{N-p}$的和,

我们对$p$分类讨论,$p=2,3,4,5,6$,其实情况数也不是很多。注意$p=3,4,5$的时候要数三元环,$O(\sqrt{n})$分块或者压位都是可以过的。

你看我多良心,标程0.3s的题TL给5s。。

WEASELSC

先爆一波黑历史,这题本来出题人做法是错的然后被我茶包了

就是个dp,用购票那题的方法优化到$O(NK\log N)$。也不知道为什么过的人比SUMCUBE少一截。

QGRID

过气出题人想出Super Hard结果失败了。。这题还是不够难

idea是,你可以找出$K=m\log_2 n$棵生成树,使得任意两点的最短路是它们在某棵生成树上的路径。怎么找呢,你首先把中线上的$m$个点的最短路树抠出来,然后对两边递归把两边的树拼一拼即可。

剩下的相信很简单吧。

另外说一下这个题本来是准备出成路径修改路径求和的,但是我只做到了$O(Q\sqrt{n}\log^2 n)$(把$m$当成常数吧。。我忘了$m$的指数了,貌似是$1.5$)所以就没出出来。。那个$\sqrt{n}$的瓶颈是二维的矩形加法矩形求和。不过听wyh2000说二维矩形加法矩形求和是可以做到$O(\log^2 n)$的,所以这题有望做到$O(Q\log^4 n)$咯?欢迎讨论。。

本来这题是投给CTSC17的。。然后zgg把它拒了。。

SEAFUNC

没看懂出题人给的题解。。写了一发表现得很糟糕,就不细说了。

比较正经的做法是每一列单独处理,每连续的一段可以用$0\ 1\ 0\ 1\ 0\ 1\ col\ l\ r$一个命令。

一个小优化:把那些线段长度排序,跳过最短的若干个(总长度不超过$100$)

另一个小优化:如果有$0$夹在两个$1$之间(即上面是$1$,下面也是$1$),那么可以把它当成$1$(当然这种事情也不能干超过$100$次)

Category: 未分类 | Tags: codechef | Read Count: 166

登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com