10
1
2017
2

codechef LTIME52

居然达成了0人AC的成就。。。虽然这不是我的本意。。。

C00K0FF

送肉题

CHEFDICE

如果存在相邻两项相同,那么答案为$0$,否则枚举$o$。一个方案$o$合法当且仅当:

  • $o$是个$1\sim 6$的排列
  • 对任意$i$,$o(o(i))=i$且$o(i)\ne i$
  • 对任意$i$,$i$和$o(i)$不能出现在序列的相邻两项

为什么呢因为你不知道骰子的滚动方向,所以top是$i$之后滚一步top不能是$i$和$o(i)$,其他值都是可以的(你仔细想想即可)。

CHEFPCHF

这题居然只有19人AC。。?

把字符串压缩一下,对于连续的一块长为$a$的全0 block,如果$a$是偶数那么把它换成两个字符$-\frac{a}{2},-\frac{a}{2}$,否则换成$-\frac{a-1}{2},0,-\frac{a-1}{2}$。注意要特判$a=1$。这样压缩完的字符串由一些正字符(读进来的)和一些负字符(全0 block)和一些$0$组成。

然后对这个新串跑Manacher,复杂度$O(K)$。跑完Manacher之后很好求答案了吧。(其实有些细节。。要考虑$i-r_i$左边和$i+r_i$右边的连续的$0$)

CHEFTRAF

这题我预计的AC人数大概是2-3人。。最终0AC我也很无奈>_>。。思路其实很好想但是特别码。。。

首先肯定是树分治。我们考虑边分治,这样两棵树都需要加若干虚点不过并没有什么问题。

我们对第一棵树边分治,设重心边$e$的两端为集合$X$和$Y$。我们需要求出$\sum_{x\in X,y\in Y}\min(dis_1(x,y),dis_2(x,y))$。

然后我们求出第二棵树上$X\cup Y$的虚树,并对这个虚树搞边分治。设重心边$e'$两端的集合为$X',Y'$,我们实际上要求$\sum_{x\in X',y\in Y'}\min(dis_1(x,y),dis_2(x,y))$。然而这两个$dis$都可以写成简单的形式,设$x$到$e$的距离为$dep_1(x)$,到$e'$的距离为$dep_2(x)$,则我们要求的是$\sum_{x\in X',y\in Y'}\min(w(e)+dep_1(x)+dep_1(y),w(e')+dep_2(x)+dep_2(y))$。这个。。随便什么数据结构维护一波就好。

复杂度$O(n\log^3 n)$。我写了6K 176行,tester写了300+行还被我卡常数了(捂脸

后记

窝现在其实已经被算设作业日死了。。这个时间的LTIME锅我想都没想就接了。。结果傻逼了。。。(说起来我这两天还感冒

第四题还说要卡骗分。。最终没卡因为我也不知道有什么骗分。。然而这届选手不给力,骗分都写不出。。。(←说得好像你写得出骗分一样

感觉除了第四题以外难度控制得还不错?要感谢admin。。本来CHEFDICE是第一题,第二题是一个提高组难度的题。。后来admin说第二题要simple(而不是easy)于是我们就把难度降了一波。。。

但是cc有一点让我很不能忍。。就是权限控制做得特别差。。比赛的前48分钟都是看不到第二题的图片的(只有管理员能看到)。。导致第二题前期的解决人数特别少。。还要感谢xellos爸爸及时救场。。。关于这个权限控制的话,各种editorial里面solution看不到甚至比赛过程中翻译看不到。。已经被人诟病很久了吧。。cc这方面真的需要改进啊。。。。

然后。。。我可能已经没力气在上学的时候出比赛了。。还是放假的时候出比较爽。(然而这是个flag,NOV17还有我的题

 

Category: 未分类 | Tags: codechef | Read Count: 50
上原步子 说:
2017年10月04日 17:54

办一场lunchtime有多少钱啊。 。 。

Avatar_small
r_64 说:
2017年10月04日 20:01

据cc官网说是350刀/场。。(然而cc发工资发的很慢


登录 *


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