尺取

尺取的时候一定要满足"单调性",就是

单调性就是比如区间取和我在右边界向右延伸的过程中整个区间和是不断增大的不会变小不然右侧就不会延伸反而右边会向回收缩，这样的话就会造成一种很混乱的局面

例一:

JES读一本书，要看完所有的知识点，这本书共有P页，第i页恰好有一个知识点ai，（每一个知识点都有一个整数编号）。全书同一个知识点可能会被提到多次，他希望阅读其中一些连续的页把所有知识点都读到，给定每页所读到的知识点，求最少的阅读页数 .

Input

第一行一个整数为书页数P，第二行P个整数为每页的知识点，每个数字表示一个知识点，保证每个ai在int范围内。

Output

输出最少阅读页数。

Sample Input

5
1 8 8 8 1

Sample Output

2

这个题就是尺取的时候用map标记一下个数就行
set有去重的作用

#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<map> 
using namespace std;
const int maxn=1e6+100;

int a[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)){
        set<int>se;
        map<int,int>mp;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            se.insert(a[i]);
        }
        int nn=se.size();
        int l=1,r=1;
        int s=0;
        int ans=1e9;
        while(1){
            while(r<=n&&s<nn){
                if(mp[a[r]]==0){
                    s++;    
                }
                mp[a[r]]++;
                r++;
            }
            if(s<nn){
                break;
            }
            ans=min(ans,r-l);
            mp[a[l]]--;
            if(mp[a[l]]==0){
                s--;
            }
            l++;
        }
        printf("%d
",ans);
    }
}

例二：

从数列中找出连续序列，使得和的绝对值与目标数之差最小

Input

多组用例，每组用例第一行两个整数n和m分别表示数列长度和查询次数，第二行为n个整数表示数列，第三行为m个整数表示目标数，以n=k=0结束输入 0<=t<=1000000000;1<=n<=100000Output

对于每次查询，输出三个整数sum,l,r，分别表示其绝对值与目标数之差最小的连续序列值与此连续序列的左右端点Sample Input

5 1
-10 -5 0 5 10
3
10 2
-9 8 -7 6 -5 4 -3 2 -1 0
5 11
15 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
15 100
0 0

Sample Output

这个题直接尺取的话不行，因为他不满足单调性,所以要找一个前缀和

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100; 
int v[maxn];
struct node{
    int sum;
    int id;
}a[maxn];
bool cmp(node x,node y){
    return x.sum<y.sum;
}
int main(){
    int n,m;
    while(cin>>n>>m){
        if(n+m==0){
            break;
        }
        a[0].sum=a[0].id=0;
        for(int i=1;i<=n;i++){
            cin>>v[i];
            a[i].sum=a[i-1].sum+v[i];
            a[i].id=i;
        }
        sort(a,a+n+1,cmp);
        int k;
        for(int i=1;i<=m;i++){
            scanf("%d",&k);
            int l=0;
            int r=1;
            int mi=0x3f3f3f3f;
            int ans,ansl,ansr;
            while(r<=n){
                int sub=a[r].sum-a[l].sum;//这里是前缀和所以后面要加一 
                if(abs(sub-k)<mi){
                    mi=abs(sub-k);
                    ansl=min(a[l].id,a[r].id)+1;
                    ansr=max(a[l].id,a[r].id);
                    ans=sub;
                }
                if(sub<k){
                    r++;
                } 
                else if(sub>k){
                    l++;
                }
                else{
                    break;
                }
                if(l==r){
                    r++;
                }
            }
            cout<<ans<<" "<<ansl<<" "<<ansr<<endl;
        }
    } 
    
}

例三：


我们都知道数字是个好玩意，那么我们想知道一个数字能是否能用若干个（或许是一个）连续的素数之和表示，并且想知道有多少种方法。例如，53 有两种表示方法 5 + 7 + 11 + 13 + 17 和 53。 现在给你一个整数 n，你要告诉他这个数字有多少种不同的连续素数和表示方式。Input多组数据输入，每行一个数字 n，当 n=0 时结束。 n 在 2 与 10000之间。Output每个输出占一行，输出对应的答案。Sample Input

Sample Output

1
1
2
3
0
0
1
2
这个还行打个标就行

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e4+100;
int prime[maxn];
int biaoji[maxn];
int vis[1000001];
int sum[maxn];
int cnt=0;
void inint(){
    for(int i=2;i<maxn;i++){
        if(!biaoji[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<maxn;j++){
            biaoji[i*prime[j]]=1;
            if(i%prime[j]==0){
                break;
            }
        }
    }
}
int main(){
    inint();
    for(int i=1;i<=cnt;i++){
        sum[i]=sum[i-1]+prime[i];
    }
    for(int i=0;i<=cnt;i++){
        for(int j=i+1;j<=cnt;j++){
            int t=sum[j]-sum[i];
            if(t<maxn)
                vis[t]++;
        }
    }
    int n;
    while(cin>>n&&n){
        cout<<vis[n]<<endl;
    }
}

sj学姐发现自己的裙子上有一个由n个数组成的数组，恰巧sj学姐的幸运数字是s，sj学姐想求出总和不小于s的子数组长度的最小值，但sj学姐太忙了，帮sj学姐解决这个问题。

Input

第一行输入n和s，第二行输入n个正整数。

Output

找到满足要求的子数组的最小长度，如果没有，输出0。

Sample Input

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Sample Output

2
3

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
int a[maxn];
int main(){
    int t,n,m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int l=1;
        int r=1;
        int sum=0;
        int ans=0x3f3f3f3f;
        while(1){
            while(sum<m&&r<=n){
                sum+=a[r];
                r++;
            }
            if(sum<m){
                break;
            }
            ans=min(ans,(r-l));
            sum-=a[l];
            l++;
        }
        if(ans>n){
            ans=0;
        }
        cout<<ans<<endl;
    }
}

月光女神是创界山最美的守护神。暗黑达垂涎女神的美色。不择手段想要得到女神的芳心！月光女神不堪其扰。干脆设立了一个结界。只有拥有大智慧的人才能通过结界去见女神一面。暗黑达虽然力量强大无比，但脑子不好使，他一直也没能见到女神。现在你能帮小渡见到女神么？
结界给出一个数n。你要求一段连续的数，这些数的平方和等于n。Input输入一个整数n，1<=n<=10^14;Output输出一个数k，k为解的个数。接下来的k行为解，每一行的解要先输出这个解中包含的数字个数，然后从小到大输出解中包含的数字。解的输出顺序要按照所包含的数字个数降序排列。Sample Input

Sample Output

2
4 21 22 23 24
3 25 26 27

满足2030的解有2个 第一个解包含4个数 分别是 21 22 23 24。21^2+22^2+23^2+24^2=2030。
第二个解包含3个数 分别是 25 26 27。25^2+26^2+27^2=2030。



这个直接尺取就行

#include<iostream>
#include<algorithm>
#include<math.h> 
using namespace std;
typedef long long ll;
const int maxn=1e6+100; 
ll k;
int LL[maxn],RR[maxn];
int main(){
    while(~scanf("%lld",&k)){
        ll l=1,r=1;
        ll len=sqrt(k*1.0)+1;
        ll sum=0;
        int cnt=0;
        while(l<=len){
            while(r<=len&&sum<k){
                sum+=r*r;
                r++;
            }
            if(sum==k){
                LL[++cnt]=l;
                RR[cnt]=r-1;
            }
            sum-=l*l;
            l++;
        } 
        cout<<cnt<<endl;
        for(int i=1;i<=cnt;i++){
            printf("%d ",RR[i]-LL[i]+1);
            for(int j=LL[i];j<=RR[i];j++){
                printf("%d ",j);
            }
            cout<<endl;
        }
    }
}



传送门
有包含n个数的序列a，求能找到最长的区间包含不超过k个不同的元素。Input

第一行包含两个整数 n, k (1 ≤ k ≤ n ≤ 5·10⁵)

第二行包含 n个整数a_i (0 ≤ a_i ≤ 10⁶) —代表数组 a中的元素.

Output

输出两个整数l, r (1 ≤ l ≤ r ≤ n) — 代表最长区间的左端点和右端点。如果有多个答案，输出任意一组即可。a中元素的位置从1到n进行编号。

Examples

Input

5 5
1 2 3 4 5

Output

1 5

Input

9 3
6 5 1 2 3 2 1 4 5

Output

3 7

Input

3 1
1 2 3

Output

1 1

#include<iostream>
#include<algorithm>
#include<set>
#include<map> 
using namespace std;
const int maxn=1e6+100;
int a[maxn];
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        map<int,int>mp;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        int l=1,r=0;
        int LL,RR;
        int num=0;
        int ans=-1;
        while(1){
            while(r<=n&&num<=m){
                r++;
                if(mp[a[r]]==0){
                    num++;  
                }
                mp[a[r]]++;
            }
            if((r-l+1)>ans){
                ans=(r-l+1); 
                LL=l;
                RR=r;
            }
            
            if(num<=m){
                break;
            }
            
            mp[a[l]]--;
            if(mp[a[l]]==0){
                num--;
            }
            l++;
        }
        cout<<LL<<" "<<RR-1<<endl;
    }
}