Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
字符串算法
图论
数据结构
数论、数学
动态规划
基础算法
计算几何
[其它内容]
科研笔记
归档
标签
TCO19 SRM 741 Div1 解题记录
解题记录
Topcoder
动态规划
数位dp
亚线性筛
2019-03-04 20:16:33
500
0
0
rockdu
解题记录
Topcoder
动态规划
数位dp
亚线性筛
### Easy DigitStringDiv1 题意：给一个串$s$，给定数$x$，现在擦除$s$的一些字符，问有多少种擦除方法使得$s$组成的数字严格大于$x$，擦除结果不能有前导0 题解：简单$dp$，不妨考虑算有多少比$x$小的。发现除了长度和$x$一样的情况需要讨论字典序其他情况都可以用组合数解决，枚举一个开头，然后在后面选出要擦除的数即可。对于长度相同的情况设$f(i,j,0/1)$表示$s$到第$i$个字符前，剩下的字符有$j$个，前面$j$个是否和$x$完全一样的方案。容易知道答案。 ### Medium BoardCoveringDiv1 题意：$N\times N$的网格上有一个障碍物，构造一个方法用三联通的形状(也就是小$L$形和长条形)覆盖整个图形，无解输出$-1$。$N\le 50$ 题解：等价于用很多条长度为$3$的倍数的路径覆盖。先把上下左右的行列$3$行$3$行地填满。剩下中间一坨暴力$dfs$。 ### Hard SimpleMathProblemDiv1 题意：对于整数$n$和质数$p$，设$g(n,p)=最大的p^c使p^c\le n$，设$f(n)=\sum_pg(n,p)$，求$\sum^x_{i=1}f(i)$ 题解：容易考虑到枚举倍数。 $$\sum_{i=1}\sum_{p\in Prime}\lfloor \frac{n}{p^i} \rfloor$$ 这不禁让人想到一个鬼才算法： 考虑到$\lfloor \frac{n}{p^i} \rfloor$只有$\sqrt n$段，只要对每一段求出里面有多少质数/质数的幂即可。 再进行优化：小于$n$的暴力，大于$n$的$Min\_25$。 采用$Min\_{25}$筛，复杂度很玄。 一看发现题解的做法也挺鬼才的，到处筛来筛去，但是$Min\_25$起码压了个$log$，应该可以过的。 $Min\_25$入门好题？
上一篇:
博客每周歌曲 6
下一篇:
Codecraft-18 and Codeforces Round #458 友情客串
0
赞
500 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册