P1822 魔法指纹
2024-09-30 13:29:07
一道放在分块训练中的分块打表屑题
看了神NaCly_Fish的题解学了间隔打表(话说这么屑的东西有什么学的必要吗)
内容大多摘自大佬的题解
1,答案可递推,才适合间隔打表
什么叫可递推呢?
假设f[n]为区间[1,n]的答案,那么f[n+1]应该可以由很短的时间从f[n]推出来。满足这个条件,就可以愉快地间隔打表辣!
像这一题就是可递推的,递推式可以写成这样:
f[n] = f[n-1] + IsLucky(n);
2,间隔打表用法
个人对于区间统计问题的用法是这样的:
在这题中,记录 [1,106],[1,2*106]....[1,1000*106] 区间的答案,容易看出这是一个前缀和的形式。
当我们要计算区间 [l,r]的答案时,只需要计算 [1,r]-[1,l-1] 即可
对于 [1,a] 的答案,可以拆成两部分计算,一部分是已经搞好的前缀和,一部分暴力计算。
3,打表的间隔
根据上面一段,可以发现打表的间隔越小,运行速度就越快。
但是代码过长的话,是没办法提交的。这题单次递推的时间复杂度是Θ(logn) 的,所以打表间隔用 106 就行了。
最新文章
- html中的meta详解
- nodejs review-04
- vs2010设置断点进行调试时不起作用
- settings的保存位置
- Remove Element
- [Google Translation API v2 for Java]
- bzoj2431: [HAOI2009]逆序对数列
- 判断鼠标从哪个方向进入--jQuery
- UIWebView &; javascript
- <;script src=";xxx.php";>;<;/script>;
- Android项目中的换肤总结
- scrapy 数据存储mysql
- 【原创】大数据基础之Zookeeper(3)选举算法
- [P3676]小清新数据结构题
- 为什么二流程序员都喜欢黑php?
- sql 语句的先后执行顺序
- Linux驱动之USB(个人)
- POD类型
- Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) Volume 5. Dynamic Programming
- windows 10 WSL 安装 Centos