Codechef SNACKDOWN 2016全记录

r_64 posted @ 2016年6月01日 12:26 in 未分类 with tags codechef , 1086 阅读

upd:elimination round时间居然是印度时间7:30。。我今天7:00好不容易赶到学校你就给我看这个?

不准备做凌晨的看手速的比赛了。。已GG

这篇文章停更


能走多远走多远←立了个flag,过不了初赛辣

这篇文章大概就是窝的snackdown题解。。可能会刷刷以前的snackdown的题目


5.30

怀着对cc的热爱打开了snackdown qualifier

KTTABLE

$A_i$作差分就可以得到可以使用的时间段长度,然后每个学生看一看是否可以用即可。

没看样例解释。。把题读错了。。以为学生的顺序可以动。。还wa了三发

MMSUM

$f_i$表示以$i$结尾的最大连续子段和,$g_i$表示以$i$结尾的序列中,删掉一个元素后连续子段和最大的那个和。(有点绕)

看转移:$f_i=\max(f_{i-1},0)+a_i$(众所周知)

$g_i=\max(g_{i-1}+a_i,f_{i-1})$。这个是因为这个连续子段和要么删掉了$a_i$前面的那个,要么删掉了$a_i$。

最后$ans=\max(f_i,g_i)$。

每天都有各种wa的原因。。没有把$f_n$算进答案中就wa了几回妈蛋

FDIVGAME

把SG表打出来之后,发现有规律。。都是连续的一段,分别是012301230123...,长度是:

  • 第一段的长度是1
  • 一段2的长度是前一段长度的2倍
  • 一段3的长度是前一段长度的1倍
  • 一段0的长度是前一段长度的3倍
  • 一段1的长度是前一段长度的2倍
  • 例如,开头是122330000001111111111112222222222222222222222223...

然后只有$O(\log A)$段sg值,暴力就是$O(\log A)$就可以找出一个数的sg值,总复杂度$O(TN\log A)$。

这题居然没wa。。

KGOOD

照道理说把出现次数最多的若干字母删得只剩(出现次数最少的字母的次数$+K$)次就好了。。

为什么wa我也不知道。。

弃疗了


6.5

这里是SNCKPA16

MAKEART

显然看有没有长度为$3$的连续的相同颜色子段就好。证明大概就是:如果没有的话显然最后一步不知道怎么画;如果有的话这个子段把序列分成两段,左边一段从左往右刷,右边一段从右往左刷就好。

NDIFFPAL

一个傻逼玄学题。设字符串是$a$个a$b$个b$c$个c后面$d$个不同字符的情况,显然$a,b,c\le 140$,$d\le 23$,$N=\frac{a(a+1)+b(b+1)+c(c+1)}{2}+d$。爆枚$a,b$,$c$可以由$c(c+1)\le 2N-a(a+1)-b(b+1)$算出最大的那个。检查$d\le 23$即可。很靠谱的样子。

实践是检验真理的唯一标准,这个算法对$N\le 10000$的所有数据都能出解。

GIVCANDY

其实就是,令$d=\gcd(C,D)$,答案显然等于$\min((A-B)\bmod D,(B-A)\bmod D)$。

MAKELIS

记$f(a)$为序列$a$的lis个数

我们考虑给出两个序列$a,b$,其中$b_{\min}>a_{\max}$,我们把它拼在一起的话$f(a+b)=f(a)f(b)$

给出序列$a$我们只要在后面加一段很小的长度为$lis(a)$的递增序列就可以构造出一个有$f(a)+1$个lis的序列

记$dp_{i,j}$为有$i$个lis,lis长度为$j$的最短序列长度(这个序列只是由上述两种方法构造出来的序列,不保证是全部序列中最短的),那么

$$dp_{i,j}=\min_{l|i}(dp_{k,l},dp_{i/k,j-l})$$

$$dp_{i,j}=\min(dp_{i-1,j}+j)$$

发现对于一个$i$,$\min_j dp_{i,j}$都不大(不超过70),构造方案的时候搞搞就好

其实这个转移跑的还是很快的

妈呀这个题想了我两个小时 →_→

SUBSEG2

退役这么久已经不知道线段覆盖怎么做了

对于一条线段,如果它包含了其他的线段那么这条线段显然没有什么卵用,删掉这些。

然后线段按左端点排序,右端点就也是递增的。

贪心的话就是先选最左边的,每选一个线段$[l_0,r_0]$,找出$l>r_0$的第一条线段(即$l$最小的线段)继续选即可

然后我们发现这个变成了一个树结构,就是选了一条线段之后下一条线段也就确定了,于是我们把树建出来,然后沿着$1$号节点往上跳(看深度)就是。

现在有询问了,就是首先找到$start\ge plan\_start$的最小线段然后看它有多少祖先$end\le plan\_end$就是。这个可以用倍增维护。

wa了一个小细节,改一下就过了

CHSPARR

不会做

为什么这个题过的比上一个题还多呢。。是因为cc的用户口味都比较独特么


登录 *


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