尺取法通常是指对数组保存一对下标(起点、终点),然后根据实际情况交替推进两个端点直到得出答案的方法。

POJ 3320

题目地址:http://poj.org/problem?id=3320

题目大意

为了准备考试,Jessica开始读一本很厚的课本。想要通过考试就要把课本的知识点都掌握。

这本书有P页,第i页恰好有一个知识点$a_i$(每一个知识点都有一个整数编号),书中同一个知识点可能多次提到,所以她希望通过阅读其中连续的一些页把所有知识点都覆盖到。给定每页提到的知识点,求出最少需要阅读的页数。

思路

这题因为不注意知识点编号范围(32位)导致Runtime error到死。。。改用map来统计遇到过的知识点次数就可以过了。。

首先t从第一页开始阅读,遇见新知识点就更新变量crtsum用来记录当前遇到过的知识点总数,若遇见新知识点就令ans=t-s。然后前面的变量s($s < t$)往后检查,若已知遇到过的知识点多于一次(即重复出现),那么s就往后挪,遇到过的知识点就-1,然后更新t-s,求出最小值即可。

AC代码

/*************************************************************************
    > File Name: 3320.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-29 二 14:58:10 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

int P;
int id[1000000+50];
map<int, int> cnt;

void solve() {
    int s = 0, t = 0;
    int ans = P;
    int lstsum = 0, crtsum = 0;
    while(t < P) {
        if(cnt[id[t++]]++ == 0) ++crtsum; // 遇见新知识点

        if(crtsum > lstsum) { // 那么就要更新ans了。
            ans = t - s;
            lstsum  = crtsum;
            // printf("%d\n", ans);
        }

        while(s < t && cnt[id[s]] > 1) cnt[id[s++]]--; // 检查前面是否有重复出现过的知识点,最后更新最小ans
        ans = min(ans, t-s);

    }
    cout << ans << endl;
}

int main() {
#ifdef Oj
    freopen("3320.in", "r", stdin);
#endif
    scanf("%d", &P);
    for (int i = 0; i < P; ++i) scanf("%d", &id[i]);
    solve();
    return 0;
}

POJ 2566

题目地址:http://poj.org/problem?id=2566

题目大意

给$N$个整数(有负数= =),以及一个$t$值,问连续子序列和的绝对值最接近$t$的值是多少,以及上下标。

思路

这题WA了好多遍。。是University of Ulm Local Contest 2001的一道只有一个队过的变态题,我将数据从上面下下来磨了好久才磨出来,最后居然只是因为上下标求错了一直WA

刚开始求连续子序列和的绝对值无解,因为有负数,子序列和的绝对值不单调。所以需要标记下前缀和,并排个序,然后用尺取法磨出来,注意上下标。。

看了一下那个队的代码,放到POJ上面居然超时= =这是亮点:

//Schranken.
for (int i=0; i<10000; i++)
{
    int u=rand()%n+1;
    int l=rand()%u;
    double d = fabs(fabs(partsum[u]-partsum[l])-t);
    if (d<best) {
        bestl=l;
        bestu=u;
        best=d;
    }
}
//

随机大法好啊。。

AC代码

/*************************************************************************
    > File Name: 2566.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-29 二 19:34:57 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <ctime>
#include <algorithm>
using namespace std;

int N, K;
pair<int,int> sum[100005]; // index->presum, value->id;
int T;


void solve() {
    sort(sum, sum+1+N); // 排个序使sum单调

    for (int i = 0; i < K; ++i) {
        scanf("%d", &T);
        int s = 0, t = 1; // (s, t]
        int l = sum[s].second, u = sum[t].second; // 这里是巨坑啊。初始化不应该用0和1
        if(l > u) swap(l, u);
        int S = sum[t].first - sum[s].first; // a[1]
        int res = S;
        int delta = abs(S - T);
        for(;;) {
            // printf("S:%d l: %d u: %d\n", S, l, u);
            while(t < N && S < T) {
                S = sum[++t].first - sum[s].first;
                if(delta > abs(S - T)) {
                    delta = abs(S-T);
                    l = sum[s].second;
                    u = sum[t].second;
                    if(l > u) swap(l, u);
                    res = S;
                }
            }
            if(S < T) break;


            if(t-s>1) {
                S = sum[t].first - sum[++s].first;
                if(delta > abs(S - T)) {
                    delta = abs(S-T);
                    l = sum[s].second;
                    u = sum[t].second;
                    if(l > u) swap(l, u);
                    res = S;
                }
            }
            else S = numeric_limits<int>::min(); // 当t-s<=1的时候就应该轮到t前进了
        }
        printf("%d %d %d\n", res, l+1, u);
    }
}

int main() {
#ifdef Oj
    freopen("2566.in", "r", stdin);
#endif
    while(scanf("%d%d", &N, &K)==2) {
        if(N == K && K == 0) break;
        int d;
        sum[0] = make_pair<int, int>(0, 0);
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &d);
            sum[i] = make_pair<int, int>(sum[i-1].first+d, i); // sum[k]=a[1]+a[2]+...+a[k]
        }
        solve();
    }
    return 0;
}

POJ 2739

题目地址:http://poj.org/problem?id=2739

题目大意

给你一个数$N$,问有多少组连续素数和等于该数。例如20就有两组(7+13和3+5+5+7)。

思路

这题比较简单了。先打表求出连续素数的前缀和,然后尺取法求即可。(用二分搜索也可以。)

AC代码

/*************************************************************************
    > File Name: 2739.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-31 四 14:16:15 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int N;
vector<int> prime_sum;

void solve() {
    int s=0, t=0, sum = 0, ans = 0;

    for(;;) {
        while(t+1<prime_sum.size() && sum < N)
            sum = prime_sum[++t] - prime_sum[s];
        // printf("prime_sum[%d]:%d prime_sum[%d]:%d sum:%d\n", s, prime_sum[s], t, prime_sum[t], sum);

        if(sum < N) break;
        if(sum == N) ++ans; // 求得一组
        sum = prime_sum[t] - prime_sum[++s];
    }
    printf("%d\n", ans);
}

int main() {
#ifdef Oj
    freopen("2739.in", "r", stdin);
#endif
    prime_sum.push_back(0);
    for(int i=2; i<=10000; ++i) {
        int j;
        for (j = 2;  j * j <= i; j++) if(i%j == 0) break;
        if(j * j > i) prime_sum.push_back(prime_sum.back()+i); // 连续素数前缀和
    }

    while(scanf("%d", &N) == 1 && N)
        solve();
    return 0;
}

POJ 2100

题目地址:http://poj.org/problem?id=2100

题目大意

问一个数$N(1\leq N \leq 10^{14})$的连续数的平方和为$N$有几种?

思路

坑死了,题目蛮简单的,被高精度坑死了。。刚开始用前缀和搞,加到$10^{14}$就停下来了,这样的后果就是完全忽略了后面的数了。

AC代码

/*************************************************************************
    > File Name: 2100.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-31 四 15:17:01 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
ll N;
struct grave {
    int l, r;
    grave(int l, int r) : l(l), r(r) {}
    bool operator<(const grave & b) const {
        return r - l > b.r - b.l;
    }
};
vector<grave> graves;

void solve() {
    int s, t;
    ll sum = 0;
    s = t = 0;
    graves.clear(); // 注意清零。。
    for(;;) {
        while(ll(t)*t <= N && sum < N) { // 注意t范围
            ++t;
            sum += ll(t)*t;
        }
        if(sum < N) break;

        if(sum == N) graves.push_back(grave(s, t));
        ++s;
        sum -= ll(s)*s;
    }

    sort(graves.begin(), graves.end());
    printf("%lu\n", graves.size());
    for(int i=0; i<graves.size(); ++i) {
        int s = graves[i].l;
        int t = graves[i].r;
        printf("%d", t-s);
        for(int j=0; j<t-s; ++j) printf(" %d", s+j+1);
        printf("\n");
    }
}

int main() {
#ifdef Oj
    // freopen("2100.in", "r", stdin);
#endif
    while(scanf("%lld", &N) == 1) solve();
    return 0;
}