POJ 尺取法

poj3061 Subsequence

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

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

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

#include
#include
#include
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>a[i];
      for(;;){
        while(tn)
        cout<<0<

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
#include
#include
#include
using namespace std;
int n,k,a[100005];
struct Z{
int x;
int y;
}z[100005];
bool cmp(Z a,Z b){
return a.xp)
                  s++;
               else if(temp

poj2100 Graveyard Design 
题目链接：http://poj.org/problem?id=2100
题意：已知一个数n，问是否存在一个连续的自然数序列使他们的平方和为n，按序列长度从大到小输出序列的长度和整个序列
尺取法，和poj3061基本一样，由于输出要求，只要用个结构体记录下长度和起始下标即可。

#include
#include
#include
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(sumS)  break;
}
if(ans==0)
    cout<<0<

poj2739 Sum of Consecutive Prime Numbers 
题目链接： http://poj.org/problem?id=2739
题意：已知一个数n,(2<=n<=10000);若n能表示成若干个连续的素数的和，则称n为consecutive prime numbers，问n有多少种表示方法；
思路：先将n以内的数筛选法打个素数表，再用尺取法判断即可；

#include
#include
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<