Name	Code	Successful Submission	Accuracy
Chef-jumping	OJUMPS	4831	28.57
Stone	RRSTONE	3471	14.8
Compilers and parsers	COMPILER	2863	18.53
Chef and Strange Matrix	CHEFBM	1243	7.82
Little Elephant and Balloons	LEBALONS	472	10.49
Sereja and Game	SEAGM	150	13.09
Fun with AGp	FUNAGP	76	3.57
Dynamic Trees and Queries	ANUDTQ	54	4.31
Sereja and Subsegment Increasings	SEINC	43	2.7
The Malaysian Flight Search	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)就是期望次数。再乘上飞机的费用就是估价。

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

• 相关文章
• 全局相关文章