尺取法（2019.5.3训练）

本次训练共5题，本文附AC代码和题目链接。

牛客网 Wannafly挑战赛23 A题 字符串

题意：给定一个只含小写字母的字符串，使得其包含26个小写字母，求最短的子串长度。

#include <bits/stdc++.h>
using namespace std;
string a;
int l,r,sum,ans,vis[130];//ASCII码总共127个
int main()
{
    ios::sync_with_stdio(false);
    cin>>a;ans=0x3f3f3f3f;
    for(l=0,r=0;r<a.length();r++)//尺取法，O(n)算法
    {
        vis[a[r]]++;
        if(vis[a[r]]==1)sum++;
        if(sum<26)continue;
        while(l<r&&vis[a[l]]>=2){vis[a[l]]--;l++;}
        ans=min(ans,r-l+1);
    }
    printf("%d\n",ans);
    return 0;
}

poj 3061 Subsequence

题意：给定一个序列，使得其和大于或等于S，求最短的子序列长度。

#include <iostream>
using namespace std;
int l,r,n,s,t,ans,sum,a[100010];
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>s;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        ans=0x3f3f3f3f;sum=0;
        for(l=1,r=1;r<=n;r++)//尺取法
        {
            sum=sum+a[r];
            if(sum<s)continue;
            while(l<r&&sum-a[l]>=s){sum=sum-a[l];l++;}
            ans=min(ans,r-l+1);
        }
        if(ans==0x3f3f3f3f)ans=0;
        cout<<ans<<endl;
    }
    return 0;
}

poj 3320 Jessica’s Reading Problem

题意：一本书有P页，每一页有一个知识点，求去最少的连续页数覆盖所有的知识点。

#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
map<int,int>vis;
int l,r,n,sum,ans,tmps,a[1000010];
inline int read()//用快读329ms，不用快读954ms
{
    int s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
    return s*f;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        vis[a[i]]++;
        if(vis[a[i]]==1)sum++;
    }
    vis.clear();
    ans=0x3f3f3f3f;
    for(l=1,r=1;r<=n;r++)
    {
        vis[a[r]]++;
        if(vis[a[r]]==1)tmps++;
        if(tmps<sum)continue;
        while(l<r&&vis[a[l]]>=2){vis[a[l]]--;l++;}
        ans=min(ans,r-l+1);
    }
    cout<<ans<<endl;
    return 0;
}

poj 2739 Sum of Consecutive Prime Numbers

题意：问一个数拆成几个连续素数的和的方案总共多少种。

#include <iostream>
#include <cstring>
using namespace std;
const int N=1e4+5;
int l,r,n,len,tmp,cnt,sum,ans,prime[N],pre[N];
bool flag[N];
void get_prime()//素数筛打表
{
    memset(flag,1,sizeof(flag));
    flag[1]=cnt=0;
    for(int i=2;i<=N;i++)
    {
        if(flag[i])
        {
            prime[++cnt]=i;
            pre[i]=cnt;//pre[i]记录i这个数是第几个素数，如果不是素数则为0
        }
        for(int j=1;j<=cnt&&prime[j]*i<=N;j++)
        {
            flag[prime[j]*i]=0;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    get_prime();
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        for(int i=n;i>=2;i--)//小于等于n的最大素数是第len个素数
        {
            if(pre[i])
            {len=pre[i];break;}
        }
        ans=sum=0;
        for(l=1,r=1;r<=len;r++)
        {
            sum=sum+prime[r];
            if(sum<n)continue;
            if(sum==n)ans++;
            while(l<r&&sum>n)
            {
                sum=sum-prime[l];l++;
                if(sum==n){ans++;break;}
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

poj 2100 Graveyard Design

题意：找到某一个区间使得区间内的数的平方和等于某一给定值k。

#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
struct node
{
    ll d,l,r;
}p[10010];
ll n,sum,l,r,cnt,len;
int main()
{
    scanf("%lld",&n);
    len=(ll)sqrt(n);
    for(l=1,r=1;r<=len;r++)
    {
        sum=sum+r*r;
        if(sum<n)continue;
        if(sum==n)
        {
            cnt++;
            p[cnt].l=l;
            p[cnt].r=r;
            p[cnt].d=r-l+1;
        }
        while(l<r&&sum>n)
        {
            sum=sum-l*l;l++;
            if(sum==n)
            {
                cnt++;
                p[cnt].l=l;
                p[cnt].r=r;
                p[cnt].d=r-l+1;
                break;
            }
        }
    }
    printf("%lld\n",cnt);
    for(ll i=1;i<=cnt;i++)
    {
        printf("%lld ",p[i].d);
        for(ll j=p[i].l;j<=p[i].r;j++)
            printf("%lld ",j);//poj竟然不卡输出格式，多打一个空格也不会PE
        printf("\n");
    }
    return 0;
}