LCA

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int N = 5e5 + ; //以后MAXN改成N。因为MAXM和MAXN不容易区分

const int M = ;

struct Edge{ int to, next; } e[N << ];

int head[N], tot, n, m, s;

int d[N], f[N][M + ]; //注意这里一定一定是M+10 

void AddEdge(int from, int to)

{

    e[tot] = Edge{to, head[from]};

    head[from] = tot++;

}

void dfs(int u, int fa) //dfs的作用是初始化f数组和d数组

{

    for(int i = head[u]; ~i; i = e[i].next)

    {

        int v = e[i].to;

        if(v == fa) continue;

        d[v] = d[u] + ;

        f[v][] = u;

        dfs(v, u);

    }

}

void init()

{

    f[s][] = s; //注意这里一定是自己的父亲为自己

    dfs(s, -);

    _for(j, , M) //注意这里是到M，不是N

        _for(i, , n)

            f[i][j] = f[f[i][j-]][j-];

}

int lca(int u, int v)

{

    if(d[u] < d[v]) swap(u, v); //u和v不要写反

    for(int j = M; j >= ; j--) //逆序

        if(d[f[u][j]] >= d[v]) //这里注意是深度的比较，u往上跳的深度和v本身的深度

            u = f[u][j];

    if(u == v) return u;

    for(int j = M; j >= ; j--)

        if(f[u][j] != f[v][j])

            u = f[u][j], v = f[v][j];

    return f[u][];

}

int main()

{

    memset(head, -, sizeof(head)); tot = ;

    scanf("%d%d%d", &n, &m, &s);

    REP(i, , n)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        AddEdge(u, v); AddEdge(v, u);

    }

    init(); //主函数里面不要忘了写

    _for(i, , m)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        printf("%d\n", lca(u, v));

    }

    return ;

}

线段树

#include<bits/stdc++.h>

#define ls (k << 1)

#define rs (k << 1 | 1)

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll; //根据题目

const int N = 2e5 + ;

struct Segment_Tree

{

    int l, r;

    ll w, f;

    int m() { return (l + r) >> ; }

    int len() { return r - l + ; };

}t[N * ];

int n, q;

inline void deal(int k, ll p)

{

    t[k].f += p;

    t[k].w += p * t[k].len();

}

inline int up(int k)

{

    t[k].w = t[ls].w + t[rs].w;

}

inline void down(int k)

{

    deal(ls, t[k].f);

    deal(rs, t[k].f);

    t[k].f = ;

}

void build(int k, int l, int r)

{

    t[k] = Segment_Tree{l, r, , };

    if(l == r) { scanf("%lld", &t[k].w); return; }

    int m = t[k].m();

    build(ls, l, m);

    build(rs, m + , r);

    up(k);

}

void add(int k, int x, ll p)

{

    if(t[k].l == t[k].r) //注意这里一定是这么写，不能写t[k].l == x，这是错的

    {

        t[k].w += p;

        return;

    }

    if(t[k].f) down(k);

    int m = t[k].m();

    if(x <= m) add(ls, x, p);

    else add(rs, x, p);

    up(k);

}

void change(int k, int L, int R, ll p)

{

    if(L <= t[k].l && t[k].r <= R) { deal(k, p); return; }

    if(t[k].f) down(k);

    int m = t[k].m();

    if(L <= m) change(ls, L, R, p);

    if(R > m) change(rs, L, R, p);

    up(k);

}

ll query(int k, int L, int R)

{

    if(L <= t[k].l && t[k].r <= R) return t[k].w;

    if(t[k].f) down(k);

    int m = t[k].m(); ll res = ;

    if(L <= m) res += query(ls, L, R);

    if(R > m) res += query(rs, L, R);

    return res;

}

int main()

{

    scanf("%d", &n);

    build(, , n);

    scanf("%d", &q);

    while(q--)

    {

        int op, x, y; ll z;

        scanf("%d", &op);

        if(op == )

        {

            scanf("%d%d%lld", &x, &y, &z);

            change(, x, y, z);

        }

        else

        {

            scanf("%d%d", &x, &y);

            printf("%lld\n", query(, x, y));

        }

    }

    return ;

}

KMP

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int N = 1e6 + ;

char a[N], b[N];

int next[N], lena, lenb;

void get_next()

{

    next[] = ; int j = ; //注意这里从0开始。因为一开始匹配了0个

    _for(i, , lenb) //这里的i从2开始

    {

        while(j && b[j + ] != b[i]) j = next[j];

        if(b[j + ] == b[i]) j++;

        next[i] = j;

    }

} 

int main()

{

    scanf("%s%s", a + , b + );

    lena = strlen(a + ); lenb = strlen(b + );

    get_next();

    int j = ;

    _for(i, , lena) //这里的i从1开始

    {

        while(j && b[j + ] != a[i]) j = next[j];

        if(b[j + ] == a[i]) j++;

        if(j == lenb) { printf("%d %d\n", i - lenb + , i); return ; }

    }

    puts("NO");

    return ;

}

同余方程

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;//如果考到数论题一定要开longlong！！！！！！！！

void exgcd(ll a, ll b, ll& d, ll& x, ll& y)

{

    if(!b) { d = a; x = ; y = ; return; }

    else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }

} 

int main()

{

    ll a, b, m;

    scanf("%lld%lld%lld", &a, &b, &m);

    ll A, B, K, d, x, y;

    A = a, B = -m, K = b;

    exgcd(A, B, d, x, y);

    if(K % d) { puts("no solution!"); return ; }

    x *= K / d; int mod = abs(B / d);

    printf("%lld\n", (x % mod + mod) % mod);

    return ;

}

同余方程组

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

void exgcd(ll a, ll b, ll& d, ll& x, ll& y)

{

    if(!b) { d = a; x = ; y = ; return; }

    else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }

} 

int main()

{

    int n;

    ll b1, b2, m1, m2;

    scanf("%d%lld%lld", &n, &b1, &m1);

    REP(i, , n)

    {

        scanf("%lld%lld", &b2, &m2);

        ll A, B, K, d, x, y;

        A = m1, B = -m2, K = b2 - b1; //推出什么写什么

        exgcd(A, B, d, x, y);

        if(K % d) { puts("no solution!"); return ; }

        x *= K / d; int mod = abs(B / d); //注意这里加abs

        x = (x % mod + mod) % mod;

        b1 = b1 + m1 * x;

        m1 = m1 * m2 / abs(d); //加abs

    }

    printf("%lld\n", b1);

    return ;

}

欧拉函数

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

ll euler(ll x)

{

    ll res = x; //注意区分res和x。x是用来取出因数的

    for(int i = ; i * i <= x; i++)

        if(x % i == )

        {

            res = res / i * (i - ); //先除后乘比较保险，可以这么做是因为i是res的因数

            while(x % i == ) x /= i;

        }

    if(x > ) res = res / x * (x - );

    return res;

}

int main()

{

    int n;

    scanf("%d", &n);

    _for(i, , n)

    {

        ll x; scanf("%lld", &x);

        printf("%lld\n", euler(x));

     }

    return ;

}

//线性求法

const int N = 1e6 + ;

int euler[N];

void get_euler()

{

    REP(i, , N) euler[i] = i;

    REP(i, , N) //注意这里i从2开始。

        if(euler[i] == i)

            for(int j = i; j < N; j += i)

                euler[j] = euler[j] / i * (i - );

}

线性筛素数

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int N = 2e7 + ;

bool is_prime[N];

vector<int> prime;

void get_prime()

{

    memset(is_prime, true, sizeof(is_prime));

    is_prime[] = is_prime[] = false;

    REP(i, , N) //切记不能越界

    {

        if(is_prime[i]) prime.push_back(i);

        REP(j, , prime.size())

        {

            if(i * prime[j] >= N) break; //切记不能越界

            is_prime[i * prime[j]] = false;

            if(i % prime[j] == ) break;

        }

    }

} 

int main()

{

    get_prime();

    int n;

    scanf("%d", &n);

    _for(i, , n)

    {

        int x; scanf("%d", &x);

        printf("%d\n", prime[x-]);

     }

    return ;

}

组合数

const int N = 1e3 + ;

int c[N][N];

void init()

{

    REP(i, , N) //从0开始

    {

        c[i][] = ;

        _for(j, , i)

            c[i][j] = c[i-][j] + c[i-][j-];

    }

}

卡特兰数

f[] = ;

REP(i, , N) f[i] = f[i-] * ( * i - ) / (i + );

巴特西

noip模板复习

LCA

线段树

KMP

同余方程

同余方程组

欧拉函数

线性筛素数

组合数

卡特兰数

最新文章

热门文章