Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
字符串算法
图论
数据结构
数论、数学
动态规划
基础算法
计算几何
[其它内容]
科研笔记
归档
标签
AGC027 解题记录
解题记录
Atcoder
贪心
2019-02-18 15:01:45
370
0
1
rockdu
解题记录
Atcoder
贪心
### A Candy Distribution Again 签到贪心，就不翻译了。 ### B Garbage Collector 题意：有$n$个垃圾排在线上，$0$处是垃圾桶，你要把$n$个垃圾捡到垃圾桶里面。拿着$k$个垃圾走路走一步消耗$(k+1)^2$的代价。此外，拿起一个垃圾消耗$x$的代价，将身上的所有垃圾放入垃圾桶同样需要$x$的代价($x$给定)。问最小代价。 ~~没睡午觉的后果，这种题都做不起了~~ 题解：最优走法肯定是把垃圾分成了很多组，每一组内先走到最远的点，然后一直往回走捡垃圾捡回去。一看就知道肯定要搞个类似差分的东西。然而真的傻。贡献用坐标写出来直接消掉了，每个的贡献就是平方的差分。于是从远到近的系数是：$5,5,7,9,11,13.......$。那么我们枚举分多少段，贪心地取系数，就可以算出每种系数有多少个，从远到近分配就好了。复杂度是一个调和级数，$O(nlogn)$。 ### CDE 发现都做过 C/D都是vanif给的，E可以看一篇很好的博客： [E ABBreviate](http://blog.leanote.com/post/rockdu/0264) ### F 咕咕咕
上一篇:
TCO19 SRM 750 Div1 解题记录
下一篇:
AGC028 解题记录
0
赞
370 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
1
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册