快读模板

这个连算法都算不上。。。

inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}

二分查找

这是我学过的第一个算法qwq

sort(a+1, a+1+n);
bool Find(int x) {  //二分查找x在a中是否出现 
    int l = 1, r = n, mid;
    while(l <= r) {
        mid = (l+r)>>1;
        if(x == a[mid]) return 1;
        if(x < a[mid]) r = mid - 1;
        else l = mid + 1;
    }
    return 0;
}

二分答案

bool check() {
    
}
int main()
{   
    // 单调递增答案 使最大值最小 
    int l = (), r = (), mid, ans;
    while(l <= r) {
        mid = (l+r)>>1;
        if(check()) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    printf("%d\n",ans);
    // 单调递减答案 使最小值最大 
    int l = (), r = (), mid, ans;
    while(l <= r) {
        mid = (l+r)>>1;
        if(check()) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return 0;
}

离散化

const int N = 1e6+7;
int n;
int a[N],t[N];
int main()
{
    n = read();
    for(int i=1;i<=n;++i)
        t[i] = a[i] = read();   //t[] 是临时数组 
    sort(t+1, t+1+n);
    int m = unique(t+1, t+1+n) - (t+1);
    for(int i=1;i<=n;++i)
        a[i] = lower_bound(t+1, t+1+m, a[i]) - t;
    for(int i=1;i<=n;++i)
        printf("%d ",a[i]); //离散化后数组 
    return 0;
}

ST表 & 倍增一般算法

const int N = 100007;
int n,m;
int lg[N];
int f[N][30];   //f[i,j]表示 [i - 2^j]区间的最大值
void RMQ() {
    for(int j=1;j<=21;++j)
        for(int i=1;i<=n;++i) if(i+(1<<j)-1 <= n) {
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
}
inline int Query(int l,int r) {
    int k = lg[r-l+1];
    return max(f[l][k], f[r-(1<<k)+1][k]);
}
int main()
{
    n = read(), m = read();
    for(int i=1;i<=n;++i)
        f[i][0] = read();
    RMQ();
    for(int i=2;i<=n;++i)
        lg[i] = lg[i>>1] + 1;
    while(m--) {
        int l = read(), r = read();
        printf("%d\n",Query(l,r));
    }
    return 0;
}

KMP

什么？？ 我已经不记得KMP的思想了！！？？

const int N = 1000007;
int kmp[N];
char a[N],b[N];
int main()
{
    cin>>a+1>>b+1;
    int la = strlen(a+1), lb = strlen(b+1);
    int j = 0;
    for(int i=2;i<=lb;++i) {
        while(j && b[i]!=b[j+1]) j = kmp[j];
        if(b[i] == b[j+1]) ++j;
        kmp[i] = j; 
    }
    j = 0;
    for(int i=1;i<=la;++i) {
        while(j && a[i]!=b[j+1]) j = kmp[j];
        if(a[i] == b[j+1]) ++j;
        if(j == lb) printf("%d\n",i-lb+1), j = kmp[j];
    }
    for(int i=1;i<=lb;++i)
        printf("%d ",kmp[i]);
    return 0;
}

Dfs(有向图)

int vis[N];
void Dfs(int u/*,,,其他状态*/) {
    vis[u] = 1; /*其他初始化*/
    for(int i=head[u];i;i=edge[i].next /*其他状态转移*/) {
        int v = edge[i].to;
        if(!vis[v] /*&& 其他限制条件*/) {
            //搜索 / 操作 
            Dfs(v);
            //回溯 
        }
    }
}

Bfs(有向图)

int vis[N];
void Bfs(/*传入条件*/) {
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(1); vis[1] = 1; /*其他初始化*/
    while(!q.empty()) {
        int u = q.front(); q.pop(); //或是其他结构体（状态空间） 
        for(int i=head[u];i;i=edge[i].next) {
            int v = edge[i].to;
            if(!vis[v]) {
                /*其他操作*/ vis[v] = 1; q.push(v);
            }
        }
    }
}

并查集

const int N = 1e5+7;
int n,m;
struct UnionFind {
    int pre[N];
    void Init() {
        for(int i=1;i<=n;++i) pre[i] = i;
    }
    int Find(int x) {
        return x==pre[x]?x:pre[x] = Find(pre[x]);
    }
    void join(int x,int y) {
        int fx = Find(x), fy = Find(y);
        if(fx != fy) pre[fx] = fy;
    }
}B;

树状数组

const int N = 500007;
int n,m;
struct Tree_A { //树状数组 
    int c[N];
    void Add(int x,int y) {
        while(x<=n) c[x]+=y, x+=x&-x;
    }
    int Sum(int x) {
        int res = 0;
        while(x>0) res += c[x], x-=x&-x;
        return res;
    }
    inline int Query(int x,int y) {
        return Sum(y) - Sum(x-1);
    }
}T;