Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
字符串算法
图论
数据结构
数论、数学
动态规划
基础算法
计算几何
[其它内容]
科研笔记
归档
标签
TCO19 SRM 747 Div1 解题记录
解题记录
Topcoder
线段树
动态规划
搜索
2019-02-25 07:59:43
348
0
0
rockdu
解题记录
Topcoder
线段树
动态规划
搜索
### Easy MostFrequentLastDigit 题意：构造一个长为$n$的数列，满足两两的和$mod\ 10$为$d$的整数对唯一最多，不能有一样多的。要求每个数都不一样，不超过$10^9$且不能被$10$整除。$n\le 200$ 题解：直接找两个数$x+y=d(mod\ 10), x\le 10, y\le 10$一个一半就行了。左右两边选自己要除以$2$，但是左右各一个选出$d$是直接相乘，一定更大。 ### Medium TieForMax 题意：有$t$张牌和$p$个开始时是空的格子。每一次会随机选择一个格子放一张牌，问最后最大的堆有多个的概率是多少。 $t,p\le 50$ 题解：直接枚举拆分数，对每个$t$的拆分用组合数计算答案。 总复杂度$O(t的整数拆分\times p)$。 ### Hard RochesterSequence 题意：称一个数列是好的当且仅当长度$l$为偶数且：定义第$i$个数和$n-i+1$的和为$a_i$，$a_i$不下降。 现在有一个数列$b_i$，问最多保留多少个数使它变为好的，并且输出方案数。 $n\le 1000,a_i\le 10^9$ 题解：有一个很显然的$O(n^4)$的$DP$。直接记忆化搜索就行了。$f(l,r)$表示$l-r$的数列最后选的$l,r$的最优解。 但是要优化，我们改成朴素区间$dp$。 先将每一个数对按$(b_i+b_j,j-i+1)$排序，因为永远只能从$b_i+b_j$小的转向$b_i+b_j$大的。剩下的每一次转移相当于矩形求最值，用一个维护一下最值以及最值个数就好了。 最终复杂度$O(n^2log^2n)$
上一篇:
TCO19 SRM 746 Div1 解题记录
下一篇:
TCO19 SRM 751 Div1 解题记录
0
赞
348 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册