板子 | ACM之梦

Category Archives: 板子

字符串hash解lcp

uLL ha1[maxn], pw1[maxn], ha2[maxn], pw2[maxn];
int len;
char str[maxn];

void Init(){
    pw1[0] = pw2[0] = 1;
    for(int i = 1; i < maxn; i++){
        pw1[i] = pw1[i - 1] * 123;
        pw2[i] = pw2[i - 1] * 29;
    }
}

void build(){
    for(int i = 1; i <= len; i++){
        ha1[i] = ha1[i - 1] * 123 + str[i];
        ha2[i] = ha2[i - 1] * 29 + str[i];
    }
}

uLL getHash1(int x, int L){
    return ha1[x + L - 1] - ha1[x - 1] * pw1[L];
}

uLL getHash2(int x, int L){
    return ha2[x + L - 1] - ha2[x - 1] * pw2[L];
}

int lcp(int x, int y){
    int l = 0, r = len - max(x, y) + 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(getHash1(x, mid) == getHash1(y, mid) && getHash2(x, mid) == getHash2(y, mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    return r;
}

uLL ha1[maxn], pw1[maxn], ha2[maxn], pw2[maxn];

int len;

char str[maxn];

void Init(){

pw1[0] = pw2[0] = 1;

for(int i = 1; i < maxn; i++){

pw1[i] = pw1[i - 1] * 123;

pw2[i] = pw2[i - 1] * 29;

}

void build(){

for(int i = 1; i <= len; i++){

ha1[i] = ha1[i - 1] * 123 + str[i];

ha2[i] = ha2[i - 1] * 29 + str[i];

}

uLL getHash1(int x, int L){

return ha1[x + L - 1] - ha1[x - 1] * pw1[L];

}

uLL getHash2(int x, int L){

return ha2[x + L - 1] - ha2[x - 1] * pw2[L];

}

int lcp(int x, int y){

int l = 0, r = len - max(x, y) + 1;

while(l <= r){

int mid = (l + r) >> 1;

if(getHash1(x, mid) == getHash1(y, mid) && getHash2(x, mid) == getHash2(y, mid))

l = mid + 1;

else

r = mid - 1;

}

return r;

}

AC自动机

ac自动机是kmp的高级版，实现多模式串匹配，常常伴有dp计数即动态转移图 [crayon-5debe26b1 …

后缀自动机

后缀自动机，线性空间将一个串的所有后缀存储。事实上后缀自动机可以存储所有的子串。以下是关于后缀自动机的一些结 …

Trie

最近整理了一下字典树的静态模板

const int maxn = 1005;
const int NODE = 1005;

struct Trie{
    int nxt[NODE][26], num[NODE];
    int root, tol;

    int newNode(){
        for(int i = 0; i < 26; i++){
            nxt[tol][i] = -1;
        }
        num[tol++] = 0;
        return tol - 1;
    }

    void Init(){
        tol = 0;
        root = newNode();
    }

    void ins(char s[]){
        int now = root;
        for(int i = 0, k; s[i]; i++){
            k = s[i] - 'a';
            if(nxt[now][k] == -1)
                nxt[now][k] = newNode();
            now = nxt[now][k];
            num[now]++;
        }
    }

    void del(char s[]){
        int now = root;
        for(int i = 0, k; s[i]; i++){
            k = s[i] - 'a';
            now = nxt[now][k];
            num[now]--;
        }
    }

    bool Find(char s[]){
        int now = root;
        for(int i = 0, k; s[i]; i++){
            k = s[i] - 'a';
            now = nxt[now][k];
            if(now == -1 || !num[now])
                return false;
        }
        return true;
    }

    int Count(char s[]){
        int now = root;
        for(int i = 0, k; s[i]; i++){
            k = s[i] - 'a';
            now = nxt[now][k];
            if(now == -1)
                return 0;
        }
        return num[now];
    }

}tree;

const int maxn = 1005;

const int NODE = 1005;

struct Trie{

int nxt[NODE][26], num[NODE];

int root, tol;

int newNode(){

for(int i = 0; i < 26; i++){

nxt[tol][i] = -1;

}

num[tol++] = 0;

return tol - 1;

}

void Init(){

tol = 0;

root = newNode();

}

void ins(char s[]){

int now = root;

for(int i = 0, k; s[i]; i++){

k = s[i] - 'a';

if(nxt[now][k] == -1)

nxt[now][k] = newNode();

now = nxt[now][k];

num[now]++;

}

void del(char s[]){

int now = root;

for(int i = 0, k; s[i]; i++){

k = s[i] - 'a';

now = nxt[now][k];

num[now]--;

}

bool Find(char s[]){

int now = root;

for(int i = 0, k; s[i]; i++){

k = s[i] - 'a';

now = nxt[now][k];

if(now == -1 || !num[now])

return false;

}

return true;

}

int Count(char s[]){

int now = root;

for(int i = 0, k; s[i]; i++){

k = s[i] - 'a';

now = nxt[now][k];

if(now == -1)

return 0;

}

return num[now];

}

}tree;

多重匹配

int mp[maxn][maxm], mat[maxm][maxn], cnt[maxm], vis[maxm], mx[maxm];
int n, m;

int dfs(int u){
    for(int i = 1; i <= m; i++){
        if(!vis[i] && mp[u][i]){
            vis[i] = 1;
            if(cnt[i] < mx[i]){
                mat[i][++cnt[i]] = u;
                return 1;
            }else{
                for(int j = 1; j <= mx[i]; j++){
                    if(dfs(mat[i][j])){
                        mat[i][j] = u;
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}

int Match(){
    memset(mat, 0, sizeof mat);
    memset(cnt, 0, sizeof cnt);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        memset(vis, 0, sizeof vis);
        if(dfs(i)) ans++;
    }
    return ans;
}

int mp[maxn][maxm], mat[maxm][maxn], cnt[maxm], vis[maxm], mx[maxm];

int n, m;

int dfs(int u){

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

if(!vis[i] && mp[u][i]){

vis[i] = 1;

if(cnt[i] < mx[i]){

mat[i][++cnt[i]] = u;

return 1;

}else{

for(int j = 1; j <= mx[i]; j++){

if(dfs(mat[i][j])){

mat[i][j] = u;

return 1;

}

return 0;

}

int Match(){

memset(mat, 0, sizeof mat);

memset(cnt, 0, sizeof cnt);

int ans = 0;

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

memset(vis, 0, sizeof vis);

if(dfs(i)) ans++;

}

return ans;

}

费用流

struct Edge{
    int v, next, flow, cap, cost;
}E[maxm];
int head[maxn], tol;
int dis[maxn], pre[maxn], vis[maxn];
int Q[maxm << 1], front, rear;

void Init(){
    memset(head, -1, sizeof head);
    tol = 0;
}

void add_edge(int u, int v, int cap, int cost){
    E[tol].v = v;
    E[tol].cap = cap;
    E[tol].flow = 0;
    E[tol].cost = cost;
    E[tol].next = head[u];
    head[u] = tol++;

    E[tol].v = u;
    E[tol].cap = 0;
    E[tol].flow = 0;
    E[tol].cost = -cost;
    E[tol].next = head[v];
    head[v] = tol++;
}

bool Spfa(int s, int t){
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    memset(pre, -1, sizeof pre);
    front = rear = 0;
    Q[rear++] = s;
    vis[s] = 1;
    dis[s] = 0;
    while(front < rear){
        int u = Q[front++];
        vis[u] = 0;
        for(int i = head[u]; ~i; i = E[i].next){
            int v = E[i].v;
            if(E[i].flow < E[i].cap && dis[v] > dis[u] + E[i].cost){
                dis[v] = dis[u] + E[i].cost;
                pre[v] = i;
                if(!vis[v]){
                    vis[v] = 1;
                    Q[rear++] = v;
                }
            }
        }
    }
    return dis[t] != INF;
}

pair <int, int> minCostmaxFlow(int s, int t){
    int flow = 0, cost = 0;
    while(Spfa(s, t)){
        int Min = INF;
        for(int i = pre[t]; ~i; i = pre[E[i ^ 1].v]){
            Min = min(Min, E[i].cap - E[i].flow);
        }
        for(int i = pre[t]; ~i; i = pre[E[i ^ 1].v]){
            E[i].flow += Min;
            E[i ^ 1].flow -= Min;
            cost += Min * E[i].cost;
        }
        flow += Min;
    }
    return make_pair(flow, cost);
}

struct Edge{

int v, next, flow, cap, cost;

}E[maxm];

int head[maxn], tol;

int dis[maxn], pre[maxn], vis[maxn];

int Q[maxm << 1], front, rear;

void Init(){

memset(head, -1, sizeof head);

tol = 0;

}

void add_edge(int u, int v, int cap, int cost){

E[tol].v = v;

E[tol].cap = cap;

E[tol].flow = 0;

E[tol].cost = cost;

E[tol].next = head[u];

head[u] = tol++;

E[tol].v = u;

E[tol].cap = 0;

E[tol].flow = 0;

E[tol].cost = -cost;

E[tol].next = head[v];

head[v] = tol++;

}

bool Spfa(int s, int t){

memset(dis, 0x3f, sizeof dis);

memset(vis, 0, sizeof vis);

memset(pre, -1, sizeof pre);

front = rear = 0;

Q[rear++] = s;

vis[s] = 1;

dis[s] = 0;

while(front < rear){

int u = Q[front++];

vis[u] = 0;

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

int v = E[i].v;

if(E[i].flow < E[i].cap && dis[v] > dis[u] + E[i].cost){

dis[v] = dis[u] + E[i].cost;

pre[v] = i;

if(!vis[v]){

vis[v] = 1;

Q[rear++] = v;

}

return dis[t] != INF;

}

pair <int, int> minCostmaxFlow(int s, int t){

int flow = 0, cost = 0;

while(Spfa(s, t)){

int Min = INF;

for(int i = pre[t]; ~i; i = pre[E[i ^ 1].v]){

Min = min(Min, E[i].cap - E[i].flow);

}

for(int i = pre[t]; ~i; i = pre[E[i ^ 1].v]){

E[i].flow += Min;

E[i ^ 1].flow -= Min;

cost += Min * E[i].cost;

}

flow += Min;

}

return make_pair(flow, cost);

}

Tarjan-点连通、边连通、强连通

点连通和边连通写法有一个细微的差别，点连通不用考虑重边带来的影响！但是边连通重边会导致原本是桥的变成不是桥，但 …

最小(大)表示法

最小(大)表示当求反串的最小表示在正串中的最靠前位置时，需要mod上循环节，这个比较容易理解，比如这个例子ab …

数论的一些板子

快速幂

LL quick_pow(LL a, LL k, LL mod){
    LL ans = 1;
    while(k){
        if(k & 1) ans = ans * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return ans;
}

LL quick_pow(LL a, LL k, LL mod){

LL ans = 1;

while(k){

if(k & 1) ans = ans * a % mod;

a = a * a % mod;

k >>= 1;

}

return ans;

}

快速乘法 [crayo …

Treap树

treap是 tree + heap的意思，就是树和堆的组合，这里的树是二叉搜索树，类似平衡数，treap维护 …