codechef APRIL17

4.11线代期中，4.17普物期中

我tm就是在作死

upd 期中已完结 全面挂惨

SIMDISH

简单题。

DISHLIFE

如果要skip，贪心地想肯定是skip某一个。一个岛屿可以被skip的充要条件是它里面没有独特的(别的岛屿中都没有的)ingredient。

ROWSOLD

要最大化时间，显然就是最大化操作次数(移动步数是确定的，总时间=操作次数+移动步数)。一个1最多能被操作多少次呢?如果它的右边是个1，那么这个次数等于它右边的1的操作次数；否则等于它右边那个1的操作次数加1。

CHEFDIV

对一个数，假设知道它的质因子分解，那么可以贪心地求答案：每次除以自己那个出现次数最多的质因子，这样构成的路径一定是最优的。

现在$B-A$不大，那就枚举$O(\sqrt{B})$内的所有质数，把这些质数跑一遍$A\sim B$内的所有数，就可以把这些数全都因式分解了。

复杂度应该是$O((B-A)\log\log B)$的。

HLD

其实之前一直写错爆OJ的原因是。。cc上不能用数学函数。。我用log()函数计算代价，就wa了。

这题其实很简单。。令$f_i$为子树$i$的代价，显然一个点的重儿子一定是$f$值最大的那个儿子，如果有多个的话任意一个都可以(这个应该可以严格证明。。我懒得证了)。这样就$O(n^2)$了。

要优化复杂度的话。。我们考虑快速计算$f_i$，我们需要维护一个点向下的所有链中，顶端重链长度为$x$($x$不超过这个点到重叶子的距离)的链的最大代价。记这个数组为$arr_x$。对于一个点$i$，它的$arr$就是它的重儿子的$arr$往右一位($arr_{i,j}=arr_{child,j-1}$)，然后$arr_{i,0}$是轻儿子里面的最大$f$值。求$f_i$的时候，在$arr$中做$O(\log n)$次RMQ即可。

然后这个过程是可以单调队列维护的，总复杂度$O(n\log n)$。

SMARKET

求出输入中连续blocks的长度。例如20,10,10,10,7,7,7,10转成1,3,3,1。对于一个询问，我们可以定位出哪些blocks被它完全包含，以及它的边界(可以单独处理)。这样就变成了一个二分查找加一个“区间中$\ge k$的数的个数”询问，用主席树随手碾压。

CLIQUED

新建虚拟节点$v$，对所有编号不超过$K$的点$i$，将$v$和$i$连权值为$\frac{X}{2}$的边，然后去掉那个团。

嗨呀。。这题spfa的队列需要开到500w。。

DGTCNT

显然只要求$\le R$的答案，再减去$\le L-1$的答案。考虑求$\le R$的答案。

容斥，把问题变成有一些$i$必须出现$a_i$次的数的个数。枚举这个数和$R$的lcp。枚举接下来那一位。这样我们确定了这个数的一些位，剩下那些位的方案数可以用组合数算出来。

因为前导零很麻烦，所以最好在求方案数的时候，整个前缀第一个非零位都确定了，然后写一个小函数统计给出前缀和后面位数的情况下的方案数。例如，求$[1,2333]$中满足条件的数的个数，可以写成$1,2,\dots,9$,$[10,19],[20,29],\dots,[90,99]$,$[100,199],[200,299],\dots,[900,999]$,$[1000,1999]$,$[2000,2099],[2100,2199],[2200,2299]$,$[2300,2309],[2310,2319],[2320,2329]$,$2330,2331,2332,2333$中满足条件的数的个数。总共拆出来不超过$2\times 10\times 18$个区间，每个区间遍历一遍$0\sim 9$的digits就可以做出来，总复杂度大概是$1024\times 18\times 10\times 10$的。

SEABIL

普物考完之后开始写HLD。。然后就没有时间做这个题了，匆匆打了个80分暴力滚粗。

我在每一列选一个球，把它及它底下的球都打到最底下一行，然后再用一杆将最底下的球都打到$(N,N)$，最后一杆进洞。

然后。。我试了4个方向。。分数稍微高了一点。。然后就真的没时间了。。

貌似对$[-3,3]$与$[-100,100]$的数据，这个策略也没有烂到爆零。对$[1,3]$与$[1,100]$的数据这应该几乎是最优的吧。

RNDGRID

数据随机的题都是水题!(因为这代表出题人也不会做，为了骗钱只好强行出出来

考虑一个大暴力：一开始所有空地都未标记。从小到大枚举步数$L$，看哪些$L$步之后走到某个障碍的点没被标记，标记它们的答案为$L-1$。

这个复杂度显然是$O(LN^2)$的。。等等，数据随机!

我们知道有$PN^2$个障碍，那么一步是$O(PN^2)$的。期望多少步呢?这个步数$x$应该满足期望有常数个空地$x$步以后没有碰到障碍，也就是$(1-P)^xN^2=O(1)$，即$x=O(\log_{1-P}\frac{1}{N^2})=O(\frac{\ln N^2}{-\ln(1-P)})$。我们总复杂度就是$O(xPN^2)=O(N^2\ln N\frac{P}{-\ln(1-P)})$。然而mathematica画一下就发现$P\in[0,1)$时，$\frac{P}{-\ln(1-P)}$不超过$1$。这样的复杂度是$O(N^2\log N)$的。

所以一个很傻逼的暴力，复杂度是对的。

最后

cc貌似缺题了