常用技巧

二分查找

二分查找有64种写法。

对其进行分类：
取整方式：向下取整，向上取整（共2种）
区间开闭：闭区间，左闭右开区间，左开右闭区间，开区间（共4种）
问题类型：
①对于不下降序列a，求最小的i，使得a[i]=key
②对于不下降序列a，求最大的i，使得a[i]=key
③对于不下降序列a，求最小的i，使得a[i]>key
④对于不下降序列a，求最大的i，使得a[i]<key
⑤对于不上升序列a，求最小的i，使得a[i]=key
⑥对于不上升序列a，求最大的i，使得a[i]=key
⑦对于不上升序列a，求最小的i，使得a[i]<key
⑧对于不上升序列a，求最大的i，使得a[i]>key（共8种）
综上所述，二分查找共有64种写法。
对于不下降序列a，n为序列a元素的个数，key为关键字。

1.求最小的i，使得a[i]=key，若不存在，则返回-1

int search1(int a[],int n,int key){
    int m,l=0,r=n-1;//闭区间[0,n-1]
    while(l<r){
        m=l+((r-l)>>1);//向下取整
        if(a[m]<key)l=m+1;
        else r=m;
    }
    if(a[r]==key)return r;
    return -1;
}

2.求最大的i，使得a[i]=key，若不存在，则返回-1

int search2(int a[],int n,int key){
    int m,l=0,r=n-1;//闭区间[0,n-1]
    while(l<r){
        m=l+((r+1-l)>>1);//向上取整
        if(a[m]<=key)l=m;
        else r=m-1;
    }
    if(a[l]==key)return l;
    return -1;
}

3.求最小的i，使得a[i]>key，若不存在，则返回-1

int search3(int a[],int n,int key){
    int m,l=0,r=n-1;//闭区间[0,n-1]
    while(l<r){
        m=l+((r-l)>>1);//向下取整
        if(a[m]<=key)l=m+1;
        else r=m;
    }
    if(a[r]>key)return r;
    return -1;
}

4.求最大的i，使得a[i]<key，若不存在，则返回-1

int search4(int a[],int n,int key){
    int m,l=0,r=n-1;//闭区间[0,n-1]
    while(l<r){
        m=l+((r+1-l)>>1);//向上取整
        if(a[m]<key)l=m;
        else r=m-1;
    }
    if(a[l]<key)return l;
    return -1;
}

• 对于3、4，也可以先判断是否存在，再进行二分查找。

快速幂

//快速幂模板 （a^b）mod p
int power(int a,int b,int p){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=(long long)ans*a%p;
        a=(long long)a*a%p;
    }
    return ans;
}

尺取法

• 例题（模板题）：poj3061
  描述
  给出N个正整数（10<N<100000）的序列，每个正整数小于或等于10000，并且给出正整数S（S<100000000）。编写程序以找到序列的连续元素的子序列的最小长度，其总和大于或等于S。
  输入
  第一行是测试用例的数量。对于每个测试用例，程序必须从第一行读取数字N和S，以间隔分隔。序列的编号在测试用例的第二行中给出，以间隔分开。输入将以文件结尾结束。
  输出
  对于每种情况，程序必须在输出文件的单独行上打印结果。如果没有答案，则打印0。
  样例输入
  2
  10 15
  5 1 3 5 10 7 4 9 2 8
  5 11
  1 2 3 4 5
  样例输出
  2
  3

参考代码：

#include<bits/stdc++.h>
#define N 100000+10
using namespace std;

int a[N];
int ans,s,n;

void solve(){
    ans=N; 
    int l=1,r=1,cnt=0,tt=0;

    while(r<=n){
        while(cnt<s&&r<=n){
            cnt+=a[r];
            r++;tt++;
        }

        while(cnt>=s){
            cnt-=a[l];
            l++;t++;
        }
        ans=min(ans,tt+1);
    }
}

int main(){
    int t,cnt;
    cin>>t;

    while(t--){
        cin>>n>>s;cnt=0;
        bool flag=false;

        for(i=1;i<=n;i++){
            cin>>a[i];cnt+=a[i];
            if(cnt>=s&&!flag)flag=true;    
        }

        if(!flag){
           cout<<'0'<<endl;continue;
        }

        solve();cout<<ans;
    }
    return 0;
}