[CodeChef]2014 May Challenge

xllend3 posted @ 2014年5月11日 13:42 in 刷比赛记录 with tags codechef , 1021 阅读
Name Code Successful Submission Accuracy
Chef-jumpingSolved OJUMPS 4831 28.57
StoneSolved RRSTONE 3471 14.8
Compilers and parsersSolved COMPILER 2863 18.53
Chef and Strange MatrixSolved CHEFBM 1243 7.82
Little Elephant and BalloonsSolved LEBALONS 472 10.49
Sereja and GameSolved SEAGM 150 13.09
Fun with AGpSolved FUNAGP 76 3.57
Dynamic Trees and QueriesSolved ANUDTQ 54 4.31
Sereja and Subsegment IncreasingsSolved SEINC 43 2.7
The Malaysian Flight SearchSolved ANUMFS 35 0.94

Chef-jumping 签到题

Stone 签到题

Compilers ans parsers 签到题

Chef ans Strange Matrix 签到题

Little Elephant and Ballons 签到题

Sereja and Game

第一问对每个质数算出可以整除多少数,然后乱搞一通。

第二问f[i][j]表示取了i个gcd是j,暴力O(n^4)转移即可过。

Fun with Agp

用一个线段树维护区间和(两个质数分开算)和标记。维护S和D的话合并的时候直接加比较方便。

修改一个数的时候直接改,没什么难度。

这道题最kenji的地方就是有好几个特判,一个是质数==2的时候没有逆元,还有一个是R%p==1的时候是等差数列。

刚开始只注意到R==1,没发现R%p==1也要特判调了一天。。。。

DynamicTrees and Queries

Splay维护DFS序。

Sereja ans Subsegment Increasings

先差分,然后答案就是正数的和。然后每次可以给一段数±4,那么会导致差分后一个数+=4,一个数-=4。然后统计一下差分后每种数字的个数乱搞一发就好了。

The Malaysian Flight Search(Challenge)

最后两个乱搞哥成功获取了数据,拿到了1分。。。然后其他人看上去只有0分了。。。但是名次还是有的。

我的做法是随机选点,然后对每个飞机估价。首先算出每个飞机能覆盖到多少节点,设为p%。那么期望能使点减少成(1-p^2-(1-p)^2)。于是-1/log(1-p^2-(1-p)^2)就是期望次数。再乘上飞机的费用就是估价。

不过我的最高分是第一次的提交(就是随机点的提交)。。。后来再怎么优化都比第一次差。然后就弃疗了。

 

Avatar_small
__Shi 说:
2014年5月11日 13:46

跪跪跪跪跪跪跪


登录 *


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