尺取法学习笔记
什么是尺取法
Codeforces 中显示它的算法名称叫做 "two pointers"
直译成中文的话叫双指针法
这个算法 hin 有意思，由于在某些巨佬眼中过于简单，以至于都没把尺取法当成一个算法
如何进行尺取法
尺取法的思想是维护两个指针 \(l,r\)? ，分别为左端点与右端点，每当确定左端点时，尝试将右端点一直移动，直到不满足条件为止
，让我们来看这一道例题
P1638 逛画展
求刚好有 \(m\) 种数字的最短区间
我们发现，当这个区间的左端点向右移动时，右端点一定不会向左移动，所以我们在枚举 \(r\) 时，不需要从 \(l\) 开始枚举，我们可以从上一次枚举到的 \(r\) 开始枚举
我们记录一个 \(cnt\) 数组， \(cnt_i\) 表示第 \(i\) 种数字在 \(l \sim r-1\) 这个区间内的出现次数
用一个变量 \(sum\) 来表示这个区间不同画的数量
维护一下，即可AC
具体细节见代码：
#include
using namespace std;
const int N=1e6+7,MAX=2e3+7;
int a[N];
int cnt[MAX];
int n,m;
int ansl,ansr=N; // 初始化区间长度为最长
signed main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",a+i);
for(int l=1,r=1,sum=0;l<=n;) {
while(r<=n && sum 习题：
UVA11572 唯一的雪花 Unique Snowflakes
求没有重复数字的最长区间
与第一题思路类似，由于值域范围较大，我使用的是 set 维护
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+7;
set s;
int a[N];
int T,n,ans;
signed main() {
scanf("%d",&T);
for(;T;--T) {
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",a+i);
s.clear(); // 清空
ans=-inf;
for(int l=1,r=1;l<=n;) {
while(s.find(a[r])==s.end() && r<=n)
s.insert(a[r]),++r; // 移动右端点指针
ans=max(ans,r-l); // 计算答案
s.erase(a[l]);
++l; // 移动左端点
}
printf("%d\n",ans);
}
return 0;
}
AT4142 [ARC098B] Xor Sum 2
求有多少个区间 \([l,r]\) ，满足 \(a_l \ xor \ a_{l+1} \ xor \dots xor \ a_r = a_l + a_{l+1} + ... +a_r\)
注意到一个性质，当 \(a \ and \ b=0\) 时，\(a \ xor \ b=a+b\)?
那么 \(l \sim r\) 所有数的异或值等于所有数的和,必须要每一个二进制位上该区间所有数加起来最多只有一个 \(1\) 才行.
直接用尺取法做，记得开 long long
#include
typedef long long ll;
using namespace std;
const int N=2e5+7;
int a[N];
ll ans;
int n;
signed main() {
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",a+i);
for(int l=1,r=1,tmp=0;r<=n;) {
while(!(tmp&a[r]) && r<=n) { // tmp&a[r]!=0,则tmp^a[r]!=tmp+a[r]
tmp+=a[r],++r; // 移动右端点指针
ans+=r-l; // 统计答案
}
tmp^=a[l],++l; // 移动左端点指针
}
printf("%lld",ans);
return 0;
}
P3143 [USACO16OPEN]Diamond Collector S
求最长的两端不相交的区间，每个区间的极差不大于 \(k\)
本题我们可以用尺取法做
要求区间互不相交，我们统计答案就要变成左端点前的最大区间+当前区间
#include
#include
using namespace std;
const int N=5e4+7;
int a[N];
int c[N];
int k;
int n,ans;
signed main() {
scanf("%d%d",&n,&k);
for(ll i=1;i<=n;++i)
scanf("%d",a+i);
sort(a+1,a+1+n); // 因为放置与顺序无关,所以我们可以先排序,使得相邻两数之差变小
for(int l=1,r=2,maxx=-1;l<=n;) {
while(a[r]-a[l]<=k && r<=n)
++r; // 移动右端点指针
c[r]=max(c[r],r-l); // 记录以r为右端点向左可以扩展的最大区间
maxx=max(maxx,c[l]); // 更新之前的最长区间
ans=max(ans,maxx+(r-l)); // 更新答案为之前的最长区间+当前区间
++l;
}
printf("%d",ans);
return 0;
}