Processing math: 67%

codechef LTIME52

r_64 posted @ 2017年9月30日 18:28 in 未分类 with tags codechef , 1457 阅读

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

C00K0FF

送肉题

CHEFDICE

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

  • o是个16的排列
  • 对任意io(o(i))=io(i)i
  • 对任意iio(i)不能出现在序列的相邻两项

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

CHEFPCHF

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

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

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

CHEFTRAF

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

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

我们对第一棵树边分治,设重心边e的两端为集合XY。我们需要求出xX,yYmin

然后我们求出第二棵树上X\cup Y的虚树,并对这个虚树搞边分治。设重心边e'两端的集合为X',Y',我们实际上要求\sum_{x\in X',y\in Y'}\min(dis_1(x,y),dis_2(x,y))。然而这两个dis都可以写成简单的形式,设xe的距离为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还有我的题

 

上原步子 说:
2017年10月04日 10:54

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

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

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


登录 *


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