迟取法

http://www.cnblogs.com/shuzy/p/3812924.html

就是两个指针表示区间[l,r]的开始与结束然后根据题目来将端点移动,是一种十分有效的做法。适合连续区间的问题

3320

这道意思是一本书有n页,每一页上有一个知识点标号a[i]可能重复,要求选择一个最小的区间使得能够覆盖所有知识点

分析:[l,r]区间推进,统计区间中能够覆盖的知识点数,对于每一个l,r都是满足可以覆盖所有知识点的最小r,处理好区间知识点数的统计就好了

复制代码

复制代码

2566

给你一个数组(可为负数)m次询问,每次询问一个区间使得区间和的绝对值最接近给定的值,有多种随意输出一种

分析:预处理前缀和sum[i]这样可以O(1)查询区间和,然后sum数组从小到大排序(因为abs(sum[i]-sum[j])=abs(sum[j]-sum[i])所以顺序不影响答案,但可以方便尺取)然后就是O(n)推进,每次有最小值是更新答案区间信息就可以了

复制代码

复制代码

2739

给你一个数,询问有多少个连续质数序列和等于该数例如53=5 + 7 + 11 + 13 + 17 

分析:筛法求质数,然后直接twopoint就可以了,统计可以相等的个数

复制代码

复制代码

2100

给你一个数,询问有多少种连续自然数的平方和等于这个数,输出所有可能

分析:由上面的基础很简单了,对于每个数枚举区间,求和,推进区间,如果可以的话将区间记录最后输出就可以了,注意使用long long ,复杂度O(1e7)

复制代码

复制代码

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz