勇攀山丘 0104 考试总结

· · 个人记录

赛前感觉：

信心爆棚！

赛后：

AFO，稳拿倒数，不是（这数据有问题吧！

估分:

A: 80 B: 50 C: 30 D:40 tot:170

A: 60 B: 10(我呸!) C:10 (呃！) D:40(嗯) tot: 120

A: 不肯多找找规律，脑袋发愣

B: 脑子爆了只会写 O(n) 的，写了个大粪，至今不知道错哪了

C: 30 分暴力打成 10 分,

D: 只会暴力

赛场:

A; 暴力,真想不到思路了（一次一次判就行了），

B: 我的思路：先把必须要要的区间求出来，在向左，如果平均值大于区间的话，那就加入要要的区间就行了，右边也是如此的话就是最优解。（真不知道哪里错了）

C:2^{40} 暴力搜索，只有十分(脑袋炸了也想不出来时间复杂度 2^{20} 三十分的暴力)

D:还是暴力，（我只配拿暴力的分

赛后

A: 听了 chy 的做法，讲的挺好，不就找规律吗，右手就行（xqy 为啥没做出来），到了一定的程度你就不用枚举，还枚举干嘛，这就能 AC，跑得挺快。

B: 听了评讲也是恍然大悟，思路也就大概是这样的：

用 f[i] 表示到第 i 个节点，而且选取这个节点，合法的一段数串的最大的平均值，用 g[i] 表示这一个合法的书穿的较小边界。

然后可以分析，每一个数串的最优值极有可能是以下两种情况之一：从这个数串开始，往前找长度为 k 的数串的平均值；f[i-1] 的数串再加上这一个。

然后，就可以转移了。

我 dp 也太逊了，想到了但没有完全想到。（有待加强）

D: 一道蓝题，有一点小难，思路是这样的吧，在补一补

首先注意到对于还没交作业的区间 [l,r]
，一定是交端点时顺便把中间交了更优，因为你交端点同时可以顺便把中间交了，但是如果先交中间则还要去端点交。
据此先将输入按 x 升序排序，设 f [i,j],0/1表示 [i,j]没交作业，剩下的都交了，当前正在交 i/j的最小时间（注意交好了），初始化 INF，

总结