由于CC的自爆，本成绩不是最终成绩（不过这成绩挺好看的不改了吧

前六道签到题不说了。

LEBLOCKS 每个颜色分别计算。同一块的很好算，不同块的爆枚中间是哪几块再乘个组合数就没了。

TWOCOMP 两条路径相交当且仅当一条路径的三个端点中至少有一个在另一条路径上。然后[tex]O(n^2 log(n))[/tex]建图流一发就没了。

SEAARC Sereja的题我居然想了一天。。。越来越弱了。

把颜色按数目分成大块和小块（我按[tex]\sqrt{n}[/tex]分的）。

对于两个大块，按顺序扫一遍，记录每个点的[tex]a,ab,aba,abab,b,ba,bab,baba[/tex]的数量[tex]O(n\sqrt{n})[/tex]

对于两个小块，把所有属于小块的点取出来扫一遍并且把每个弧塞进树状数组里统计。[tex]O(n\sqrt{n}log(n))[/tex]

对于大块和小块，处理方法和两个大块一样，只不过扫的时候在大块里二分小块元素位置。[tex]O(n\sqrt{n}log(n))[/tex]

DARTS

一开始我用贪心法刷challenge刷到0.9左右然后感觉没法优化了，感觉搞个DP有希望，就写了一个。

然后本机DP程序和贪心差不多的时候交了一发0.003，又交了一发0.004。。。。。然后我就弃疗biubiu了。

结果今天发现rejudge了。。。。这尼玛真是无语了。。。

（最后有rank4？太灵异了

说说我的做法。

首先注意到分数比较大的时候肯定是往期望得分大的地方投，所以找几个点试投一下取最高就行了。

然后就是零头的处理。

第一个想法是贪心：是1..20||25的2倍就投相应区域，否则若分数<=40投1，否则投期望分最高的。这样有0.7

然后想优化一下，分数>60投最高的，else若分数>40投（分数-40）。这样有0.9

然后感觉没办法优化了，于是写了个DP，f[i][j][k]表示剩i分投(j,k)这个点的期望次数（坐标系可以随你建）。然后取很有可能成为最优点的点多试投几次。然后若投完了以后这轮废了那么等于损失三轮。然后转移一下就好了。这样就有0.955了。由于刚开始这程序只有0.004就没有继续优化下去，然后就滚粗了。。。

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