这个技巧常用在求解连续序列里的一些信息，并且在求这些信息的过程，要使这些信息在序列里具有单调性，具体做法通常是指对数组保存一对下标（起点，终点），然后根据实际情况交替推进两个端点得出答案。比如poj3061求出总和不小于S的连续子序列的长度的最小值。 然后这个算法就像一本尺子一样保持一个宽度，从左往右扫一遍这个序列。
Subsequence poj3061
#include<cstdio>#include<algorithm>using namespace std;const int N=100000+10;int a[N];int main(){ int T;scanf("%d",&T); while(T--){ int n,s;scanf("%d %d",&n,&s); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int ans=n+1,i=0,j=0,sum=0; for(;;){ while(sum<s&j<n){ sum+=a[++j]; } if(sum<s) break; ans=min(ans,j-i); sum-=a[++i]; } if(ans==n+1) ans=0; PRintf("%d/n",ans); }Jessica’s Reading poj3320
#include<set>#include<map>#include<cstdio>using namespace std;set<int>cou;map<int,int>num;//知识点->出现次数的映射int a[1000000+10];int main(){ int n; while(~scanf("%d",&n)){ num.clear();cou.clear(); for(int i=0;i<n;i++){ int x;scanf("%d",&a[i]); } for(int i=0;i<n;i++){ cou.insert(a[i]); } int l=0,r=0,t=0,ans=n; //尺取法求解 for(;;){ while(r<n&&t<cou.size()){ if(num[a[r++]]++==0) t++; } if(t<cou.size()) break; ans=min(r-l,ans); if(--num[a[l++]]==0) t--; } printf("%d/n",ans); }}poj2566（变形的尺取法） 题意： 给你一个序列，k次询问每次给一个数，问序列里那段区间和的绝对值最接近询问的数。
思路：很容易想到预处理一个前缀和，但是前缀和不单调，所以需要先排个序。之后就是尺取法了：首尾分别逐步向前挪动，挪动过程中记录答案。
代码：
#include<cstring>#include<cstdio>#include<algorithm>using namespace std;typedef pair<int,int>P;P p[100000+10];int main(){ int n,t; while(~scanf("%d%d",&n,&t)&&n&&t){ p[0]=P{0,0}; int sum=0; for(int i=1;i<=n;i++){ int a;scanf("%d",&a); sum+=a; p[i]=P{sum,i}; } sort(p,p+n+1); for(int i=0;i<t;i++){ int x;scanf("%d",&x); int l=0,r=1,num=0,ans=0x7fffffff,ansl=0,ansr=0; while(l<n&&r<=n){ int tem=p[r].first-p[l].first; if(abs(tem-x)<abs(ans-x)){ ans=tem;ansl=p[l].second;ansr=p[r].second; } if(tem==x) break; else if(tem<x) r++; else l++; if(l==r) r++; } if(ansl>ansr) swap(ansl,ansr); printf("%d %d %d/n",ans,ansl+1,ansr); } }}poj2739 题意：给你一个数，判断能不能由一段连续素数和构成。 先打一个素数表，再尺取法。
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=10000+10;bool prime[maxn];int num[1500],t;void solve(){ memset(prime,true,sizeof(prime)); prime[0]=prime[1]=false; for(int i=2;i<=sqrt(maxn)+1;i++){ if(prime[i]){ for(int j=i*2;j<=10000;j+=i){ prime[j]=false; } } } t=0; for(int i=2;i<=10000;i++){ if(prime[i]) num[t++]=i; }}int main(){ solve(); int n; while(scanf("%d",&n)&&n){ int ans=0,l=0,r=0,tem=0; for(;;){ while(tem<n&&num[r]<=n){ tem+=num[r++]; } if(tem==n) ans++; tem-=num[l++]; if(l==r) break; } printf("%d/n",ans); }}poj2100 和上一题类似，问一个数能不能由一段来连续的序列平方和构成。
#include<cstdio>using namespace std;typedef long long ll;int main(){ ll n; while(~scanf("%lld",&n)){ ll ans=0,l=1,r=1,num=0; for(;;){ while(num<n&&r*r<=n){ num+=r*r; r++; } if(num==n) ans++; if(l*l>=n) break; num-=l*l;l++; } printf("%lld/n",ans); num=0;l=1;r=1; for(;;){ while(num<n&&r*r<=n){ num+=r*r; r++; } if(num==n){ printf("%lld",r-l); for(int i=l;i<r;i++) printf(" %d",i); printf("/n"); } if(l*l>=n) break; num-=l*l;l++; } }}这个技巧大概的模板
for(;;){ while(...&&r<n){//满足的条件 } if() ..... if(尺取结束条件) break; l++;}新闻热点
疑难解答
