Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
TCO19 SRM 750 Div1 解题记录
解题记录
Topcoder
二分答案
动态规划
状态压缩
2019-02-19 09:36:53
392
0
0
rockdu
解题记录
Topcoder
二分答案
动态规划
状态压缩
### Easy IdenticalBags 题意：你有$N$种糖果，第$i$种糖果有$A_i$个。你想给一些小朋友发糖果包，每个糖果包里面每种糖果的个数要一样且要装恰好$bagSize$个糖果，问最多可以分多少糖果包。$N\le 100$ 题解：二分一下分多少糖果包，整除加一下验证就好了。$O(N log N)$ ### Medium SimulateBST 题意：你有一个二叉查找树，模拟$N$个插入，输出每个点插入后的深度和。($N\le 5\times 10^5$) 题解：拿个$set$维护一下$dfs$序查前驱后继就完了，查完讨论一下哪个深度更大。$O(NlogN)$。 ### Hard PurpleSubsequences 题意：给定$L$，称含有长度恰好为$L$的上升子序列的序列为$Purple$的。对于序列$A$，统计所有$Purple$的本质不同的子序列。$L\le 6,|A|\le 60,A_i\le 20$。 题解： 本质不同这个问题可以用类似某序列自动机的思想转移，每一次转最靠前的字符。怎么记录是不是$purple$的呢？ 本来$Naive$的觉得这不随便记吗，然而…… 发现可能要记下做$lis$的整个过程，否则信息怎么都不完整…… 不过$L$才$6$，$A_i$才$20$！！！！ 考虑二分求$lis$的方法，记$x[i]$为长度为$i$的$lis$结尾可以的最小值是多少，总状态比较少，就可以过了。 $O(n^2\sum^{6}_{i=1}\binom {20} {i})$
上一篇:
TCO19 SRM 749 Div1 解题记录
下一篇:
AGC027 解题记录
0
赞
392 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册