题意：给定一串n长度的序列(由小写字母组成)，然后进行q次询问，输入次数k和字符c，表示将序列最多替换k次字符，能够得到连续c串的长度。
思路：维护区间的l和r，不断缩放寻找解，原来这就是尺取法。
Code:
#include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; int n, q, k; char s[1505], c[5]; int main() { scanf("%d", &n); scanf("%s", s+1); scanf("%d", &q); for(int i = 1; i <= q; ++i) { scanf("%d %s", &k, c); int cnt = 0, ans = 0, l = 1, r = 0; while(1) { while(r <= n && cnt <= k) { if(s[++r] != c[0]) ++cnt; //r走到n+1时候的比较无所谓 } if(r > n) //大于n了，进行最后一次的限制来找ans { ans = max(ans, r-l); break; } ans = max(ans, r-l); while(cnt > k) { if(s[l] != c[0]) --cnt; //如果l位消耗一次k，需要进行相应的cnt-1 ++l; } } printf("%d\n", ans); } return 0; }
板子分析：
以poj-3061为例进行分析，题意：给定一个整数s，求一个长度为n的序列(所有元素均为正整数)中总和不小于s的连续子序列的长度的最小值，如果不存在，则输出0。
#include <algorithm> #include <iostream> #include <cstdio> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 100005; int n, s, t; int a[maxn]; void solve() { int ans = inf, l = 0, r = 0, sum = 0; while(1) { while(r < n && sum < s) { sum += a[r++]; } if(r >= n) { while(sum >= s) { ans = min(ans, r-l); sum -= a[l++]; } break; } while(sum >= s) { ans = min(ans, r-l); sum -= a[l++]; } } if(ans == inf) printf("0\n"); else printf("%d\n", ans); } int main() { scanf("%d", &t); while(t--) { scanf("%d %d", &n, &s); for(int i = 0; i < n; ++i) scanf("%d", &a[i]); solve(); } return 0; } 分析：尺取法就是利用两个下标(起点，终点)的不断缩放像虫子伸缩爬行一样来找出一个最优解。 步骤：首先需要找到第一次出现满足条件的末端 r 的位置，因此从0开始让虫子的头部 r 一直向前爬，尾部 l 保持不动，直到出现满足条件的时候停下，这时大家会很容易的想到这个 a[l]....a[r] 序列的前端很可能会有一些"冗余值"，即这些值去掉后，序列的总和依然大于S。这时，我们就要让虫子的尾部 l 开始移动，每次只需移动一个单位，每当尾部 l 缩进1(基本都是+1)，就需要从sum中减去相应的缩进值，并需要再次判断当前的序列和与S的关系。如果满足条件，则可以尝试更新ans，否则就会重新让虫子的头部 r 前进，直到下一次满足大于S或者r走到尽头的时候再进行操作。就是这样一伸一缩，像一个虫子一样，算法便能求出了最优解。这个算法的适用类型就是解决一些连续区间覆盖类问题。
ps：r走到尽头的判断根据不同题不同方法，只需思路明确便能找到可行的判断方法。
(分析来自http://blog.csdn.net/cumtcyf/article/details/52079488)
继续加油~
