8
18
2017
0

codechef AUG17

垃圾cha题,毁我青春。以后看到琪琪给给的cha题还是不要去做了吧。。

upd. rating predictor说我7☆了。。那这应该就是退坑一战了吧。。虽然以后还会去cc圈圈钱,我也还会继续爱着这个oj的哦(笑)

RAINBOWA

先判是不是1234567654321形的串,再判是不是回文串。

CHEFMOVR

考虑$D=1$的情况,首先平均数得是整数,然后从左至右每次贪心地将当前数变成平均数即可。

$D\ne 1$的情况,会发现数列中下标膜$D$不一样的数是不影响的,变成$D$个$D=1$的问题做就好。

复杂度$O(N)$。

话说我因为cout和printf混用WA了一发。

GCAC

大模拟

PALINGAM

垃圾讨论题。

第一步A出的字符B必须没有,否则B胜。

如果第一步A出的字符为$c$,且$c$在$s$中的出现次数至少为$2$,那么A胜。

第二步B出的字符$d$A必须没有,否则A胜。

然后B把所有$d$都放$c$左边就可以防止最终串变成回文串并获得胜利。

WALKBT

如果是静态问题:给出一些叶子,求至少在根到一个叶子路径上的点的数目。将叶子排序后设为$a_1,a_2,\dots,a_n$,则$\sum_{i=2}^nN-LCP(a_i,a_{i-1})$就是答案。

对于动态的问题,用可持久化线段树维护所有版本的叶子,用平衡树维护叶子排序后的结果就好。在可持久化线段树上维护Hash,查LCP和比大小都是$O(\log N)$的。复杂度$O(N\log^2 N)$。

HILLJUMP

我们考虑弹飞绵羊那题的分块,这样我们只要对每个点维护它跳多少步之后跳出块,以及跳出块后跳到哪即可。另外维护一个结构支持$O(\sqrt{n})$区间加法,$O(1)$单点查询。

那么现在的问题就是维护区间加法。我们发现只有$200$个数的next需要改动($[l-100,l-1]$和$[r-99,r]$),并且(若块的大小至少是$100$)它们集中在$O(1)$个块中。为了获取新的next,我们需要提出$[l-100,l+99]$然后做一遍two pointers就可以更新$[l-100,l-1]$;提出$[r-99,r+100]$然后做一遍two pointers就可以更新$[r-99,r]$。

复杂度$O(Q\sqrt{N})$。

(感觉cc上的数据结构题都很straight forward啊??

STRINGRA

  1. 首先,$0,1,2,\dots,N$必须是图的一个拓扑序。
  2. 对任意$i$,如果$i\to i+1$的边不存在,那么无解。
  3. 考虑$i$和$i+1$。
    • 如果$i$和$i+1$出度不同,那么说明$i+1$是某种颜色的最后一次出现,然后$i$和$i+1$的出边指向相同的地方(除去$i\to i+1$的那条);如下图
    • 如果它们出度相同,那么$i$和$i+1$的出边指向相同的地方——除了$i\to i+1$的那条和某条以$i+1$为起点的$i+1\to u$。$u$和$i+1$的颜色一样。如下图

这样可以得出(颜色个数)条链,每条链上颜色相同。字典序最小的话贪贪就好。

CHEFFA

设第$i,i+1,i+2$个位置操作$c_i$次,那么操作完之后第$i$个位置的值等于$A_i+c_{i-2}-c_{i-1}-c_i$。

实际上问的是有多少个数列$c$,使得$\forall i,A_i+c_{i-2}-c_{i-1}-c_i\ge 0$。

用$f_{i,j,k}$表示只考虑$c_{1\dots i}$,且$c_{i}=j,c_{i-1}=k$的数列的个数,dp即可。

我们可以确定$c_i$的bound:注意到操作是不改变$\sum_i\phi^iA_i$的值的,其中$\phi=\frac{1+\sqrt{5}}{2}$(因为$\phi^2=\phi+1$)。那么$c_n\le \frac{\sum_{i\le n}\phi^iA_i}{\phi^n}\le maxA\cdot\sum_{i\le n}(1/\phi)^i\le 131$。这里代入$maxA=50$。

我们还可以确定数列的长度:$\phi^{len}\le\sum_{i\le n}\phi^iA_i$,故$len\le N+\log_{\phi}(\phi+1)maxA=61$。

复杂度是$O(N^4)$的。虽然看起来常数$\phi^3$很大,但是实际上转移的条数远远不到,按照特定的方法写是可以0.02s过的。

(upd:$c_i$貌似是不超过$50$的?

FLOWERPO

有幸和rajat1603、zhouyuchen等大神同台竞技拼手速!(并且虐他们1h+

虽然这题是水题但是也比较坑了。

考虑$C=1$的情况,令$f_{i,j}$为在$j$步以内引爆$i\dots n$的最小代价,那么显然要引爆$i$,枚举$i$最多到$k$,则

$$f_{i,j}=\min_{k>i}(A_i-A_k)^2+f_{k,j-1}$$

这个dp的复杂度是$O(N^2B)$的,实际上跑得挺快的。

考虑$C\ne 1$的情况,一个想法是:令$g_{i,j}$为$j$步之内引爆$1\dots i$的最小代价,枚举$C$点的strength$s$,设影响到的点为$[i,j]$,则$g_{j,B-1}+f_{i,B-1}+s^2$为答案。

事实上这个想法(应该)是包括我在内大多数人的第一反应,但是仔细想想会发现它其实是不对的。一个反例数据是

4 3 3
1 10 13 19

正确答案是90。13引爆10,然后10干掉全场。而上面的算法会得出答案为117。上面算法错误的原因是19没有必要被13引爆。

秉持着“大胆猜想,不用求证”的爆OJ抢一血狗的精神,我们猜测答案一定是长这样的:$C$引爆另一个点$D$,然后另一个点按照刚刚的方式引爆全场。这样只要再求一个$h_{i,j}$表示$j$步从$C$引爆$i$的最少代价,然后枚举$C$用多少步引爆$D$,枚举$D$和$D$的strength,这样复杂度正好是$O(N^2B)$的。

upd:这个题居然是全场过题人数最少。。你站药丸

MATDW

瞎几把写的。。反正我排名很垃圾。。。我可能就不太适合做cha题吧。。。

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

登录 *


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