尺取法
尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的
时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案。
使用尺取法时应清楚以下四点：
1、 什么情况下能使用尺取法? 2、何时推进区间的端点？ 3、如何推进区间的端点？ 3、何时结束区间的枚举？
尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步得到根据其端点得到，那么尺取法便是不可行的。首先，明确题目所需要求解的量之后，区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。
总结：尺取法的模型便是这样：根据区间的特征交替推进左右端点求解问题，其高效的原因在于避免了大量的无效枚举，其区间枚举都是根据区间特征有方向的枚举，如果胡乱使用尺取法的话会使得枚举量减少，因而很大可能会错误，所以关键的一步是进行问题的分析
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, s,a[N];
int main(){
int t;
cin >> t;
while (t--)
{
scanf("%d%d", &n,&s);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int st = 1, en = 1;
int tot = 0;
int ans = n+10;
while (1)
{
while (en <= n&&tot < s)
tot += a[en++];
if (tot < s)
break;
ans = min(ans, en - st);
tot -= a[st++];
}
if (ans == n + 10) printf("0\n");
else
printf("%d\n", ans);
}
return 0;
}
POJ 3320 Jessica's Reading Problem
求最小的页数覆盖所有知识点
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
const int N = 1e6 + 10;
int n,a[N];
set<int> s;
map<int, int> cnt;
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]),s.insert(a[i]);
int sum = s.size();
int st = 1, en = 1, tot = 0;
int ans = n;
while (1)
{
while (en <= n&&tot < sum){
if (cnt[a[en]] == 0){
tot++;
}
cnt[a[en++]]++;
}
if (tot < sum) break;
ans = min(ans, en - st);
--cnt[a[st]];
if (cnt[a[st++]] == 0) tot--;
}
printf("%d\n", ans);
return 0;
}
POJ 2566 Bound Found
给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小，如果存在多个，任意解都可行。
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e9 + 10;
int n,k,t,a[N];
typedef pair<int, int> P;
P s[N];
int main()
{
while (scanf("%d%d", &n, &k) && (n || k))
{
s[0] = P(0, 0);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
s[i] = P(a[i] + s[i - 1].first, i);
}
sort(s, s + n + 1);//保证0在负数后面，即开始就出现正数，负数的话会一直更新en++
while (k--)
{
scanf("%d", &t);
int st = 0, en = 1, minv = INF,l=1,r=n,ans=s[1].first;
while (en <= n)
{
int sum = s[en].first - s[st].first;
if (abs(sum - t) < minv){
minv = abs(sum - t);
l = s[st].second, r = s[en].second;
ans = sum;
}
if (sum == t)
break;
else if (sum < t){
en++;
}
else{
st++;
}
if (st == en) en++;
}
if (l>r) swap(l, r);
printf("%d %d %d\n", ans, l+1, r);
}
}
return 0;
}
//poj2739
#include <cstdio>
#include <algorithm>
#include <cstring>
#include<iostream>
#define INF 0x3f3f3f3f
#define LL long long
#define N 10100
using namespace std;
int prime[N], tot;
bool vis[N];
int n;
void get_prime(int n)
{
memset(vis, true, sizeof(vis));
for (int i = 2; i <= n; i++)
{
if (vis[i]){
prime[++tot] = i;
for (int j = i + i; j <= n; j += i){
vis[j] = false;
}
}
}
}
int main()
{
get_prime(10090);
while (scanf("%d", &n) && n)
{
int st = 1, en = 1,sum=0,ans=0;
while (1)
{
while (sum < n&&prime[en] <= n) sum += prime[en++];
if (sum == n) ans++;
if (sum<n) break;
sum -= prime[st++];
}
printf("%d\n", ans);
}
return 0;
}
//poj2100
#include <cstdio>
#include <algorithm>
#include <cstring>
#include<iostream>
#include<vector>
#define INF 0x3f3f3f3f
typedef long long ll;
#define N 10100
using namespace std;
typedef pair<ll, ll> P;
vector<P> ans;
ll n;
int main()
{
while (cin >> n)
{
ans.clear();
ll st = 1, en = 1;
ll sum = 0;
while (1)
{
while (sum < n&&en*en <= n)
sum += en*en,en++;
if (sum == n){
ans.push_back(P(st, en));
}
if (sum < n)
break;
sum -= st*st;
st++;
}
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++)
{
P t = ans[i];
printf("%lld", t.second - t.first);
for (ll j = t.first; j < t.second; j++)
printf(" %lld", j);
printf("\n");
}
}
return 0;
}
评论