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$次)