Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
TCO19 SRM 739 Div1 解题记录
解题记录
Topcoder
构造
二分答案
贪心
2019-03-09 09:17:46
718
0
0
rockdu
解题记录
Topcoder
构造
二分答案
贪心
### Easy ForumPostEasy 题意：有一个论坛，告诉你一些文章发布的确切时间和模糊时间，让你推算当前可能的字典序最小的时间。 确切时间就是$hh:mm:ss$表示时、分、秒。 模糊时间形如： $few\ seconds\ ago$:$0s-59s$ $x\ minutes\ ago$:$x\ m-x\ m\ 59s$（$x\in [0,59]$） $x\ hours\ ago$:$x\ h-x\ h\ 59\ m\ 59 s$（$x\in [1,23]$） 注意，是字典序最小。 题解：恶心题，先把时间都按照秒算，求出可行时间区间，在这个区间内高位到低位贪心。 一个坑是时间可能跨天，比如第一天$23:00:00$的文章显示$5\ hours\ ago$那么就是第二天了，判一下就行。最好把同天和跨天的时段分开记。 ### Medium HungryCowsMedium 题意：有一个坐标轴，有$N$头牛，每头牛有一个胃口值$p_i$，表示要吃$p_i$单位的东西吃饱，牛一开始都在$0$。在坐标轴上的一些位置有一些谷仓，每头牛一单位时间可以选择移动一个单位长度或者吃一单位的东西(当前位置有谷仓)。但是一个谷仓一单位时间只能有一头牛同时吃东西。问最少多少单位时间后所有牛吃饱。$N\le 300,p_i\le 10^9$ 题解：傻逼二分，二分答案，验证就贪心让牛的胃口小的尽量塞后面。 ### Hard MakePolygon 题意：在$25\times 25$的格点上构造面积最小的$N$个点简单多边形(可以不凸) $N\le 500$ 题解：很简单就可以发现，最终的面积一定是$(N-2)/2$，考虑增量，我们每次都可以增量一个小的底边和高都为$1$的三角形。问题在于如何摆在$25\times 25$的格点里。 我的构造方法很麻烦，需要用很多组件拼出来，在我仔细查阅了google之后发现一个简单的构造方法，只需要两个组件： 以下转自kmjp's blog:  这样利用率就很高了，并且在可以增量的情况下代码难度大大降低，可以通过
上一篇:
LOJ#6289. 花朵
下一篇:
TCO19 SRM 752 Div1 解题记录
0
赞
718 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册