Codechef SNACKDOWN 2016全记录

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的用户口味都比较独特么