codechef JULY16

7月1日点开比赛发现只有7个题。。吓尿了。。我大cc本性暴露无遗

一堆dota狗吵得死的情况下我还坚持做毒瘤题。。我的抖M能力还可以嘛

被我猜中了，比赛延长了2天。。

EGRANDR

不解释

CHEFELEC

"codechef × 李电" 第一弹

用1把序列切成若干段，每一段削掉最大的那一部分。

CHEFARC

在傻逼题中算码农题了。

首先，对一个机器人需要建一个图，如果一步可以从$x$走到$y$那么连一条边，然后可以求出对每个点，这个机器人至少需要多少步可以走到。

设$f_1(x)$为机器人1至少要多少步走到点$x$，$f_2(x)$为机器人2至少要多少步走到点$x$。答案即为$\min_x(\max(f_1(x),f_2(x)))$。

边数$O(NMK^2)$，bfs复杂度与边数同级。

CHEFTET

“最大值”就是逗你玩的。。如果答案不是$-1$那么肯定是$v=\frac{\sum(A_i+B_i)}N$。

然后很容易把问题规模缩小$1$。。

• 如果$A_1=v$那么$A_2+=B_1$；
• 如果$A_1+B_1=v$那么什么都不干；
• 如果$A_1+B_2=v$那么$A_2+=B_1$，$B_2=0$；
• 如果$A_1+B_1+B_2=v$那么$B_2=0$；
• 否则无解。
• 最后把$A_1,B_1$删掉，得到规模缩小$1$的问题。

复杂度$O(N)$。

POLYEVAL

开始以为是trivial的多点求值问题。。看到时限、数据范围、模数之后觉得来者不善

首先，模数$p=786433=2^{18}\times 3+1$是一个标准的FFT模数。。其次$O(N\log^2 N)$配上多点求值的常数想过这个题简直就是天方夜谭。。最后，我真的不想写多点求值算法(唯一的一次尝试是花了四个小时没写出来就弃疗了)

考虑$p$的一个原根$r$，例如$r=10$。令一个数$0<x<p$的对数$\log x$是$[0,p-1]$中的一个数使得$r^{\log x}=x$。这样，如果询问的数的对数都是$3$的倍数，那么一次DFT就可以做掉(别忘了DFT的本质是特殊的多点求值)。

那么剩下$2/3$的数怎么办呢?考虑一个数$x$，假设$\log x=3r+1$，那么

$$F(x)=\sum_{i=0}^Na_ix^i=\sum_{i=0}^Na_ir^i(\frac{x}{r})^i$$

那么对所有$\frac{x}{r}$(这些数的对数都是$3$的倍数)求一遍后面那个多项式的值就是了。

对$\log x=3r+2$的情况把$\sum_{i=0}^Na_ir^{2i}x^i$DFT一次就是。

最后注意输入为$0$时输出$a_0$。

复杂度$3$次长为$262144$的DFT。

一个OJ心机起来，无人能阻挡。

CHSGMNTS

法克，又读错题了，还好很容易改

我们不关心$[A_a,A_{a+1},\dots,A_b]$的内部是否有重复元素，$[A_c,A_{c+1},\dots,A_d]$同理

枚举$[a,b]$，考虑数列的后缀$A_{b+1\dots n}$，如果$A_i$在$A_{a\dots b}$中出现过那么把它删掉，两边的数列断裂。最终设数列断成了长度为$x_1,x_2,\dots,x_l$的几段，答案就是$\sum \binom{x_i+1}{2}$。

枚举$a$，在$b$从$a$增大到$n$的过程中，$b$每增大就删掉一些后面的数。搞一棵线段树维护哪些数被删了，$\sum\binom{x_i+1}{2}$可以很容易的维护。

CHEFPOL

根据polya定理，我们需要考虑所有面到面的排列$p$，如果$p$可以由一系列旋转和镜面翻转得到。对于所有$1\le i\le N$，我们需要求出循环节个数为$i$的排列个数$f(i)$，最后用$\sum f(i)C^i$除以合法的$p$的个数就是答案。所以问题的关键是求$f(i)$。

什么样的$p$是可行的呢?我们发现给出的其实是一个无向图，两个面相邻那么之间有一条边，否则就没有。$p$代表着这个图的自同构排列。即：映射前相邻的面，映射后也应该相邻；映射前不相邻的面，映射后也不相邻。

因为题面中说是polyhedron的邻接图。。所以是稀疏图。。写了个爆搜，每确定一位就剪个枝

AC了

mgch的风格正在向sereja靠拢

WORKCHEF

这种傻逼题我居然不会做。。老子要写一个傻瓜题解。。

设一个数$x$的整除集合$div(x)$为所有1-9中的数字$i$组成的集合，其中$i$出现在$x$的十进制表达式中且$i$整除$x$。

唔。。我将会用到容斥原理。。基于$\sum_{t\subseteq s}(-1)^{|t|}=[s=\emptyset]$的反演。

我们要求$[L,R]$中$|div(x)|\ge K$的数个数。令$x$表示$[L,R]$中的整数，我们要求的就是

\begin{eqnarray}
Ans &=& \sum_x\sum_{|s|\ge K}[div(x)=s]\nonumber\\
&=& \sum_x\sum_{|s|\ge K,s\subseteq div(x)}\sum_{t\subseteq div(x)-s}(-1)^{|t|}\nonumber\\
&=& \sum_x\sum_{t\subseteq div(x), |t|\ge K}(-1)^{|t|}\sum_{|s|\ge K, s\subseteq t}(-1)^{|s|}
\end{eqnarray}

后面只与$|t|$有关，就是

$$Ans=\sum_x\sum_{t\subseteq div(x),|t|\ge K}f(|t|)$$

区间$[L,R]$中有多少个数$x$，满足$t$内所有数字都出现在$x$内，且都整除$x$?

通过数位dp可以变成$O(10\lg R)$个这样的问题：$[a\times 10^b,(a+1)\times 10^b)$内有多少个数$x$，满足上面条件?这样就可以变成：$<10^b$的数中，模$\text{lcm}(t)$为某个数且$t_0$($t$中没出现在$a$中的数)中的所有数字都出现了的数的个数。

用$f_{i,j,k,l}$表示$<10^j$的数中，所有数字是$k$，模$i$是$l$的数的个数。为了卡常数，我们注意到如下几点：

• $i$的取值范围只有$48$个。。$2520$的所有约数
• $l$的状态量是$O(i)$的
• $k$的状态量一般达不到$2^9$。。因为询问问的是模$\text{lcm}(t)$为某个数且$t_0$都出现了，而$t_0$只能是$t$的子集，所以$k$中只要考虑$i$的所有$<10$的约数啦。

然后预处理1s就跑完了，飞快的

询问的时候考虑求$[1,R)$内满足条件的数的个数，枚举$x$和$R$作为字符串的LCP，以及$x$的下一位，枚举$t$和$t_0$，查$f$这个表就好了。

CLUSSCHE

cc这次cha题好像玩脱了的样子，随随便便就能搞出炒鸡优的解。一个tie breaker问题没有起到break tie的作用。。不过后来前8名的分数还是不一样的说

考虑，有$N$个整数$D_i$和$N$个整数$U_i$，每次将$U$中的一个数加到$D$中一个数的头上，要求最小化加完数之后$D$的极差。贪心。每次拎出$U$中的最大数加到$D$中最小数头上。

然后，我们无视$C$的限制，直接跑算法就可以出来辣！为什么呢因为$C$这个限制实在是太宽松了。。。

数据范围萎得死，$O(N^3)$随便过，代码不到1K

这就是大众分做法>_<

我的做法嘛，找权值尽可能大的放$D$的方法。。权值是怎么计算的呢，假设放完了$D$得到一个极差和新的$U$，我们随机一个新的$D$用上面的贪心算法放到$U$上再得到一个极差，两个极差加起来就是权值了。当然实现的时候我随了好几个新的$D$。

并没有什么效果。。但是确实比大众分高了那么一丢丢。

ALLPOLY

就是求多边形的核的面积。。半平面交。。cc越来越辣鸡了

我从未见过如此厚颜无耻的OJ。。出个计算几何题不卡精度都不好意思说是一道计算几何题

总之卡了我几天就是了。。要从网上找半平面交板子看哪里写萎了，然后还要考虑平行(我是说，正向共线)的半平面只留下限制最严格的那个，就可以获得70分

讲道理数据中居然有这样的情况，队首两个半平面反向共线。。而且是用long double存储的情况下叉积直接等于0(并不是<eps，是直接等于0)。。QAQ不知道是怎样的数据。。望高人指点

然后我就开始了乱搞之路。。当然第一个想到的就是随机扰动，但是搞了很久之后才想到把所有点都随机扰动，扰了一个$\frac{2^{31}}{10^{11}}$以内的值发现过了所有小数据然而大数据WA了。。最后特判$N\le 12$的时候扰动否则不扰动

AC，讲道理我这么浪也只交了60发就AC了

OJ从未见过如此厚颜无耻的我

nonsense

好想做做自己想做的事啊。。

啊。。或许成为大人了就再也没有时间做自己喜欢做的事了呢

然而我想做什么呢

其实更好地说应该是计划内的事吧。。比如说deadline>today+10days的事情

但是我还是有其他想做的事的。。。

想学习chrome和firefox的附加组件编写。。因为有需求

搞到了盗版洛天依，但是不知道除了骂人以外能用来干嘛，而且我根本不会调转音啊啊啊

要是搞得到rin该多好

好想把所有任务都推掉，好想写自己喜欢的代码，或者连续10天去想uyhip的题

这个月ibm的题太水了，摔

lantern炸掉了。。寡妇王还真是叼呢

ps lantern在这个月中旬又好了。。