codechef JULY16

r_64 posted @ 2016年7月13日 10:42 in 未分类 with tags codechef , 924 阅读

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在这个月中旬又好了。。


登录 *


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