









codechef LTIME52
居然达成了0人AC的成就。。。虽然这不是我的本意。。。
C00K0FF
送肉题
CHEFDICE
如果存在相邻两项相同,那么答案为0,否则枚举o。一个方案o合法当且仅当:
- o是个1∼6的排列
- 对任意i,o(o(i))=i且o(i)≠i
- 对任意i,i和o(i)不能出现在序列的相邻两项
为什么呢因为你不知道骰子的滚动方向,所以top是i之后滚一步top不能是i和o(i),其他值都是可以的(你仔细想想即可)。
CHEFPCHF
这题居然只有19人AC。。?
把字符串压缩一下,对于连续的一块长为a的全0 block,如果a是偶数那么把它换成两个字符−a2,−a2,否则换成−a−12,0,−a−12。注意要特判a=1。这样压缩完的字符串由一些正字符(读进来的)和一些负字符(全0 block)和一些0组成。
然后对这个新串跑Manacher,复杂度O(K)。跑完Manacher之后很好求答案了吧。(其实有些细节。。要考虑i−ri左边和i+ri右边的连续的0)
CHEFTRAF
这题我预计的AC人数大概是2-3人。。最终0AC我也很无奈>_>。。思路其实很好想但是特别码。。。
首先肯定是树分治。我们考虑边分治,这样两棵树都需要加若干虚点不过并没有什么问题。
我们对第一棵树边分治,设重心边e的两端为集合X和Y。我们需要求出∑x∈X,y∈Ymin。
然后我们求出第二棵树上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还有我的题
2017年10月04日 10:54
办一场lunchtime有多少钱啊。 。 。
2017年10月04日 13:01
据cc官网说是350刀/场。。(然而cc发工资发的很慢