正文

OI 常用模板 手写

IP云
IP云V管理员/1 阅读
12/02
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

线性筛素数

(例题 洛谷P3383) 
bool p[50000010];

int cnt = 0;

int prime[10000010];

inline void init()

{

    int N = 50000010;

    p[0] = p[1] = 1;

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

    {

        if(!p[i]) prime[++cnt] = i;

        for(int j = 1; j <= cnt && prime[j] * i <= N; ++j )

        {

            p[prime[j] * i] = 1;

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

        }

    }

}

乘法逆元

(例题 洛谷P3811)

公式 : 

#include <bits/stdc++.h>

long long a[3000001];

int n,p;

int main()

{

    a[1] = 1;

    scanf("%d%d",&n,&p);

    printf("1\n");

    for(int i = 2; i <= n; i++ )

    {

        a[i] = (long long)((p - (p / i)) * a[p % i]) % p;

        while(a[i] < 0)a[i] += p;

        printf("%d\n",a[i]);

    }

    return 0;

}

网络最大流

(例题P3376)(dinic算法) 
#include <bits/stdc++.h>

struct Edge

{

    int to,next,cap;

}edge[200010];

const int inf = 1 << 29;

int head[10010],d[10010];

int cnt;

int n,m,s,t,maxflow;

std::queue<int> q;

inline void add_edge(int u,int v,int cap)

{

    cnt++;

    edge[cnt].to = v;

    edge[cnt].cap = cap;

    edge[cnt].next = head[u];

    head[u] = cnt;

}

bool bfs()

{

    memset(d, 0, sizeof(d));

    while(!q.empty())q.pop();

    q.push(s);

    d[s] = 1;

    while(q.size())

    {

        int x = q.front();

        q.pop();

        for(int i = head[x]; i; i = edge[i].next)

        {

            if(edge[i].cap > 0 && d[edge[i].to] == 0)

            {

                q.push(edge[i].to);

                d[edge[i].to] = d[x] + 1;

            }

        }

    }

    return d[t];

}

int dinic(int x, int flow)

{

    if(x == t || flow == 0)return flow;

    int rest = flow, k;

    for(int i = head[x]; i && rest; i = edge[i].next)

    {

        if(edge[i].cap > 0 && d[edge[i].to] == d[x] + 1)

        {

            k = dinic(edge[i].to, std::min(rest, edge[i].cap));

            if(!k)d[edge[i].to] = 0;

            edge[i].cap -= k;

            edge[i ^ 1].cap += k;

            rest -= k;

        }

    }

    return flow - rest;

}

int main()

{

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

    scanf("%d%d", &s, &t);

    cnt = 1;

    for(int i = 1; i <= m; i++)

    {

        int u, v, c;

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

        add_edge(u, v, c);

        add_edge(v, u, 0);

    }

    int flow = 0,now = 0;

    while(bfs())

    {

        while(flow = dinic(s, inf))maxflow += flow;

    }

    printf("%d", maxflow);

    return 0;

}

欧拉函数 
void getphi()

{

    phi[1] = 1;

    for(int i = 2; i <= n; i++)

    {

        if(!p[i])

        {

            prime[++cnt] = i;

            phi[i] = i - 1;

        }

        for(int j = 1; j <= cnt; j++)

        {

            if(i * prime[j] > n)break;

            p[i * prime[j]] = 1;

            if(i % prime[j] == 0)

            {

                phi[i * prime[j]] = phi[i] * prime[j];

                break;

            }

            else phi[i * prime[j]] = phi[i] * (prime[j] - 1);

        }

    }

}

拓展欧几里得 
inline void exgcd(long long a,long long b,long long &x,long long &y)

{

    if(b == 0)

    {

        x = 1, y = 0;

        return;

    }

    exgcd(b, a % b, y, x);

    y -= (a / b * x);

}

Dijkstra + 堆优化

(例题P4779) 
#include<bits/stdc++.h>

const int MaxN = 100010, MaxM = 500010;

struct edge

{

    int to, dis, next;

};

edge e[MaxM];

int head[MaxN], dis[MaxN], cnt;

bool vis[MaxN];

int n, m, s;

inline void add_edge( int u, int v, int d )

{

    cnt++;

    e[cnt].dis = d;

    e[cnt].to = v;

    e[cnt].next = head[u];

    head[u] = cnt;

}

struct node

{

    int dis;

    int pos;

    bool operator <( const node &x )const

    {

        return x.dis < dis;

    }

};

std::priority_queue<node> q;

inline void dijkstra()

{

    dis[s] = 0;

    q.push( ( node )

    {

        0, s

    } );

    while( !q.empty() )

    {

        node tmp = q.top();

        q.pop();

        int x = tmp.pos, d = tmp.dis;

        if( vis[x] )

            continue;

        vis[x] = 1;

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

        {

            int y = e[i].to;

            if( dis[y] > dis[x] + e[i].dis )

            {

                dis[y] = dis[x] + e[i].dis;

                if( !vis[y] )

                {

                    q.push( ( node )

                    {

                        dis[y], y

                    } );

                }

            }

        }

    }

}

int main()

{

    memset( dis, 0x3f, sizeof( dis ) );

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

    for( register int i = 0; i < m; ++i )

    {

        register int u, v, d;

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

        add_edge( u, v, d );

    }

    dijkstra();

    for( int i = 1; i <= n; i++ )

        printf( "%d ", dis[i] );

    return 0;

}

二分图匹配

(例题P3386) 
#include <bits/stdc++.h>

const int MaxN = 1010, MaxM = 500010;

struct edge

{

    int to,next;

}e[MaxM << 1];

int head[MaxN],match[MaxN],vis[MaxN];

int ans, cnt;

int n, m;

inline void add_edge(int u, int v)

{

    cnt++;

    e[cnt].to = v;

    e[cnt].next = head[u];

    head[u] = cnt;

}

bool dfs(int x)

{

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

    {

        int y = e[i].to;

        if(!vis[y])

        {

            vis[y] = 1;

            if(!match[y] || dfs(match[y]))

            {

                match[y] = x;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    int num;

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

    for(int i = 1; i <= num; i++)

    {

        int u, v;

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

        add_edge(u, v);

    }

    for(int i = 1; i <= n; i++)

    {

        memset(vis, 0, sizeof(vis));

        if(dfs(i))ans++;

    }

    printf("%d", ans);

    return 0;

}

Treap

例题 洛谷P3369 
//Treap by little_sun

#include <bits/stdc++.h>

using namespace std;

struct node

{

    int l;    //左儿子

    int r;    //右儿子

    int v;    //value

    int size; //树大小[节点个数]

    int rnd;  //随机值

    int w;    //相同数值个数

} tree[100005];

int n, size, root, ans;

void update(int k) //更新节点信息

{

    tree[k].size = tree[tree[k].l].size + tree[tree[k].r].size + tree[k].w;

}

void rturn(int &k) //右旋

{

    int t = tree[k].l;

    tree[k].l = tree[t].r;

    tree[t].r = k;

    tree[t].size = tree[k].size;

    update(k);

    k = t;

}

void lturn(int &k) //左旋

{

    int t = tree[k].r;

    tree[k].r = tree[t].l;

    tree[t].l = k;

    tree[t].size = tree[k].size;

    update(k);

    k = t;

}

void insert(int &k, int x) //插入

{

    if (k == 0)

    {

        size++;

        k = size;

        tree[k].size = tree[k].w = 1;

        tree[k].v = x;

        tree[k].rnd = rand();

        return;

    }

    tree[k].size++;

    if (tree[k].v == x)

        tree[k].w++;

    else if (x > tree[k].v)

    {

        insert(tree[k].r, x);

        if (tree[tree[k].r].rnd < tree[k].rnd)

            lturn(k);

    }

    else

    {

        insert(tree[k].l, x);

        if (tree[tree[k].l].rnd < tree[k].rnd)

            rturn(k);

    }

}

void del(int &k, int x) //删除

{

    if (k == 0)

        return;

    if (tree[k].v == x)

    {

        if (tree[k].w > 1)

        {

            tree[k].w--;

            tree[k].size--;

            return;

        }

        if (tree[k].l * tree[k].r == 0)

            k = tree[k].l + tree[k].r;

        else if (tree[tree[k].l].rnd < tree[tree[k].r].rnd)

            rturn(k), del(k, x);

        else

            lturn(k), del(k, x);

    }

    else if (x > tree[k].v)

    {

        tree[k].size--;

        del(tree[k].r, x);

    }

    else

    {

        tree[k].size--;

        del(tree[k].l, x);

    }

}

int query_rank(int k, int x)

{

    if (k == 0)

        return 0;

    if (tree[k].v == x)

        return tree[tree[k].l].size + 1;

    else if (x > tree[k].v)

        return tree[tree[k].l].size + tree[k].w + query_rank(tree[k].r, x);

    else

        return query_rank(tree[k].l, x);

}

int query_num(int k, int x)

{

    if (k == 0)

        return 0;

    if (x <= tree[tree[k].l].size)

        return query_num(tree[k].l, x);

    else if (x > tree[tree[k].l].size + tree[k].w)

        return query_num(tree[k].r, x - tree[tree[k].l].size - tree[k].w);

    else

        return tree[k].v;

}

void query_pro(int k, int x)

{

    if (k == 0)

        return;

    if (tree[k].v < x)

    {

        ans = k;

        query_pro(tree[k].r, x);

    }

    else

        query_pro(tree[k].l, x);

}

void query_sub(int k, int x)

{

    if (k == 0)

        return;

    if (tree[k].v > x)

    {

        ans = k;

        query_sub(tree[k].l, x);

    }

    else

        query_sub(tree[k].r, x);

}

int main()

{

    scanf("%d", &n);

    int opt, x;

    for (int i = 1; i <= n; i++)

    {

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

        if (opt == 1)

            insert(root, x);

        if (opt == 2)

            del(root, x);

        if (opt == 3)

            printf("%d\n", query_rank(root, x));

        if (opt == 4)

            printf("%d\n", query_num(root, x));

        if (opt == 5)

        {

            ans = 0, query_pro(root, x), printf("%d\n", tree[ans].v);

        }

        if (opt == 6)

        {

            ans = 0, query_sub(root, x), printf("%d\n", tree[ans].v);

        }

    }

    return 0;

}

相关阅读

目录[+]