头像

胡图图

辽宁大学




离线:2分钟前


最近来访(882)
用户头像
disheng
用户头像
Behappyeveryday
用户头像
Acwer
用户头像
晴明
用户头像
crr
用户头像
ciaocian
用户头像
小张小张自作主张
用户头像
Ymer
用户头像
今晚占用9kb
用户头像
一万小时定律
用户头像
Kitebin
用户头像
Forever_Czz
用户头像
向往的生活
用户头像
菜狗一枚
用户头像
ღSupperღ
用户头像
faith_9
用户头像
Protein
用户头像
沙二
用户头像
XX31MRK
用户头像
stan_ym

分享 图论板子

图论板子(后面会陆续更新的)

Kruskal重构树

每一次加边会合并两个集合,我们可以新建一个点,点权为加入边的边权,同时将两个集合的根节点分别设为新建点的左儿子和右儿子。然后我们将两个集合和新建点合并成一个集合。将新建点设为根。

不难发现,在进行 轮之后我们得到了一棵恰有 个叶子的二叉树,同时每个非叶子节点恰好有两个儿子。这棵树就叫 Kruskal 重构树。

性质:不难发现,原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。

mst.png

板子题

给你一个图,图上有点权和边权。以及q个查询:每个查询给你一个初始位置x和初始能量k。
你每到一个新点上即可获得该点的能量(即点权),但是如果想通过一条边,你的能量总数需要大于边权。
问:可以获取的最大能量数

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10; 

int n,m,q,idx;

int f[N][21],cost[N][21],fa[N];
int w[N];

struct Edge{
    int a,b,c;
    bool operator<(const Edge&t) const {
        return c < t.c;
    }
}e[N];

int find(int x) {
    if(fa[x] == x) return x;

    return fa[x] = find(fa[x]);
}

int main() {

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

    for(int i=1;i<=n;i++) scanf("%d",&w[i]);

    for(int i=1;i<=m;i++) {
        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
    }

    sort(e + 1,e + m + 1); // 对边排序

    for(int i=1;i<N;i++) fa[i] = i;

    idx = n;

    // 构造重构树
    for(int i=1;i<=m;i++) {
        int a = find(e[i].a);
        int b = find(e[i].b);
        int c = e[i].c;
        if(a == b) continue;
        ++idx;
        fa[a] = idx; fa[b] = idx;
        w[idx] = w[a] + w[b];
        f[a][0] = idx;
        f[b][0] = idx;
        cost[a][0] = c - w[a];
        cost[b][0] = c - w[b];
    }

    w[0] = w[idx]; // 上界设为根

    // 倍增求最高可以到达的地方
    for(int j=1;j<=20;j++) {
        for(int i=1;i<=idx;i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
            cost[i][j] = max(cost[i][j - 1],cost[f[i][j - 1]][j - 1]);
        }
    }

    for(int i=1;i<=q;i++) {
        int x,k; scanf("%d%d",&x,&k);
        for(int j=20;j>=0;j--) if(cost[x][j] <= k) x = f[x][j];
        printf("%d\n",w[x] + k);
    }


    return 0;
}

虚树

通过树链剖分的方式,将关键点转换为部分树(O(nlogn))

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 3e5 + 10,M = N * 2;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n,m;
int w[M],h[N],e[M],ne[M],idx;
int id[N],nw[N],cnt;
int dep[N],sz[N],top[N],fa[N],son[N],st[N],tp;
int root;
int is[N];
bool choosen[N];

ll minv[N]; // 表示要删掉这个点要付出的代价

void add(int a,int b,int c) {
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
}

void dfs1(int u,int father ,int depth) {
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        minv[j] = min(minv[u],(ll)w[i]);
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u,int t) {
    id[u] = ++ cnt, top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

int lca(int x,int y)
{
    while (top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]];

    if (dep[x]<dep[y]) return x; 

    return y;
}

bool CMP(int a,int b) {
    return id[a] < id[b];
}

void ins(int x)
{
    if (tp==0)
    {
        st[tp=1]=x;
        return;
    }
    int ance=lca(st[tp],x);//相当于z
    while ((tp>1)&&(dep[ance]<dep[st[tp-1]]))
    {
        add(st[tp-1],st[tp],0);
        --tp;
    }
    if (dep[ance]<dep[st[tp]]) add(ance,st[tp--],0);
    if ((!tp)||(st[tp]!=ance)) st[++tp]=ance;
    st[++tp]=x;
}//增量构建

ll dp(int u)
{
    ll temp = 0;

    for(int i=h[u];~i;i=ne[i]) {
        int x = e[i];
        temp += dp(x);
    }

    h[u] = -1;

    if(choosen[u]) return minv[u];

    return min(minv[u],temp); 
}


int main() {

    memset(h,-1,sizeof h);

    scanf("%d",&n);

    for(int i=0;i<n-1;i++) {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
    }

    minv[1] = INF;
    dfs1(1, -1, 1);
    dfs2(1, 1);

    idx = 0;
    memset(h,-1,sizeof h);

    scanf("%d",&m);

    while(m--) {
        int len; scanf("%d",&len);
        for(int i=1;i<=len;i++) {
            scanf("%d",&is[i]);
            choosen[is[i]] = true;
        }

        sort(is + 1,is + len + 1,CMP);

        if(is[1]!=1) st[tp=1] = 1; //加入根

        for(int i=1;i<=len;i++) ins(is[i]);

        if(tp) while(--tp) add(st[tp],st[tp + 1],0);

        printf("%lld\n",dp(1));

        idx = 0;
        for(int i=1;i<=len;i++) {
            choosen[is[i]] = false;
        }

    }


}

树链剖分

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 100010,M = N * 2;

int n,m;
int w[N],h[N],e[M],ne[M],idx;
int id[N],nw[N],cnt;
int dep[N],sz[N],top[N],fa[N],son[N];

struct Tree
{
    int l, r;
    ll add, sum;
}tr[N * 4];

void add(int a,int b) {
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}

void dfs1(int u,int father ,int depth) {
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u,int t) {
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
    auto &root = tr[u], &left = tr[u << 1],&right = tr[u << 1 | 1];
    if(root.add) {
        left.add += root.add, left.sum += root.add * (left.r - left.l + 1);
        right.add += root.add,right.sum += root.add * (right.r - right.l + 1);
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, nw[r]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}


void update(int u,int l,int r,int k) {
    if(l <= tr[u].l && r >= tr[u].r) {
        tr[u].add += k;
        tr[u].sum += k * (tr[u].r - tr[u].l + 1);
        return ;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) update(u << 1,l,r,k);
    if(r > mid) update(u << 1 | 1,l,r,k);
    pushup(u);
}

ll query(int u, int l, int r)
{
    if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    ll res = 0;
    if (l <= mid) res += query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

void update_path(int u,int v,int k) {

    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u,v);
        update(1,id[top[u]],id[u],k);
        u = fa[top[u]];
    }

    if(dep[u] < dep[v]) swap(u,v);
    update(1,id[v],id[u],k);
}

ll query_path(int u,int v) {
    ll res = 0;
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u,v);
        res += query(1,id[top[u]],id[u]);
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u,v);
    res += query(1,id[v],id[u]);
    return res;
}

void update_tree(int u,int k) {
    update(1,id[u],id[u] + sz[u] - 1,k);
}

ll query_tree(int u) {
    return query(1,id[u],id[u] + sz[u] - 1);
}

int main() {

    memset(h,-1,sizeof h);

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",&w[i]);

    for(int i=0;i<n-1;i++) {
        int a,b; scanf("%d%d",&a,&b);
        add(a,b); add(b,a);
    }

    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);

    scanf("%d",&m);

    while(m--) {
        int t,u,v,k;
         scanf("%d%d",&t,&u);
         if(t == 1) {
             scanf("%d%d",&v,&k);
             update_path(u,v,k);
         }
         else if(t == 2) {
             scanf("%d",&k);
             update_tree(u,k);
         }
         else if(t == 3) {
             scanf("%d",&v);
             printf("%lld\n",query_path(u,v));
         }
         else printf("%lld\n",query_tree(u));
    }


    return 0;
}


活动打卡代码 AcWing 159. 奶牛矩阵

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n,m;

int Next[N];
map<string,int> mp;
int idx;
string str[N];
int s[N];
bool st[N];

void work(string &s) {

    for(int i=1;i<=m;i++) {
        bool flag = true;
        for(int j=0;j<m;j+=i) {
            int len = min(i,m - j);
            if(!(s.substr(0,len) == s.substr(j,len) ))
            {
                // cout << s.substr(0,len) << " " << s.substr(j,len) << endl;
                flag = false;
                break;
            }
        }
        if(!flag) {
            st[i] = true;
        }
    }
}

int main(){

    cin >> n >> m;

    for(int i=1;i<=n;i++) 
    {
        cin >> str[i];
        if(!mp.count(str[i])) {
            mp[str[i]] = ++ idx;
        }
        s[i] = mp[str[i]];
    }


    for(int i=2,j=0;i<=n;i++)
    {
        while(j && s[i] != s[j + 1]) j = Next[j];
        if(s[i] == s[j + 1]) j ++ ;
        Next[i] = j;
    }

    int len = n - Next[n];

    for(int i=1;i<=n;i++) {
        work(str[i]);
    }

    int maxv = 1;

    while(st[maxv]) maxv ++ ;

    cout << len * maxv << endl;


    return 0;
}


活动打卡代码 AcWing 158. 项链

#include <bits/stdc++.h>

using namespace std;

int n;

string get_min(string &s) {

    int i = 0 , j = 1;

    while(i < n && j < n) {

        int k = 0;
        while(k < n && s[i + k] == s[j + k]) k ++ ;
        if(k == n) break;
        if(s[i + k] > s[j + k]) i = i + k + 1;
        else j = j + k + 1;

        if(i == j) j ++ ;
    }

    int k = min(i,j);

    return s.substr(k,n);
}

int main() {

    string s,t; cin >> s >> t;

    n = s.size();

    s = s + s;
    t = t + t;

    s = get_min(s);
    t = get_min(t);

    if(s == t) {
        puts("Yes");
        cout << s << endl;
        return 0;
    }
    puts("No");

    return 0;
}


活动打卡代码 AcWing 156. 矩阵

#include <bits/stdc++.h>

#define ull unsigned long long

using namespace std;

const int N=1010;

const int base=131;

set<ull,bool> s;

int n,m,A,B;
char g[N];
ull h[N][N],p[N * N];

ull get(ull h[],int l,int r)
{
   return h[r]-h[l-1]*p[r-l+1]; 
}

int main(){

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

    p[0] = 1;

    for(int i=1;i<N*N;i++) p[i] = p[i - 1] * base;

    for(int i=1;i<=n;i++) {
        scanf("%s",g + 1);
        for(int j=1;j<=m;j++) 
            h[i][j] = h[i][j - 1] * base + (g[j] - '0'); 
    }

    unordered_set<ull> s;

    for(int j=B;j<=m;j++) {
        ull temp = 0;
        for(int i=1;i<=n;i++) {
            temp = p[B] * temp + get(h[i],j - B + 1,j);

            if(i > A) temp -= get(h[i - A],j - B + 1,j) * p[A * B];
            if(i >= A) s.insert(temp);
        }
    }

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

    while(T--) {
        ull res = 0;
        for(int i=1;i<=A;i++) {
            scanf("%s",g + 1);
            for(int j=1;j<=B;j++) {
                res = res * base + (g[j] - '0');
            }
        }
        if(s.count(res)) puts("1");
        else puts("0");
    }







    return 0;
}




数据结构板子(会持续更新的)

线段树

  • 维护序列,线段树区间乘合加,维护区间和
#include <iostream>
#include <cstring>
#include <algorithm>

#define ll long long

using namespace std;

const int N = 100010;

struct Tree{
    int l,r;
    ll sum,mul,add;
};

Tree tr[N << 2];
int n,mod,m;
int w[N];

void pushup(int u)
{
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}

void eval(Tree &a,int mul,int add)
{
    a.sum = ((ll)a.sum * mul % mod + (ll)(a.r - a.l + 1) * add % mod) % mod;
    a.mul = ((ll)a.mul * mul) % mod;
    a.add = (a.add * mul % mod + add) % mod;
}

void pushdown(int u)
{
    eval(tr[u << 1],tr[u].mul,tr[u].add);
    eval(tr[u << 1 | 1],tr[u].mul,tr[u].add);
    tr[u].mul = 1;
    tr[u].add = 0;
}

void build(int u,int l,int r)
{
    tr[u].l = l;
    tr[u].r = r;
    tr[u].mul = 1;
    tr[u].add = 0;
    if(l == r){
        tr[u].sum = w[l] % mod;
        return ;
    }

    int mid = l + r >> 1;

    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);

    pushup(u);
}

void modify(int u,int l,int r,int mul,int add)
{
    if(l <= tr[u].l  && r >= tr[u].r) eval(tr[u],mul,add);
    else
    {
        pushdown(u);

        int mid = tr[u].l + tr[u].r >> 1;

        if(l <= mid) modify(u << 1,l,r,mul,add);
        if(r > mid) modify(u << 1 | 1,l,r,mul,add);

        pushup(u);
    }

}

ll query(int u,int l,int r)
{
    if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;

    if(r <= mid) return query(u << 1,l,r);
    else if(l > mid) return query(u << 1 | 1,l,r);
    else
    {
        ll left = query(u << 1,l,r);
        ll right = query(u << 1 | 1,l,r);
        ll res = (left + right) % mod;

        return res;
    }

}



int main(){

    ios :: sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> mod;

    for(int i=1;i<=n;i++) cin >> w[i];

    build(1,1,n);

    cin >> m;

    while(m--)
    {
        int op,l,r;
        cin >> op >> l >> r;
        if(op == 1)
        {
            int c;
            cin >> c;
            modify(1,l,r,c,0);
        }
        else if(op == 2)
        {
            int c;
            cin >> c;
            modify(1,l,r,1,c);
        }
        else
        {
            cout << query(1,l,r) << endl;
        }
    }



    return 0;
}

  • 线段树+矩阵
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 200010;

typedef array<ll, 3> vec;
typedef array<vec, 3> mat;

vec operator+(const vec& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = a[i] + b[i];
    return c;
}

vec operator-(const vec& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = a[i] - b[i];
    return c;
}

vec operator*(const mat& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            c[i] += a[i][j] * b[j];
    return c;
}

mat operator*(const mat& a, const mat& b)
{
    mat c;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            c[i][j] = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                c[i][k] += a[i][j] * b[j][k];
    return c;
}

struct Tree{
    int l,r;
    bool used;
    mat add;
    vec sum; // sum{[f[i] ^ 0 ,f[i] ^ 1,f[i] ^ 2]}
};

Tree tr[N << 2];
bool st[N];
mat S = {vec({1,0,0}),vec({0,1,0}),vec({0,0,1})};
mat ADD = {vec({1,0,0}),vec({1,1,0}),vec({1,2,1})};
mat SUB = {vec({1,0,0}),vec({-1,1,0}),vec({1,-2,1})};
int Q,D,n;

vec get(int u) {
    if(!tr[u].used) return {0,0,0};

    return tr[u].sum;
}

void pushup(int u)
{
    tr[u].sum = (get(u << 1) + get(u << 1 | 1));
}

void eval(Tree &a,mat &add)
{
    a.sum = add * a.sum;
    a.add = add * a.add;
}

void pushdown(int u)
{
    eval(tr[u << 1],tr[u].add);
    eval(tr[u << 1 | 1],tr[u].add);
    tr[u].add = S;
}

void build(int u,int l,int r)
{
    tr[u].l = l;
    tr[u].r = r;
    tr[u].add = S;
    tr[u].sum = {0,0,0};
    tr[u].used = true;
    if(l == r){
        tr[u].sum = {1,0,0};
        tr[u].used = false;
        return ;
    }

    int mid = l + r >> 1;

    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);

    pushup(u);
}

void modify(int u,int l,int r,mat &add)
{
    if(l <= tr[u].l  && r >= tr[u].r) {
        eval(tr[u],add);
    }
    else
    {
        pushdown(u);

        int mid = tr[u].l + tr[u].r >> 1;

        if(l <= mid) modify(u << 1,l,r,add);
        if(r > mid) modify(u << 1 | 1,l,r,add);

        pushup(u);
    }
}

void modify(int u, int x, bool used)
{
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].used = used;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, used);
        else modify(u << 1 | 1, x, used);
        pushup(u);
    }
}


int main(){

    n=2e5;

    build(1,1,n);

    scanf("%d%d",&Q,&D);


    while(Q--) {
        int x; scanf("%d",&x);
        int l = max(1,x - D);
        int r = x;
        if(!st[x]) {
            if(l < r) 
                modify(1,l,r-1,ADD);
            modify(1,x,true);
            st[x] = true;
        }
        else {
            if(l < r) 
                modify(1,l,r-1,SUB);
            modify(1,x,false);
            st[x] = false;
        }
        auto res = tr[1].sum;
        ll ans = (res[2] - res[1]) / 2;
        printf("%lld\n",ans);
    }




    return 0;
}
  • 线段树维护二进制

将二进制的某一位-1或者某一位+1

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 3e5 + 10;

struct Tree{
    int l,r;
    int sum,add;
    int ans;
    int r_0;
    int r_1;
};

Tree tr[N << 2];
int n,q,a[N];

void eval(Tree &a,int add)
{
    int len = a.r - a.l + 1;
    a.sum += len * add;
    a.add += add;
    if(a.sum >= len) {
        a.r_1 = a.r,a.ans = a.r;
        a.r_0 = 0;
    }
    else if(a.sum <= 0){
        a.r_0 = a.r,a.ans = 0;
        a.r_1 = 0;
    }
}

void pushup(int u)
{
    if(tr[u << 1].r_0 != tr[u << 1].r) tr[u].r_0 = tr[u << 1].r_0;
    else tr[u].r_0 = max(tr[u << 1 | 1].r_0,tr[u << 1].r_0);

    if(tr[u << 1].r_1 != tr[u << 1].r) tr[u].r_1 = tr[u << 1].r_1;
    else tr[u].r_1 = max(tr[u << 1 | 1].r_1,tr[u << 1].r_1);

    tr[u].ans = max(tr[u << 1].ans,tr[u << 1 | 1].ans);
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}



void pushdown(int u)
{

    eval(tr[u << 1],tr[u].add);
    eval(tr[u << 1 | 1],tr[u].add);

    tr[u].add = 0;

}

void build(int u,int l,int r)
{
    tr[u].l = l;
    tr[u].r = r;
    tr[u].add = 0;
    tr[u].sum = 0;
    tr[u].r_0 = r;
    tr[u].r_1 = 0;
    tr[u].ans = 0;

    if(l == r){

        return ;
    }

    int mid = l + r >> 1;

    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);

    pushup(u);
}

void modify(int u,int l,int r,int add)
{
    if(l <= tr[u].l  && r >= tr[u].r) {
        eval(tr[u],add);
    }
    else
    {
        pushdown(u);

        int mid = tr[u].l + tr[u].r >> 1;

        if(l <= mid) modify(u << 1,l,r,add);
        if(r > mid) modify(u << 1 | 1,l,r,add);

        pushup(u);
    }

}

int query(int u,int l,int r,int v)
{
    if(l <= tr[u].l && r >= tr[u].r) {
        if(v == 0) return tr[u].r_0;
        else {

            return tr[u].r_1;
        }

    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;

    if(r <= mid) return query(u << 1,l,r,v);
    else if(l > mid) return query(u << 1 | 1,l,r,v);
    else
    {
        int left = query(u << 1,l,r,v);
        int right = query(u << 1 | 1,l,r,v);
        if(left != tr[u << 1].r) {
            return left;
        }

        return max(left,right);
    }

}

void insert(int x) {
    int p = query(1,x,3e5,1);
    if(p == 0) modify(1,x,x,1);
    else {
        modify(1,x,p,-1);
        modify(1,p+1,p+1,1);
    }

}

void del(int x) {
    int p = query(1,x,3e5,0);
    if(p == 0) modify(1,x,x,-1);
    else {
        modify(1,x,p,1);
        modify(1,p+1,p+1,-1);
    }

}

int main() {

    build(1,1,3e5);

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

    for(int i=1;i<=n;i++ ) {
        int x; scanf("%d",&x);
        a[i] = x;
        insert(x);

    }

    for(int i=1;i<=q;i++) {
        int x,y; scanf("%d%d",&x,&y);
        del(a[x]);
        a[x] = y;
        insert(y);
        printf("%d\n",tr[1].ans);
    }



    return 0;
}

串串

  • trie
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1000010;

int ne[N][26],cnt[N],idx;
char str[N];
int n,m;
void insert()
{
    int p=0;
    for(int i=0;i<strlen(str);i++)
    {
        int &temp=ne[p][str[i]-'a'];
        if(!temp) temp=++idx;
        p=temp;
    }
    cnt[p]++;
}

int query()
{
    int p=0,res=0;
    for(int i=0;i<strlen(str);i++)
    {
        int &temp=ne[p][str[i]-'a'];
        if(!temp) break;
        res+=cnt[temp];
        p=temp;
    }

    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%s",str);
        insert();
    }
    for(int i=0;i<m;i++)
    {
        scanf("%s",str);
        printf("%d\n",query());
    }



    return 0;
}

  • KMP

    n - Next[n]可以求出循环节的长度,Next[i]表示以i为后缀能匹配最长的前缀长度

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n,m;

char s[N],t[N];

int Next[N];

int main(){

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

    for(int i=2,j=0;i<=n;i++)
    {
        while(j && s[i] != s[j + 1]) j = Next[j];
        if(s[i] == s[j + 1]) j ++ ;
        Next[i] = j;
    }

    for(int i=1,j=0;i<=m;i++)
    {
        while(j && t[i] != s[j + 1]) j = Next[j];
        if(t[i] == s[j + 1]) j ++ ;
        if(j == n)
        {
            cout << i - j << " ";
            j = Next[j];
        }
    }

    return 0;
}
  • 最小表示法
string get_min(string &s) { // 这里的s要翻倍s = s + s

    int i = 0 , j = 1;

    while(i < n && j < n) {

        int k = 0;
        while(k < n && s[i + k] == s[j + k]) k ++ ;
        if(k == n) break;
        if(s[i + k] > s[j + k]) i = i + k + 1;
        else j = j + k + 1;

        if(i == j) j ++ ;
    }

    int k = min(i,j);

    return s.substr(k,n);
}
  • 字符串哈希
#include<iostream>
#include<cstring>
#include<cstdio>
#define ull unsigned long long
using namespace std;

const int N=1000010;
const int base=131;
char str[N];
ull h[N],p[N];
ull get(int l,int r)
{
   return h[r]-h[l-1]*p[r-l+1]; 
}
int main(){
    scanf("%s",str+1);
    int n=strlen(str+1);
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*base+str[i]-'a'+1;
        p[i]=p[i-1]*base;
    }
    int m;
    cin>>m;
    int l1,l2,r1,r2;
    for(int i=0;i<m;i++)
    {
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))
            puts("Yes");
        else 
            puts("No");
    }
    return 0;
}



分享 数学板子

数学板子(后面会陆续更新的)

分解质因数

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int primes[N],cnt;
bool st[N];

void init() {

    st[1] = true;
    st[0] = true;

    for(int i=2;i<N;i++)
    {
        if(!st[i]) primes[cnt ++ ] = i;

        for(int j=0;primes[j] * i < N ; j ++ )
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
                break;
        }
    }
}

int main(){

    init();

    int T;

    cin >> T;

    while(T -- )
    {
        int n;

        cin >> n;

        for(int i=0;primes[i]*primes[i]<=n;i++)
        {
            int x = primes[i];
            if(n % x == 0)
            {
                int c = 0;

                while(n % x == 0) c ++ ,n /= x;

                cout << x << " " << c << endl;
            }
        }

        if(n > 1) cout << n << " " << 1 << endl;

        cout << endl;
    }

    return 0;
}

NTT

  • 多项式乘法
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int g = 3, gi = 332748118, mod = 998244353; // g为原根,gi为g的逆元
const int M = 1 << 22;

int tot,bit;
int a[M], b[M],rev[M];
int n,m;

int qmi(int a, int b) //快速幂,a为底数,k为指数
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

void NTT(int *a, int n, int type) // NTT,type=1时系数表示法转点值表示法,否则点值表示法转系数表示法
{
    for (int i = 0; i < n; ++i) //先将a变成最后的样子
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1)
    {                                                            //在这之前NTT与FFT无异
        int gn = qmi(type ? g : gi, (mod - 1) / (i << 1)); //单位原根g_n
        for (int j = 0; j < n; j += (i << 1))                    //枚举具体区间,j也就是区间右端点
        {
            int g0 = 1;
            for (int k = 0; k < i; ++k, g0 = 1ll * g0 * gn % mod) //合并,记得要取模
            {
                int x = a[j + k], y = 1ll * g0 * a[i + j + k] % mod;
                a[j + k] = (x + y) % mod;
                a[i + j + k] = (x - y + mod) % mod;
            }
        }
    }
}

int main()
{

    cin >> n >> m;

    while((1 << bit) < n + m + 1) bit ++ ;
    tot = 1 << bit;

    for(int i=0;i<tot;i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));

    memset(a,0,sizeof a);
    memset(b,0,sizeof b);

    for(int i=0;i<=n;i++) cin >> a[i];
    for(int i=0;i<=m;i++) cin >> b[i];

    NTT(a, tot, 1);
    NTT(b, tot, 1);

    for (int i = 0; i < tot; ++i)
        a[i] = 1ll * a[i] * b[i] % mod; // O(n)乘法

    NTT(a, tot, 0); //点值表示法转系数表示法

    int inv = qmi(tot, mod - 2); // inv为len的逆元(费马小定理求逆元)

    for (int i = 0; i <= n + m; ++i) //输出
        printf("%d ",1ll * a[i] * inv % mod);
    puts("");

    return 0;
}


  • 多项式求逆和多项式快速幂
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 400003, mod = 998244353, G = 3, Gi = 332748118;

int n, k, A[N]; // n表示有多少项 0 ~ n-1,k表示快速幂次数
int ans[N];
int rev[N];
int Ln[N];
int Exp[N];

inline int read(){
    int ch = getchar(), res = 0;
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9'){
        res = (res * 10ll + ch - '0') % mod;
        ch = getchar();
    }
    return res;
}

int qmi(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = (LL) res * a % mod;
        a = (LL) a * a % mod;
        b >>= 1;
    }
    return res;
}


void NTT(int *A, int limit, int type){
    for(int i = 0;i < limit;i ++)
        if(i < rev[i]) swap(A[i], A[rev[i]]);
    for(int mid = 1;mid < limit;mid <<= 1){
        int Wn = qmi(type == 1 ? G : Gi, (mod - 1) / (mid << 1));
        for(int j = 0;j < limit;j += mid << 1){
            int w = 1;
            for(int k = 0;k < mid;k ++, w = (LL) w * Wn % mod){
                int x = A[j + k], y = (LL) w * A[j + k + mid] % mod;
                A[j + k] = (x + y) % mod;
                A[j + k + mid] = (x - y + mod) % mod; 
            }
        }
    }
    if(type == -1){
        int inv = qmi(limit, mod - 2);
        for(int i = 0;i < limit;i ++) A[i] = (LL) A[i] * inv % mod;
    }
}


void poly_inv(int *A, int deg){
    static int tmp[N];
    if(deg == 1){
        ans[0] = qmi(A[0], mod - 2);
        return;
    }
    poly_inv(A, deg + 1 >> 1);
    int limit = 1, L = -1;
    while(limit <= (deg << 1)){limit <<= 1; L ++;}
    for(int i = 0;i < limit;i ++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
    for(int i = 0;i < deg;i ++) tmp[i] = A[i];
    for(int i = deg;i < limit;i ++) tmp[i] = 0;
    NTT(tmp, limit, 1); NTT(ans, limit, 1);
    for(int i = 0;i < limit;i ++) ans[i] = (2 - (LL) ans[i] * tmp[i] % mod + mod) % mod * ans[i] % mod;
    NTT(ans, limit, -1);
    for(int i = deg;i < limit;i ++) ans[i] = 0;
}


void poly_Ln(int *A, int deg){
    static int tmp[N];
    poly_inv(A, deg);
    for(int i = 1;i < deg;i ++) tmp[i - 1] = (LL) i * A[i] % mod;
    tmp[deg - 1] = 0;
    int limit = 1, L = -1;
    while(limit <= (deg << 1)){limit <<= 1; L ++;}
    for(int i = 0;i < limit;i ++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
    NTT(ans, limit, 1); NTT(tmp, limit, 1);
    for(int i = 0;i < limit;i ++) Ln[i] = (LL) ans[i] * tmp[i] % mod;
    NTT(Ln, limit, -1);
    for(int i = deg + 1;i < limit;i ++) Ln[i] = 0;
    for(int i = deg;i;i --) Ln[i] = (LL) Ln[i - 1] * qmi(i, mod - 2) % mod;
    Ln[0] = 0;
    for(int i = 0;i < limit;i ++) ans[i] = tmp[i] = 0;
}


void poly_Exp(int *A, int deg){
    if(deg == 1){
        Exp[0] = 1;
        return;
    }
    poly_Exp(A, deg + 1 >> 1);
    poly_Ln(Exp, deg);
    for(int i = 0;i < deg;i ++) Ln[i] = (A[i] + (i == 0) - Ln[i] + mod) % mod;
    int limit = 1, L = -1;
    while(limit <= (deg << 1)){limit <<= 1; L ++;}
    for(int i = 0;i < limit;i ++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
    NTT(Exp, limit, 1); NTT(Ln, limit, 1);
    for(int i = 0;i < limit;i ++) Exp[i] = (LL) Exp[i] * Ln[i] % mod;
    NTT(Exp, limit, -1);
    for(int i = deg;i < limit;i ++) Exp[i] = 0;
    for(int i = 0;i < limit;i ++) Ln[i] = ans[i] = 0;
}

void poly_ni(int n){ // 多项式求逆

    memset(A,0,sizeof A);
    memset(ans,0,sizeof ans);
    memset(rev,0,sizeof rev);
    memset(Exp,0,sizeof Exp);
    memset(Ln,0,sizeof Ln);

    for(int i = 1;i < n;i ++) {
        int x = read(); 
        A[i] = -x + mod;
    }

    A[0] = 1 % mod;

    poly_inv(A,n);

    for(int i=0;i<n;i++) printf("%d ",ans[i]);

} 

void poly_mi(int n,int k) { // 多项式快速幂

    memset(A,0,sizeof A);
    memset(ans,0,sizeof ans);
    memset(rev,0,sizeof rev);
    memset(Exp,0,sizeof Exp);
    memset(Ln,0,sizeof Ln);

    for(int i = 0;i < n;i ++) A[i] = read();

    poly_Ln(A, n);

    for(int i = 0;i < n;i ++) A[i] = (LL) Ln[i] * k % mod, Ln[i] = 0;

    poly_Exp(A, n);

    for(int i = 0;i < n;i ++) printf("%d ", Exp[i]);

    puts("");
}

int main(){

    n = read();

    poly_ni(n);

}

分治NTT

QQ图片20220806173021.png

分治NTT处理这个a,b,a_0 = 1,b_0 = 0

// 分治ntt处理ai和bi

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 262144, K = 17, mod = 998244353, G = 3; // K设为log(N)

int n, i, x;

int pos[N + 5], A[N + 5], B[N + 5], W[N + 5], g[K + 5], ng[K + 5], inv[N + 5], inv2;

int p[N + 5], invp[N + 5], cost[N + 5], w[N + 5], pre[N + 5];

int ea[N + 5], eb[N + 5], fa[N + 5], fb[N + 5];

int qmi(int a, int b)
{
    int res = 1;

    while (b)
    {
        if (b & 1)
            res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }

    return res;
}

inline void NTT(int *a, int n, int t)
{
    for (int i = 1; i < n; i++)
        if (i < pos[i])
            swap(a[i], a[pos[i]]);
    for (int d = 0; (1 << d) < n; d++)
    {
        int m = 1 << d, m2 = m << 1, _w = t == 1 ? g[d] : ng[d];
        for (int i = 0; i < n; i += m2)
            for (int w = 1, j = 0; j < m; j++)
            {
                int &A = a[i + j + m], &B = a[i + j], t = 1LL * w * A % mod;
                A = B - t;
                if (A < 0)
                    A += mod;
                B = B + t;
                if (B >= mod)
                    B -= mod;
                w = 1LL * w * _w % mod;
            }
    }
    if (t == -1)
        for (int i = 0, j = inv[n]; i < n; i++)
            a[i] = 1LL * a[i] * j % mod;
}

void solve(int l, int r)
{
    if (l == r)
    {
        if (l)
        {
            ea[l+1]=((ea[l]-(1LL-p[l])*fa[l]%mod*pre[l])%mod+mod)*invp[l]%mod; // fa[l]就是ntt处理出来的那个求和
            eb[l+1]=((eb[l]-cost[l]-(1LL-p[l])*fb[l]%mod*pre[l])%mod+mod)*invp[l]%mod;
        }
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid);
    int k = 1;
    while (k < r - l + 1) k <<= 1;
    for (int i = 0; i < k; i++)
        A[i] = B[i] = W[i] = 0;

    for (int i = l; i <= mid; i++)
    {
        A[i - l] = ea[i];
        B[i - l] = eb[i];
    }

    for (int i = 1; i <= r - l; i++)
        W[i] = w[i];

    int j = __builtin_ctz(k) - 1;
    for (int i = 0; i < k; i++)
        pos[i] = pos[i >> 1] >> 1 | ((i & 1) << j);

    NTT(A,k,1);
    NTT(B,k,1);
    NTT(W,k,1);

    for (int i = 0; i < k; i++)
    {
        A[i] = 1ll * A[i] * W[i] % mod;
        B[i] = 1ll * B[i] * W[i] % mod;
    }

    NTT(A,k,-1);
    NTT(B,k,-1);

    for (int i = mid + 1; i <= r; i++)
    {
        fa[i] = (fa[i] + A[i - l]) % mod;
        fb[i] = (fb[i] + B[i - l]) % mod;
    }
    solve(mid + 1, r);
}

int main()
{

    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);

    for (g[K] = qmi(G, (mod - 1) / N), ng[K] = qmi(g[K], mod - 2), i = K - 1; ~i; i--)
        g[i] = 1LL * g[i + 1] * g[i + 1] % mod, ng[i] = 1LL * ng[i + 1] * ng[i + 1] % mod;

    for (int i = 1; i <= N; i++)
        inv[i] = qmi(i, mod - 2);
    inv2 = inv[2];

    int T;

    scanf("%d", &T);

    while (T--)
    {

        scanf("%d", &n);

        for (int i = 0; i < n; i++)
        {
            int x;
            scanf("%d%d", &x, &cost[i]);
            p[i] = 1ll * x * inv[100] % mod;
            invp[i] = 100ll * inv[x] % mod;
        }

        for(int i=1;i<n;i++) {
            scanf("%d",&w[i]);
            pre[i] = (pre[i - 1] + w[i]) % mod;
        }
        for(i=1;i<n;i++)pre[i]=qmi(pre[i],mod-2);

        for (i = 0; i <= n; i++) fa[i] = fb[i] = 0;
        ea[0] = 1, eb[0] = 0;
        ea[1] = 1, eb[1] = (mod-cost[0])%mod;

        solve(0,n-1);

        int res = 1ll * (mod - eb[n]) * qmi(ea[n],mod - 2) % mod;
        printf("%d\n",res);
    }

    return 0;
}

线性基(求最大异或和)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 100010;

int n;
LL a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);

    int k = 0;
    for (int i = 62; i >= 0; i -- )
    {
        for (int j = k; j < n; j ++ )
            if (a[j] >> i & 1)
            {
                swap(a[j], a[k]);
                break;
            }
        if (!(a[k] >> i & 1)) continue;
        for (int j = 0; j < n; j ++ )
            if (j != k && (a[j] >> i & 1))
                a[j] ^= a[k];
        k ++ ;
        if (k == n) break;
    }

    LL res = 0;
    for (int i = 0; i < k; i ++ ) res ^= a[i];
    printf("%lld\n", res);
    return 0;
}

MIN25求1-n的质数和


#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

typedef long long LL;

namespace Min25 {

    int prime[N], id1[N], id2[N], flag[N], ncnt, m;

    LL g[N], sum[N], a[N], T, n;

    inline int ID(LL x) {
        return x <= T ? id1[x] : id2[n / x];
    }

    inline LL calc(LL x) {
        return x * (x + 1) / 2 - 1;
    }

    inline LL f(LL x) {
        return x;
    }

    inline void init() {
        m = ncnt = 0;
        T = sqrt(n + 0.5);
        for (int i = 2; i <= T; i++) {
            if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
            for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
                flag[i * prime[j]] = 1;
                if (i % prime[j] == 0) break;
            }
        }
        for (LL l = 1; l <= n; l = n / (n / l) + 1) {
            a[++m] = n / l;
            if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
            g[m] = calc(a[m]);
        }
        for (int i = 1; i <= ncnt; i++) 
            for (int j = 1; j <= m && (LL)prime[i] * prime[i] <= a[j]; j++) 
                g[j] = g[j] - (LL)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
    }

    inline LL solve(LL x) {
        if (x <= 1) return x;
        return n = x, init(), g[ID(n)];
    }

}

int main() {
    LL n; scanf("%lld", &n);
    printf("%lld\n", Min25::solve(n));
}

数学小结论

  • (a + b) = (a ^ b) + 2 * (a & b)
  • $\lfloor x / y \rfloor$ = z,已知x和z求y的范围是[x / (z + 1) + 1,x / z]
  • 网格中从(0,0)出发向下和向右走,到达(x,y)的方案数未C(x,x + y)
  • 组合数求和:$ \sum_{i=0}^k\binom{n+i}n=\binom{n+k+1}{n+1} $
  • 错排公式: D(n) = (n-1) [D(n-2) + D(n-1)],特殊地,D(1) = 0, D(2) = 1.
  • 博弈论公平组合游戏可以视为一颗有向数,一个节点的sg(u) = 子节点mex{sg(v)},可以将多个状态拆分成,多个局面下的一个状态,并且sg(root_1) ^ sg(root_2) …。


活动打卡代码 AcWing 3164. 线性基

胡图图
11天前
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 100010;

int n;
LL a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);

    int k = 0;
    for (int i = 62; i >= 0; i -- )
    {
        for (int j = k; j < n; j ++ )
            if (a[j] >> i & 1)
            {
                swap(a[j], a[k]);
                break;
            }
        if (!(a[k] >> i & 1)) continue;
        for (int j = 0; j < n; j ++ )
            if (j != k && (a[j] >> i & 1))
                a[j] ^= a[k];
        k ++ ;
        if (k == n) break;
    }

    LL res = 0;
    for (int i = 0; i < k; i ++ ) res ^= a[i];
    printf("%lld\n", res);
    return 0;
}


活动打卡代码 AcWing 2174. 费用流

胡图图
14天前
#include <bits/stdc++.h>

using namespace std;

const int N = 5010, M = 100010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d)
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool spfa()
{
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (f[i] && d[ver] > d[t] + w[i])
            {
                d[ver] = d[t] + w[i];
                pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if (!st[ver])
                {
                    q[tt ++ ] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

void EK(int& flow, int& cost)
{
    flow = cost = 0;
    while (spfa())
    {
        int t = incf[T];
        flow += t, cost += t * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, c, d);
    }

    int flow, cost;
    EK(flow, cost);
    printf("%d %d\n", flow, cost);

    return 0;
}


活动打卡代码 AcWing 2280. 最优标号

胡图图
15天前
#include <bits/stdc++.h>

#define pii pair<int,int>
#define ll long long

using namespace std;

const int N = 100010, M = 200010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
pii edge[N];

int p[N];

void add(int a, int b, int c,int d)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T)  return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;  // 当前弧优化
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

void build(int D) {

    memset(h,-1,sizeof h);
    idx = 0;

    for(int i=1;i<=m;i++) {
        int a = edge[i].first;
        int b = edge[i].second;
        add(a,b,1,1);
    }

    for(int i=1;i<=n;i++) {
        if(p[i] > 0) {
            if(p[i] >> D & 1) add(i,T,INF,0);
            else add(S,i,INF,0);
        }
    }
}

int dinic(int D)
{
    build(D);

    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

int main() {

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

    S = 0,T = n + 1;

    for(int i=1;i<=m;i++) scanf("%d%d",&edge[i].first,&edge[i].second);

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

    memset(p,-1,sizeof p);

    while(K--) {
        int a,b; scanf("%d%d",&a,&b);
        p[a] = b;
    }

    ll ans = 0;

    for(int i=0;i<=30;i++) {
        ll res = (ll)dinic(i);
        ans += res << i;
    }

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


    return 0;
}




胡图图
15天前
#include <bits/stdc++.h>

using namespace std;

const int N = 10010,M=200010,INF=1e8;

int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N],cur[N];

void add(int a,int b,int c) {
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx ++ ;
}

bool bfs() {
    int hh = 0,tt = 0;
    memset(d,-1,sizeof d);
    q[0] = S,d[S] = 0,cur[S] = h[S];

    while(hh <= tt) {
        int t = q[hh ++ ];
        for(int i=h[t];~i;i=ne[i]) {
            int ver = e[i];
            if(d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                q[++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u,int limit) {
    if(u == T) return limit;
    int flow = 0;
    for(int i=cur[u];~i && flow < limit ; i = ne[i] ) {
        cur[u] = i;
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i] ) {
            int t = find(ver,min(f[i],limit - flow));
            if(!t) d[ver] = -1;
            f[i] -= t,f[i ^ 1] += t,flow += t;
        }
    }
    return flow;
}

int dinic() {

    int r =0,flow;
    while(bfs()) while(flow = find(S,INF)) {
        r += flow;
    }
    return r;
}

int main() {
    scanf("%d%d%d%d",&n,&m,&S,&T);

    memset(h,-1,sizeof h);

    while(m -- ) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    printf("%d\n",dinic());

    return 0;
}