一些板子

发表于 更新于 本文字数： 4.3k 阅读时长 ≈ 16 分钟

我就是来水博客的

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int n,a;
struct node{
	int p,v;
};
stack<node> s;
int f[3000001];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		while(!s.empty()&&s.top().v<a)
		{
			f[s.top().p]=i;
			s.pop();
		}
		s.push({i,a});
	}
	for(int i=1;i<=n;i++) cout<<f[i]<<" ";
	return 0;
}

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
deque<int> q;
int n,k,a[1000001];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back();
		q.push_back(i);
		while(q.front()<=i-k) q.pop_front();
		if(i>=k) cout<<a[q.front()]<<" ";
	}
	cout<<endl;
	q.clear();
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&a[q.back()]<=a[i]) q.pop_back();
		q.push_back(i);
		while(q.front()<=i-k) q.pop_front();
		if(i>=k) cout<<a[q.front()]<<" ";
	}
	return 0;
}

堆/优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e6+5;
int n;
priority_queue<int,vector<int>,greater<int>> q;
int main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int op,x;
		cin>>op;
		if(op==1)
		{
			cin>>x;
			q.push(x);
		}
		else if(op==2) cout<<q.top()<<endl;
		else q.pop();
	}
	return 0;
}

ST 表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e5+5;
int n,m;
int st[maxn][31];
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>st[i][0];
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j+(1<<(i-1))>n) break;
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
        }
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        int len=log2(r-l+1);
        cout<<max(st[l][len],st[r-(1<<len)+1][len])<<endl;
    }
    return 0;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e4+5;
int n,m;
int fa[maxn];
int findfa(int x)
{
    if(x!=fa[x]) return fa[x]=findfa(fa[x]);
    else return x;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    while(m--)
    {
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1) 
        {
            fa[findfa(x)]=findfa(y);
        }
        else 
        {
            int fx=findfa(x),fy=findfa(y);
            if(fx==fy) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }
    return 0;
}

树状数组

单点修改，区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=5e5+5;
int n,m;
int tree[maxn];
int lowbit(int x) {return -x&x;}
void add(int x,int val)
{
    while(x<=n)
    {
        tree[x]+=val;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        add(i,x);
    }
    while(m--)
    {
        int opt,x,k;
        cin>>opt>>x>>k;
        if(opt==1) add(x,k);
        else cout<<query(k)-query(x-1)<<endl;
    }
    return 0;
}

区间修改，单点查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=5e5+5;
int n,m;
int a[maxn],tree[maxn];
int lowbit(int x) {return -x&x;}
void add(int x,int val)
{
    while(x<=n)
    {
        tree[x]+=val;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--) add(i,a[i]-a[i-1]);
    while(m--)
    {
        int opt,x,y,k;
        cin>>opt;
        if(opt==1)
        {
            cin>>x>>y>>k;
            add(x,k);
            if(y<n) add(y+1,-k);
        }
        else
        {
            cin>>x;
            cout<<query(x)<<endl;
        }
    }
    return 0;
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e5+5;
int n,m;
ll a[maxn];
ll tree[maxn<<2],tag[maxn<<2];
void push_up(int x) {tree[x]=tree[2*x]+tree[2*x+1];}
void build(int x,int l,int r)
{
    if(l==r)
    {
        tree[x]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    push_up(x);
}
void push_down(int x,int l,int r)
{
    int mid=(l+r)/2;
    tag[x*2]+=tag[x];
    tag[x*2+1]+=tag[x];
    tree[x*2]+=tag[x]*(mid-l+1);
    tree[x*2+1]+=tag[x]*(r-mid);
    tag[x]=0;
}
void add(int x,int l,int r,int nl,int nr,ll val)
{
    if(l>=nl&&r<=nr) 
    {
        tree[x]+=val*(r-l+1);
        tag[x]+=val;
        return;
    }
    int mid=(l+r)/2;
    push_down(x,l,r);
    if(mid>=nl) add(x*2,l,mid,nl,nr,val);
    if(mid<nr) add(x*2+1,mid+1,r,nl,nr,val);
    push_up(x);
}
ll query(int x,int l,int r,int nl,int nr)
{
    if(l>=nl&&r<=nr) return tree[x];
    int mid=(l+r)/2;
    push_down(x,l,r);
    ll res=0;
    if(mid>=nl) res+=query(x*2,l,mid,nl,nr);
    if(mid<nr) res+=query(x*2+1,mid+1,r,nl,nr);
    push_up(x);
    return res;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        int opt,x,y,k;
        cin>>opt;
        if(opt==1)
        {
            cin>>x>>y>>k;
            add(1,1,n,x,y,k);
        }
        else
        {
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

线段树分裂/合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=2e5+5;
int n,m;
int a[maxn];
ll tree[maxn<<5];
int son[maxn<<5][2],rub[maxn<<2],cnt,top;
int root[maxn<<2],tot;
int new_node()
{
    if(top) return rub[top--];
    return ++cnt;   
}
void del(int &x) 
{
    tree[x]=son[x][0]=son[x][1]=0;
    rub[++top]=x;
    x=0;
}
void push_up(int x) {tree[x]=tree[son[x][0]]+tree[son[x][1]];}
void build(int &x,int l,int r)
{
    if(!x) x=new_node();
    if(l==r)
    {
        tree[x]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(son[x][0],l,mid);
    build(son[x][1],mid+1,r);
    push_up(x);
}
void add(int &x,int l,int r,int q,int val)
{
    if(!x) x=new_node();
    if(l==r) 
    {
        tree[x]+=val;
        return;
    }
    int mid=(l+r)/2;
    if(mid>=q) add(son[x][0],l,mid,q,val);
    else add(son[x][1],mid+1,r,q,val);
    push_up(x);
}
ll query(int x,int l,int r,int nl,int nr)
{
    if(l>=nl&&r<=nr) return tree[x];
    int mid=(l+r)/2;
    ll res=0;
    if(mid>=nl) res+=query(son[x][0],l,mid,nl,nr);
    if(mid<nr) res+=query(son[x][1],mid+1,r,nl,nr);
    return res;
}
void split(int &x,int &y,int l,int r,int nl,int nr)
{
    if(!x) return;
    if(l>=nl&&r<=nr)
    {
        y=x;
        x=0;
        return;
    }
    if(!y) y=new_node();
    int mid=(l+r)/2;
    if(mid>=nl) split(son[x][0],son[y][0],l,mid,nl,nr);
    if(mid<nr) split(son[x][1],son[y][1],mid+1,r,nl,nr);
    push_up(x),push_up(y);
}
int merge(int &x,int &y,int l,int r)
{
    if(!x||!y) return x+y;
    if(l==r)
    {
        tree[x]+=tree[y];
        del(y);
        return x;
    }
    int mid=(l+r)/2;
    son[x][0]=merge(son[x][0],son[y][0],l,mid);
    son[x][1]=merge(son[x][1],son[y][1],mid+1,r);
    push_up(x);
    del(y);
    return x;
}
int kth(int x,int l,int r,ll k)
{
    if(l==r) return l;
    int mid=(l+r)/2;
    if(k<=tree[son[x][0]]) return kth(son[x][0],l,mid,k);
    else return kth(son[x][1],mid+1,r,k-tree[son[x][0]]);
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(root[++tot],1,n);
    while(m--)
    {
        int opt,p,x,y;
        cin>>opt;
        if(opt==0)
        {
            cin>>p>>x>>y;
            split(root[p],root[++tot],1,n,x,y);
        }
        else if(opt==1)
        {
            cin>>p>>x;
            root[p]=merge(root[p],root[x],1,n);
        }
        else if(opt==2)
        {
            cin>>p>>x>>y;
            add(root[p],1,n,y,x);
        }
        else if(opt==3)
        {
            cin>>p>>x>>y;
            cout<<query(root[p],1,n,x,y)<<endl;
        }
        else 
        {
            cin>>p>>x;
            if(tree[root[p]]<x) cout<<-1<<endl;
            else cout<<kth(root[p],1,n,x)<<endl;
        }
    }
    return 0;
}

字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=3e6+5;
int t,n,q;
string s;
int tree[maxn][65],cnt;
int sum[maxn];
int getnum(char ch)
{
    if(ch>='0'&&ch<='9') return ch-'0';
    if(ch>='A'&&ch<='Z') return ch-'A'+10;
    if(ch>='a'&&ch<='z') return ch-'a'+36;
}
void init()
{
    for(int i=0;i<=cnt;i++)
        for(int j=0;j<=62;j++)
            tree[i][j]=0;
    for(int i=1;i<=cnt;i++) sum[i]=0;
    cnt=0;
}
void add(string s)
{
    int u=0;
    for(int i=0;i<s.size();i++)
    {
        int tmp=tree[u][getnum(s[i])];
        if(!tmp)
        {
            tree[u][getnum(s[i])]=++cnt;
            tmp=cnt;
        }
        sum[tmp]++;
        u=tmp;
    }
}
int query(string s)
{
    int u=0;
    for(int i=0;i<s.size();i++)
    {
        int tmp=tree[u][getnum(s[i])];
        if(!tmp) return 0;
        u=tmp;
    }
    return sum[u];
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)
    {
        init();
        cin>>n>>q;
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            add(s);
        }
        while(q--)
        {
            cin>>s;
            cout<<query(s)<<endl;
        }
    }
    return 0;
}

笛卡尔树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e7+5;
int n;
int p[maxn];
int son[maxn][2];
int st[maxn],top;
ll ans;
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++)
    {
        int tmp=top;
        while(tmp&&p[st[tmp]]>p[i]) --tmp;
        if(tmp) son[st[tmp]][1]=i;
        if(tmp<top) son[i][0]=st[tmp+1];
        st[++tmp]=i;
        top=tmp;
    }
    for(int i=1;i<=n;i++) ans^=1ll*i*(son[i][0]+1);
    cout<<ans<<" ";
    ans=0;
    for(int i=1;i<=n;i++) ans^=1ll*i*(son[i][1]+1);
    cout<<ans<<endl;
    return 0;
}

FHQ-Treap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e5+5;
int n;
int son[maxn][2],val[maxn],pri[maxn],sze[maxn],cnt;
int root;
mt19937 rnd(time(0));

int newnode(int x)
{
    sze[++cnt]=1;
    pri[cnt]=rnd();
    son[cnt][0]=son[cnt][1]=0;
    val[cnt]=x;
    return cnt;
}

void push_up(int u) {sze[u]=sze[son[u][0]]+sze[son[u][1]]+1;}

void split(int u,int k,int &x,int &y)
{
    if(!u)
    {
        x=y=0;
        return;
    }
    if(k>=val[u])
    {
        x=u;
        split(son[u][1],k,son[u][1],y);
    }
    else
    {
        y=u;
        split(son[u][0],k,x,son[u][0]);
    }
    push_up(u);
}

int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(pri[x]>pri[y])
    {
        son[x][1]=merge(son[x][1],y);
        push_up(x);
        return x;
    }
    else
    {
        son[y][0]=merge(x,son[y][0]);
        push_up(y);
        return y;
    }
}

int ranking(int u,int k)
{
    while(1)
    {
        if(sze[son[u][0]]>=k) u=son[u][0];
        else if(sze[son[u][0]]+1==k) return u;
        else k-=sze[son[u][0]]+1,u=son[u][1];
    }
}

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    int x,y,z;
    while(n--)
    {
        int opt,a;
        cin>>opt>>a;
        if(opt==1)
        {
            split(root,a,x,y);
            root=merge(merge(x,newnode(a)),y);
        }
        else if(opt==2)
        {
            split(root,a,x,z);
            split(x,a-1,x,y);
            y=merge(son[y][0],son[y][1]);
            root=merge(merge(x,y),z);
        }
        else if(opt==3)
        {
            split(root,a-1,x,y);
            cout<<sze[x]+1<<endl;
            root=merge(x,y);
        }
        else if(opt==4)
        {
            cout<<val[ranking(root,a)]<<endl;
        }
        else if(opt==5)
        {
            split(root,a-1,x,y);
            cout<<val[ranking(x,sze[x])]<<endl;
            root=merge(x,y);
        }
        else
        {
            split(root,a,x,y);
            cout<<val[ranking(y,1)]<<endl;
            root=merge(x,y);
        }
    }
    return 0;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e6+5;
string s1,s2;
int nxt[maxn];
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s1>>s2;
    nxt[0]=-1;
    int j=-1;
    for(int i=1;i<s2.size();i++)
    {
        nxt[i]=-1;
        while(j!=-1&&s2[i]!=s2[j+1]) j=nxt[j];
        if(s2[i]==s2[j+1]) ++j;
        nxt[i]=j;
    }
    j=-1;
    for(int i=0;i<s1.size();i++)
    {
        while(j!=-1&&s1[i]!=s2[j+1]) j=nxt[j];
        if(s1[i]==s2[j+1]) ++j;
        if(j+1==s2.size())
        {
            cout<<i-j+1<<endl;
            j=nxt[j];
        }
    }
    for(int i=0;i<s2.size();i++) cout<<nxt[i]+1<<" ";
    cout<<endl;
    return 0;
}

Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=5e3+5,maxm=2e5+5;
int n,m;
struct edge
{
    int v,w;
};
vector<edge> g[maxn]; 
priority_queue<pii,vector<pii>,greater<pii>> q;
int vis[maxn],dis[maxn];
int num,ans;
void prim()
{
    memset(dis,0x7f,sizeof(dis));
    q.push({0,1});
    dis[1]=0;
    while(!q.empty()&&num<n)
    {
        int u=q.top().second,d=q.top().first;
        q.pop();
        if(vis[u]) continue;
        ++num;
        ans+=d;
        vis[u]=1;
        for(auto x:g[u])
        {
            int v=x.v,w=x.w;
            if(dis[v]>w)
            {
                dis[v]=w;
                q.push({w,v});
            }
        }
    }
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    prim();
    if(num==n) cout<<ans<<endl;
    else cout<<"orz"<<endl;
    return 0;
}

Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=5e3+5,maxm=2e5+5;
int n,m;
struct Edge
{
    int u,v,w;
}edge[maxm];
bool cmp(Edge x,Edge y) {return x.w<y.w;}
int fa[maxn];
int findfa(int x)
{
    if(x!=fa[x]) return fa[x]=findfa(fa[x]);
    return x;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    }
    sort(edge+1,edge+1+m,cmp);
    int num=0,ans=0;
    for(int i=1;i<=m;i++)
    {
        if(num==n-1) break;
        int fx=findfa(edge[i].u),fy=findfa(edge[i].v);
        if(fx==fy) continue;
        fa[fx]=fy;
        ++num;
        ans+=edge[i].w;
    }
    if(num<n-1) cout<<"orz"<<endl;
    else cout<<ans<<endl;
    return 0;
}

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e4+5;
int n,m,s;
struct edge
{
    int v,w;
};
vector<edge> g[maxn];
int dis[maxn],cnt[maxn],vis[maxn];
queue<int> q;
void spfa()
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto x:g[u])
        {
            int v=x.v,w=x.w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n) return;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
                
            }
        }
    }
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    spfa();
    for(int i=1;i<=n;i++) 
    {
        if(dis[i]==0x3f3f3f3f) cout<<(1<<30)-1+(1<<30)<<" ";
        else cout<<dis[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e5+5;
int n,m,s;
struct edge
{
    int v,w;
};
vector<edge> g[maxn];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>> q;
int dis[maxn],vis[maxn];

void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push({0,s});
    while(!q.empty())
    {
        int d=q.top().first,u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto ed:g[u])
        {
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    dijkstra();
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}

强连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=5e4+5;
int n,m;
vector<int> g[maxn],ans[maxn];
int tot;
stack<int> st;
int dfn[maxn],low[maxn],cnt;
int vis[maxn];
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++cnt;
    st.push(u);
    vis[u]=1;
    for(int v:g[u])
    {
        if(!dfn[v]) 
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        ++tot;
        while(st.top()!=u)
        {
            ans[tot].push_back(st.top());
            vis[st.top()]=0;
            st.pop();
        }
        ans[tot].push_back(st.top());
        vis[st.top()]=0;
        st.pop();
    }
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
    cout<<tot<<endl;
    for(int i=1;i<=tot;i++)
    {
        cout<<ans[i].size()<<" ";
        for(int j:ans[i]) cout<<j<<" ";
        cout<<endl;
    }
    return 0;
}

割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=2e5+5;
int n,m;
vector<int> g[maxn];
int dfn[maxn],low[maxn],cnt;
int tot;
vector<int> ans;
stack<int> st;
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++cnt;
    st.push(u);
    int son=0;
    bool flag=false;
    for(int v:g[u])
    {
        if(!dfn[v])
        {
            ++son;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(fa&&low[v]>=dfn[u])
            {
                flag=true;
                while(st.top()!=u) st.pop();
            }
        }
        else if(v!=fa) low[u]=min(low[u],dfn[v]);
    }
    if(fa==0&&son>1) flag=true;
    if(flag) ++tot,ans.push_back(u);
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
    cout<<tot<<endl;
    sort(ans.begin(),ans.end());
    for(int i:ans) cout<<i<<" ";
    cout<<endl;
    return 0;
}

树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e4+5;
int n;
vector<int> g[maxn];
int root,maxdepth;
void dfs1(int u,int fa,int depth)
{
    if(maxdepth<depth)
    {
        maxdepth=depth;
        root=u;
    }
    for(int v:g[u])
    {
        if(v==fa) continue;
        dfs1(v,u,depth+1);
    }
}
void dfs2(int u,int fa,int depth)
{
    maxdepth=max(maxdepth,depth);
    for(int v:g[u])
    {
        if(v==fa) continue;
        dfs2(v,u,depth+1);
    }
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1,0,1);
    dfs2(root,0,1);
    cout<<maxdepth-1<<endl;
    return 0;
}

树的重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
int n,u,v;
int g[101][101],w[101];
int main()
{
	ios::sync_with_stdio(false);
	memset(g,0x3f3f3f3f,sizeof(g));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>u>>v;
		g[i][u]=g[u][i]=g[i][v]=g[v][i]=1;
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i!=k&&j!=k&&i!=j&&g[i][j]>g[i][k]+g[k][j])
				{
					g[i][j]=g[i][k]+g[k][j];
				}
			}
		}
	}
	int minn=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		int sum=0;
		for(int j=1;j<=n;j++)
		{
			if(i!=j) sum+=g[i][j]*w[j];
		}
		if(sum<minn) minn=sum;
	}
	cout<<minn<<endl;
	return 0;
}

LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=5e5+5;
int n,m,s;
vector<int> g[maxn];
int fa[maxn][25],depth[maxn];
void dfs(int u,int father)
{
    fa[u][0]=father;
    depth[u]=depth[father]+1;
    for(int i=1;i<=20;i++)
    {
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int v:g[u])
    {
        if(v==father) continue;
        dfs(v,u);
    }
}
int lca(int u,int v)
{
    if(depth[u]<depth[v]) swap(u,v);
    int tmp=depth[u]-depth[v];
    for(int i=0;tmp;i++)
    {
        if(tmp&1) u=fa[u][i];
        tmp>>=1;
    }
    if(u==v) return u;
    for(int i=20;i>=0&&u!=v;i--)
    {
        if(fa[u][i]!=fa[v][i])
        {
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(s,0);
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        cout<<lca(u,v)<<endl;
    }
    return 0;
}

CRT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=15;
void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int tmp=y;
    y=x-(a/b)*y;
    x=tmp;
}
ll n;
ll a[maxn],b[maxn];
ll mul=1,ans;
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++) mul*=a[i];
    for(int i=1;i<=n;i++)
    {
        ll m=mul/a[i];
        ll inv,y;
        exgcd(m,a[i],inv,y);
        ans=(ans+b[i]*m*inv%mul)%mul;
    }
    cout<<(ans+mul)%mul<<endl;
    return 0;
}

高斯消元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=105;
int n;
double a[maxn][maxn];
bool guass()
{
    for(int i=1;i<=n;i++)
    {
        int maxp=i;
        for(int j=i+1;j<=n;j++)
        {
            if(fabs(a[j][i])>fabs(a[maxp][i])) maxp=j;
        }
        if(a[maxp][i]==0) return false;
        swap(a[maxp],a[i]);
        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;
            double tmp=a[j][i]/a[i][i];
            for(int k=i+1;k<=n+1;k++) a[j][k]-=a[i][k]*tmp;
        }
    }
    return true;
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n+1;j++)
        {
            scanf("%lf",&a[i][j]);
        }
    }
    if(!guass()) printf("No Solution\n");
    else
    {
        for(int i=1;i<=n;i++) printf("%.2lf\n",a[i][n+1]/a[i][i]);
    }
    return 0;
}