POJ 尺取法

poj3061 Subsequence

挑战P146。题意：给定长度为n的数列整数a0,a1,...,a(n-1)以及整数S，求出总和不小于S的连续子序列的长度的最小值，如果解不存在，则输出零。$10<n<10^5,0<a_i<=10^4,S<10^8$;

思路：尺取法，设起始下标s，截止下标e，和为sum，初始时s=e=0;若sum<S，将sum增加a(e),并将e加1，若sum>=S,更新t-s，并将sum减去a(s)，sj增加1，再和S比较，重复该步骤，直接附上书上代码

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int main(){

    int x,a[100005];

    cin>>x;

    while(x--){

      int s=0,t=0,sum=0,S,n,ans;

      cin>>n>>S;

      ans=n+1;

      for(int i=0;i<n;i++)

        cin>>a[i];

      for(;;){

        while(t<n&&sum<S){

            sum+=a[t++];

        }

        if(sum<S)

            break;

        ans=min(ans,t-s);

        sum-=a[s++];

      }

      if(ans>n)

        cout<<0<<endl;

      else cout<<ans<<endl;

    }

}

poj2566 Bound Found

题目链接：http://poj.org/problem?id=2566

题意：已知一个长度为n的整数序列和非负数t，求该序列中一个连续的子序列，使其和的绝对值最接近t，输出该序列的左右下标；

这题是《挑战》上尺取法部分的习题，暴力肯定会T，开始觉得尺取法不可做，看了下题解发现自己还是太菜了，稍微变下形就不会了，，，，

尺取法一般数列都是有序的，给的数列不是有序的，只要求出他们的前缀和再排个序就变成有序的了，用了一个结构体z[i]保存前缀和信息，z[i].x表示前i个数的和，由于排序后i会变化，故z[i].y记录初始的i，排序后即可使用尺取法更新最接近t值得左右下标，讲的应该比较清楚了哦->_->

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

int n,k,a[100005];

struct Z{

int x;

int y;

}z[100005];

bool cmp(Z a,Z b){

return a.x<b.x;

}

int main(){

    while(scanf("%d%d",&n,&k)&&(n!=0||k!=0)){

          z[0].x=z[0].y=0;

          for(int i=0;i<n;i++){

            scanf("%d",&a[i]);

            z[i+1].x=z[i].x+a[i];

            z[i+1].y=i+1;

          }

    sort(z,z+n+1,cmp);

    for(int i=0;i<k;i++){

            int p;int s=0,t=1,temp,minn=0x3f3f3f3f,l,r,ans;

        scanf("%d",&p);

          while(s<=n&&t<=n){

             temp=z[t].x-z[s].x;

            if(abs(temp-p)<minn){

               minn=abs(temp-p);

               l=z[t].y;

               r=z[s].y;

               ans=temp;

            }

               if(temp>p)

                  s++;

               else if(temp<p)

                  t++;

               else break;

               if(s==t)

                 t++;

          }

    printf("%d %d %d\n",ans,min(l,r)+1,max(l,r));

    }

    }

}

poj2100 Graveyard Design

题目链接：http://poj.org/problem?id=2100

题意：已知一个数n，问是否存在一个连续的自然数序列使他们的平方和为n，按序列长度从大到小输出序列的长度和整个序列

尺取法，和poj3061基本一样，由于输出要求，只要用个结构体记录下长度和起始下标即可。

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

struct Z{

long long int x,y,z;

}z[1000005];

int main(){

long long int ans=0,S,s=1,t=1,sum=0;

cin>>S;

for(;;){

    while(sum<S){

        sum+=t*t;

        t++;

    }

    if(sum==S){

        z[ans].x=t-s;

        z[ans].y=s;

        z[ans].z=t-1;

        ans++;

    }

    sum-=s*s;

    s++;

    if(s*s>S)  break;

}

if(ans==0)

    cout<<0<<endl;

    else {

        cout<<ans<<endl;

        for(int i=0;i<ans;i++){

            cout<<z[i].x<<" ";

            int j;

            for( j=z[i].y;j<z[i].z;j++)

                cout<<j<<" ";

            cout<<j<<endl;

        }

    }

}

poj2739 Sum of Consecutive Prime Numbers

题目链接： http://poj.org/problem?id=2739

题意：已知一个数n,(2<=n<=10000);若n能表示成若干个连续的素数的和，则称n为consecutive prime numbers，问n有多少种表示方法；

思路：先将n以内的数筛选法打个素数表，再用尺取法判断即可；

#include<cstdio>

#include<iostream>

using namespace std;

int prime[10005],ans[10005]={0},is_prime[10005];

int main(){

 int p=0;

 for(int i=0;i<=10000;i++)

    is_prime[i]=1;

 is_prime[1]=is_prime[1]=0;

 for(int i=2;i<=10000;i++){

    if(is_prime[i]){

        prime[p++]=i;

        for(int j=2*i;j<=10000;j+=i)

            is_prime[j]=false;

    }

 }

 int s=0,t=0,sum=0;

 for(;;){

    while(t<10000&&sum<=10000){

        sum+=prime[t++];

        ans[sum]++;

    }

      sum=0;s++;t=s;

      if(prime[s]>10000)

         break;

  }

 int n;

 while((cin>>n)&&n!=0){

    cout<<ans[n]<<endl;

 }

}

巴特西

POJ 尺取法

poj3061 Subsequence

poj2566 Bound Found

poj2100 Graveyard Design

poj2739 Sum of Consecutive Prime Numbers

最新文章

热门文章