尺取法

2019-07-27

CSDN迁移

POJ 3061 Subsequence

给出一个序列,求区间和大于或者等于S的最短区间长度。n<=1e5


方法一:预处理前缀和数组,二分答案
时间复杂度:O(nlogn)足够解决题目了但是想想其他办法


方法二:尺取法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
const int maxn=1e5+100;
using namespace std;
int a[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
int n,s;
while (t--){
cin >> n >> s;

for (int i=1;i<=n;i++) cin >> a[i];
int l,r,sum;
l = r = 1;sum =0;
int ans = n+1;
for (;;){
while (r <= n && sum <s) {
sum+=a[r++];
}
if (sum < s ) break;
ans = min(ans,r-l);
sum -=a[l++];
}

if (ans == n+1) cout << 0 << endl;
else cout << ans << endl;
}
return 0;
}

POJ 3320 Jessica’s Reading Problem

一本书上有一些知识点,每一页上恰好有一个知识点,同一个知识点可能出现在多个页上,询问阅读一段连续区间页覆盖所有知识点。(p<=1e6)


用一个set求出总知识点的个数,用map维护知识点,注意L处删的知识点R要后移到这个知识点找到的位置。
这道题提交的过程着实令人自闭,最后过的方法是把外层定义的map和set放到main函数里面来定义,卡常…我服了。
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <map>
#include <set>
const int maxn=1e6+100;
using namespace std;
int a[maxn];


int main(){
map <int,int> count;
set <int> all;
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i=1;i<=n;i++) {
cin >> a[i];
all.insert(a[i]);
}
int tot = all.size();

int l = 1,r = 1,num = 0;
int ans = n;
for(;;){
while (r <= n && num < tot){
if (count[a[r++]]++ == 0)
num ++;
}
if (num < tot) break;
ans = min(ans,r-l);
if (--count[a[l++]]==0) num--;
}

cout << ans;
}

HihoCoder - 1722 最小差值

给定N个数组,每个数组都包含M个整数。
现在你被要求从每个数组中选出一个数,总共N个数,然后求出其中最大与最小的差值。
在M*N种选法中,差值最小是多少?
Input
第一行包含两个整数N和M。
以下N行,每行包含M个整数。
对于50%的数据,1 ≤ N × M ≤ 10000
对于100%的数据,1 ≤ N × M ≤ 200000 0 ≤ 每个整数 ≤ 1000000
Output
最小的差值
Sample Input
3 3
8 1 6
3 5 7
4 9 2
Sample Output
2


惊奇的发现可以把所有数先放在一起排序,然后尺取法,像上面那一题一样建模,很适配的解决问题了。非常漂亮。

洛谷 P1638 逛画展

建个模又和上面一样,就很简单。

UVA 11572 Unique Snowflakes

题意:求没有重复数字的最长区间.。
满足尺取法的性质证明:当L一路增加的时候,R不可能减小。所以尺取法,一旦发现了重复数字,L就++到重复数字消失,R向前开过去。用个map存一下数字的个数就完事了。

Atcoder 4142 Xor Sum 2

题意:求区间[l,r]的对数,使得A[l] xor A[l+1] xor … xor A[r] = A[l] + A[l+1] + … +A[r]。
其实 A XOR B <=A + B,所以取等的情况一定是每一位上至多出现一次一,考虑一下尺取法,当L增加,R不可能减小吗?其实是必然可以减小,而且如果(L,R)可行,那必然X取小于R的(L,X)都必然成立,所以一旦找到了(L,R),可以O(1)算出以L为起点的。再仔细考虑一下尺取法。
每一次我们延伸 R 的时候,判断 now xor a[r] 和 now+a[r] 是否相等,如果相等就继续将 R 向右移动,否则停止.对于这一个 L ,答案的个数就是 R-L ,因为l→r−1 中任意取一个位置 都是符合条件的。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
可以看到上面的条件是r<=n.
这个代码其实是枚举了r,尺取了l的位置,所以每一次将r++以后更新答案.
*/
for (int l=1,r=1,now=0;r<=n;){
for (;!(now&a[r])&&r<=n;){
/*now & a[r] = 0即now ^ a[r] = now + a[r]*/
now|=a[r++];
ans+=r-l;
}
now^=a[l++];
}
/*如果用上面说的方法代码是这样的.*/
for (int l=1,r=1,now=0;l<=n;){
for (;r<=n&&(now^a[r])==now+a[r];) now^=a[r++];
ans+=r-l,now^=a[l++];
}

部分内容参考自洛谷日报