ACM模板集（更新中）

关闭同步流

1
2
3
ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

关闭同步之后，cin与scanf的执行效率相差无几

优化快读模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57)
    {
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=nc();
   	return x*f;
}

快写模板

1
2
3
4
5
6
7
8
9
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

手动打开O2开关：

1
#pragma GCC optimize(2)

快速幂模板

数字快速幂

1
2
3
4
5
6
7
8
9
10
11
12
//非递归快速幂
int qpow(int a, int n)
{
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

矩阵快速幂

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
struct Matrix 
{
    lint d[2][2];
    Matrix() {
        memset(d, 0, sizeof(d));
    }
//初始化部分
    Matrix operator* (const Matrix& x) {
        Matrix ans;
        for (int i = 0; i <= 1; ++i) {
            for (int j = 0; j <= 1; ++j) {
                for (int k = 0; k <= 1; ++k) {
                    ans.d[i][j] += (d[i][k] * x.d[k][j]) % m;
                }
                ans.d[i][j] = (((ans.d[i][j] % m) + m) % m);
            }
        }
        return ans;
    }
};
//重载乘号部分
Matrix fpow(Matrix a, lint n) {
    Matrix ans;
    ans.d[0][0] = ans.d[1][1] = 1;//初始化
    while (n) {
        if (n & 1) {
            ans = ans * a;
        }
        a = a * a;
        n >>= 1;
    }
    return ans;
}
    Matrix a;
    a.d[0][0] = 1;
    a.d[0][1] = 1;
    Matrix c;
    c.d[0][0] = 1;
    c.d[0][1] = 1;
    c.d[1][0] = 1;
    //构建Base矩阵部分
    c = fpow(c, n - 2);

素数筛

普通版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int IsPrime(int n)
{
    int i;
    if(n<2||(n!=2&&n%2==0))
        return 0;
    else
    {
        for(i=3;i*i<=n;i+=2)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}

埃式筛法

1
2
3
4
5
6
7
//埃式筛
for(int i=2;i<=n;i++){
	if(!vis[i]){
		prime[++cnt]=i;
		for(int j=1;j*i<=n;j++)vis[i*j]=true;
	}
}

欧拉筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//欧拉筛函数
void Euler_sieve(int n)
{
    int i,j,k;
    k=0;//保存素数的个数
    memset(vis,0,sizeof(int)*maxn);//初始化数组
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)//i是素数，则存起来
            prime[k++]=i;
        for(j=0;j<k;j++)//进行倍增，用i去乘以i之前(包括i)的素数
        {
            if(i*prime[j]>n)//倍增结果超出范围，退出
                break;
            vis[ i*prime[j] ]=1;//将倍增结果进行标记
            if(i%prime[j]==0)//i是前面某个素数的倍数时，也需要退出
                break;
        }
    }
}

约数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int c[N],p[N];
void divide(int n) {
    cnt = 0;
    for(int i = 2; i * i <= n; ++ i) {
        if(n % i == 0) {
            p[ ++ cnt] = i,c[cnt] = 0;
            while(n % i == 0) n /= i,c[cnt] ++ ;
        }
    }
    if(n > 1)//如果n是质数
        p[ ++ cnt] = n,c[cnt] = 1;
    for(int i = 1;i <= cnt; ++ i)
        cout << p[i] << "^" << c[i] << endl;
}

GCD

1
2
3
4
5
6
7
8
9
//1
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}C++
//2
int gcd(int a , int b){
return a%b==0? b:gcd(b,a%b);
}

lcm

1
2
3
int lcm(int a,int b){
	return a / gcd(a,b) * b;//先除后乘，以免溢出64位整数
}

反素数

如果某个正整数 n 满足如下条件，则称为是反素数： 任何小于 n 的数的正约数个数都小于 n 的正约数个数，即 n 是 …1…n 中正约数个数最多的数。

筛选出n以内的最大反素数

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
int p[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
ULL n;
ULL ans, ans_num;  
// ans 为 n 以内的最大反素数（会持续更新），ans_sum 为 ans                   
// 的因子数。
void dfs(int depth, ULL temp, ULL num, int up) {
    if (depth >= 16 || temp > n) return;
    if (num > ans_num) 
    {
	    ans = temp;
	    ans_num = num;
    }
    if (num == ans_num && ans > temp) ans = temp;
    for (int i = 1; i <= up; i++) {
 	   if (temp * p[depth] > n) break; 
  	  dfs(depth + 1, temp *= p[depth], num * (i + 1), i);
    }
    return;
}
    while (cin>>n))
    {
        ans_num = 0;
	    dfs(0, 1, 1, 60);
    	cout<<ans<<'\n';
    }

求欧拉函数

\(\varphi(N)=N \times \prod_{p\mid N}(1-\frac{1}{p})\)

1
2
3
4
5
6
7
8
9
10
11
12
inline int euler_one(int n)
{
    int ans = n;
    for(int i = 2;  i * i <= n; ++ i){
        if(n % i == 0){
            ans = ans / i * (i - 1);
            while(n % i == 0)n /= i;
        }
    }
    if(n > 1)ans = ans / n * (n - 1);
    return ans;
}

结合欧拉筛做法

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
void init(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i), phi[i] = i - 1; 
        // 性质一，素数指数为1的情形
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
            {
                phi[p * i] = phi[i] * p; 
                // 性质二，整除直接求解倍数
                break;
            }
            else
                phi[p * i] = phi[p] * phi[i]; 
            // 这时肯定互质，用性质三
        }
    }
}

并查集

1
2
3
4
5
6
7
 for(i=1;i<=n;i++)
        f[i]=i;
f[find(p2)]=find(p3);
int find(int k){
    if(f[k]==k)return k;
    return f[k]=find(f[k]);
}

扩展域并查集

1
2
3
4
5
6
7
//双倍初始化 
for(int i=1; i<=n*2; i++)
        f[i]=i;
f[y] = find(e[i].a + n);
        //本人和敌人的敌人放一间
        f[x] = find(e[i].b + n);
        //本人和敌人的敌人放一间

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
int st[N][20];
int lg[N];
int n,m;
    for(int i=2;i<=n;i++)
    {
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>st[i][0];
    }
    for(int j=1;j<=lg[n];j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
    int l,r;
    while(m--)
    {
        cin>>l>>r;
        int t=lg[r-l+1];
        cout<<max(st[l][t],st[r-(1<<t)+1][t])<<'\n';
    }

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int lowbit(int x)
{
	return x&-x;
}
void add(int x,int y )
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		tree[i]+=y;
	}
}
int sum(int x)
{
	if(x==0)
	{
		return 0;
	}
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		ans+=tree[i];
	}	
	return ans;
}

线段树

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
ll a[N];
ll w[N*4];
void pushup(const int u)
{
    w[u]=w[u*2]+w[u*2+1];
    //w[u]是区间和，u*2是左子树，u*2+1是右子树
    //节点表示的区间和等于两个子节点所表示的区间之和。
    //有了这个操作，我们就可以递归的求出每一个节点所表示的信息。
}
void build(const int u,int l,int r)
{
    if(l==r)
    //到达叶子节点
    {
        w[u]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    //将区间分成[l,mid]和[mid+1,r]进行递归构造
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    //位运算以便降低时间
    pushup(u);
    //由于子区间的区间和更新当前区间的和
    //你要不断pushup进行更新的意思
}
//1.单点查询操作
ll query1(int u,int l,int r,int p)
{
//其中u是根节点，l是左边，r是右边，p是要查询的点
if(l==r)
{
    return w[u];
    //到达叶子节点返回值就可以
}
else
{
    int mid=(l+r)/2;
    if(mid>=p)
    //如果查询的位置在左子树
    //就递归查询左子树
{
    return query1(u*2,l,mid,p);
}
else
//反之查询右子树
{
    return query1(u*2+1,mid+1,r,p);
}
}
//由于查询没有对区间和进行修改操作，因此不需要Pushup
}
//2.单点修改操作
ll update1(int u,int l,int r,int p,ll x)
{
    if(l==r)
    {
        w[u]=x;
        //到达叶子节点直接返回即可
    }
    else
    {
        int mid=(l+r)>>1;
        if(mid>=p)
        {
            update1(u*2,l,mid,p,x);
        }
        else
        {
            update1(u*2+1,mid+1,r,p,x);
        }
        pushup(u);
        //更新后要修改当前节点的和
    }
}
bool inrange(int L,int R,int l,int r)
{
    return (l<=L)&&(R<=r);
    //判断是否包含
}
//跟刚才那个是极端，这个就是毫无交集了
bool outrange(int L,int R,int l,int r)
{
    return (L>r)||(R<l);
    //判断两者的交集是否无解
}
//区间修改
ll lzy[N*4];
//重中之重的部分就是这一块，所谓的区间修改和区间修改相应的查询，都会变化
void maketag(int u,int len,ll x)
{
    lzy[u]+=x;
    //给这个点加上懒标记
    w[u]+=len*x;
    //这个点加上相应的值
}
//懒标记的下放
//肯定要分区间节点，左子树和右子树的下放
//注意要加上长度
void pushdown(int u,int L,int R)
{
    int Mid=(L+R)/2;
    maketag(u*2,Mid-L+1,lzy[u]);
    maketag(u*2+1,R-Mid,lzy[u]);
    lzy[u]=0;
    //tag的下放所以避免重复修改，当前层要清空标记
}
ll query(int u,int L,int R,int l,int r)
{
    if(inrange(L,R,l,r))
    {
        return w[u];
    }
    //和上面一样如果一样就进行包含求和
    else if(!outrange(L,R,l,r))
    {
        int Mid=(L+R)/2;
        //求平均操作
        pushdown(u,L,R);
        //下放操作
        return query(u*2,L,Mid,l,r)+query(u*2+1,Mid+1,R,l,r);
        //直接分左右查询
    }
    else
    {
        return 0;
    }
}
void update(int u,int L,int R,int l,int r,ll x)
{
    if(inrange(L,R,l,r))
    {
        maketag(u,R-L+1,x);
        //直接打上节点
    }
    //包含就直接下放
    else if(!outrange(L,R,l,r))
    {
        int Mid=(L+R)/2;
        pushdown(u,L,R);
        //进行下放，然后进行更新
        update(u*2,L,Mid,l,r,x);
        update(u*2+1,Mid+1,R,l,r,x);
    pushup(u);
    }
}
int main()
{
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
}
build(1,1,n);
rep(i,1,m)
{
    int op,x,y;
    cin>>op;
    ll k;
    if(op==1)
    {
        cin>>x>>y>>k;
        update(1,1,n,x,y,k);
    }
    else
    {
        cin>>x>>y;
        cout<<(query(1,1,n,x,y))<<'\n';
    }
}
}

最小生成树

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;
const int N=5005;
int k,n,m,cnt,sum,ai,bi,ci,head[N],dis[N],vis[N];
struct Edge
{
    int v,w,next;
}e[400005];
void add(int u,int v,int w)
{
    e[++k].v=v;
    e[k].w=w;
    e[k].next=head[u];
    head[u]=k;
}
//经典链式前向星，不会的话，我这篇写完下一篇就介绍这个（）
typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;
//最小堆，先取出的是最小的意思
void prim()
{
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()&&cnt<n)
    {
        int d=q.top().first,u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        cnt++;
        sum+=d;
        vis[u]=1;
        for(int i=head[u];i!=-1;i=e[i].next)
            if(e[i].w<dis[e[i].v])
            {
                dis[e[i].v]=e[i].w;
        q.push(make_pair(dis[e[i].v],e[i].v));
            }
    }
}
int main()
{
    memset(dis,127,sizeof(dis));
    //初始化为无限大
    memset(head,-1,sizeof(head));
    //链式前向星操作了
  	cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	cin>>ai>>bi>>ci;
        add(ai,bi,ci);
        add(bi,ai,ci);
    }
    prim();
    if (cnt==n)cout<<sum;
    else cout<<"orz";
}
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
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,u,v,total;
struct edge
{
int start;
int to;
long long val;	
}bian[100000000];
int f[10000000];
long long ans;
int find(int x)
{
	if(f[x]==x)
	{
		return x;
	}
	else
	{
	return 	f[x]=find(f[x]);
	}
}
bool cmp(edge a,edge b)
{
	return a.val<b.val;	
}
void kruskal()
{
	for(int i=1;i<=m;i++)
	{
		u=find(bian[i].start);
		v=find(bian[i].to);
		if(u==v)
		{
			continue;
		}
		ans+=bian[i].val;
		f[u]=v;
		total++;
		if(total==n-1)
		{
			break;
		}	
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		f[i]=i;	
	}
	for(int i=1;i<=m;i++)
	{
		cin>>bian[i].start>>bian[i].to>>bian[i].val;
	}
	sort(bian+1,bian+m+1,cmp);
	kruskal();
    if(total==n-1)
    {
cout<<ans;
    }
    else
    {
cout<<"orz";
    }	
}

字典树

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
const int N = 1000050;
int trie[N][26];
//N是树的层数
int cnt[N];
//看是不是以这个字母结尾，以及如果以这个字母结尾，究竟是结尾了多少次呢
int id;
//节点的编号
void insert(string s)
    //插入函数
    //需要一个字符串
{
	int p = 0;
    //插入自然也是从根节点开始，注意，根节点不存储字符
	for (int i = 0; i < s.size(); i++)
        //遍历字符串
	{
		int x = s[i] - 'a';
        //进行字母的一个小变形，因为我们得到0-25
		if (trie[p][x] == 0) trie[p][x] = ++id;
        //如果没有所对应的字母没有，就建一个
		p = trie[p][x];
        //然后接下来p就是这个刚建立的字母哩
	}
	cnt[p]++;
    //遍历完了，出循环，也就是说字母存储结束了，但我们需要知道，于是cnt用来记录结束否
}
//插入就讲完了，感觉还是很清晰的
int  find(string s)
{
	int p = 0;
    //查找一样从根节点开始查找
	for (int i = 0; i < s.size(); i++)
	{
        //遍历字符串
		int x = s[i] - 'a';
        //依然变形
		if (trie[p][x] == 0)return 0;
        //如果没有，就返回
		p = trie[p][x];
        //有的话就好了，就继续往下搜
	}
	return cnt[p];
    //遍历完了，康康是不是结束的那个节点，妙哉啊
}

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
a=" "+a;
   b=" "+b;
   la=a.length()-1;
   lb=b.length()-1;
   for (int i=2;i<=lb;i++)
   {     
   while(j&&b[i]!=b[j+1])
       j=kmp[j];    
      if(b[j+1]==b[i])j++;    
       kmp[i]=j;
      }
   j=0;
   for(int i=1;i<=la;i++)
   {
         while(j>0&&b[j+1]!=a[i])
          j=kmp[j];
         if (b[j+1]==a[i]) 
          j++;
         if (j==lb) 
	  {
	  cout<<i-lb+1<<'\n';
	  j=kmp[j];
	  }
      }
   for (int i=1;i<=lb;i++)
   cout<<kmp[i]<<" ";

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
const int N=6e5;
int n,m,s,t,tot=0,f[N][20],d[N],ver[2*N],Next[2*N],head[N];
queue<int> q;
void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void bfs()
{
    q.push(s);
    d[s]=1;//将根节点入队并标记
    while(q.size())
    {
        int x=q.front();q.pop();//取出队头
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[i];
            if(d[y])
                continue;
            d[y]=d[x]+1;
            f[y][0]=x;//初始化，因为y的父亲节点就是x
            for(int j=1;j<=t;j++)
                f[y][j]=f[f[y][j-1]][j-1];//递推f数组
            q.push(y);
        }
    }
}
int lca(int x,int y)
{
    if(d[x]>d[y])
        swap(x,y);
    //保证顺序
    for(int i=t;i>=0;i--)
        if(d[f[y][i]]>=d[x])
            y=f[y][i];//尝试上移y
    if(x==y)
        return x;//若相同说明找到了LCA
    for(int i=t;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i],y=f[y][i];
        }//尝试上移x、y并保持它们不相遇
    return f[x][0];//当前节点的父节点即为LCA
}
int main()
{
    cin>>n>>m>>s;
    t=log2(n)+1;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
        //添加边的过程
    }
    bfs();
    while(m--)
    {
        int a,b;
        cin>>a>>b;
 cout<<lca(a,b)<<'\n';
    }

三分

1
2
3
4
5
6
7
8
9
while (r - l > eps)
{
    mid = (l + r) / 2;
    double fl = f(mid - eps), fr = f(mid + eps);
    if (fl < fr)
        l = mid; 
    else
        r = mid;
}

最长上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int maxn = 103, INF = 0x7f7f7f7f;
int a[maxn], f[maxn];
int n,ans = -INF;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++) 
    {
        cin>>a[i];
        f[i] = 1;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j]+1);
    for(int i=1; i<=n; i++) 
        ans = max(ans, f[i]);
    cout<<ans;
    return 0;
}

贪心加二分

1
2
3
4
5
6
7
8
int len = 0;
for (int i = 0; i < n; ++i)
{
    if (dp[len] < A[i])
        dp[++len] = A[i];
    else
        *lower_bound(dp + 1, dp + len + 1, A[i]) = A[i];
}

最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
while (cin >> s1 >> s2)
{
    memset(dp, 0, sizeof(dp));
    int n1 = strlen(s1), n2 = strlen(s2);
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    cout << dp[n1][n2] << endl;
}

最长公共子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (cin >> s1 >> s2)
{
    memset(dp, 0, sizeof(dp));
    int n1 = strlen(s1), n2 = strlen(s2), ma = 0;
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = 0;
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            ma = max(ma, dp[i][j]);
    cout << ma << endl;
}

字符哈希

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
ull base=131;
struct data
{
    ull x,y;
}a[10010];
char s[10010];
int n,ans=1;
ull mod1=19260817;
ull mod2=19660813;
ull hash1(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod1;
    return ans;
}
ull hash2(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod2;
    return ans;
}
bool comp(data a,data b)
{
    return a.x<b.x;
}
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        a[i].x=hash1(s);
        a[i].y=hash2(s);
    }
    sort(a+1,a+n+1,comp);
    for (int i=2;i<=n;i++)
        if (a[i].x!=a[i-1].x || a[i-1].y!=a[i].y)
            ans++;
    cout<<ans;

61, 83, 113, 151, 211, 281, 379, 509 683, 911 / 一千以下

1217, 1627, 2179, 2909, 3881, 6907, 9209, / 一万以下

12281, 16381, 21841, 29123, 38833, 51787, 69061, 92083, / 十万以下

122777, 163729, 218357, 291143, 388211, 517619, 690163, 999983, / 百万以下

1226959, 1635947, 2181271, 2908361, 3877817, 5170427, 6893911, 9191891, / 千万以下

12255871, 16341163, 21788233, 29050993, 38734667, 51646229,68861641, 91815541, 一亿以下

1e9+7 和 1e9+9 // 十亿左右

122420729,163227661,217636919,290182597,386910137,515880193,687840301,917120411,/ 十亿以下

1222827239,1610612741, 3221225473ul, 4294967291ul / 十亿以上

匈牙利算法

最大匹配问题

最小点覆盖问题

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
int M, N;          
//M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; 
//邻接矩阵存图
int p[MAXN];         
//记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      
//记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 
            //记录状态为访问过
            if (p[j] == 0 || match(p[j])) 
            //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    
                //当前左侧元素成为当前右侧元素的新匹配
                return true; 
                //返回匹配成功
            }
        }
    return false; 
    //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}

珂朵莉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto split(ll pos)
// 若不支持C++14，auto须改为set<node>::iterator
{
    auto it = tree.lower_bound(node(pos, 0, 0)); // 寻找左端点大于等于pos的第一个节点
    // 若不支持C++11，auto须改为set<node>::iterator
    if (it != tree.end() && it->l == pos) // 如果已经存在以pos为左端点的节点，直接返回
        return it;
    it--; // 否则往前数一个节点
    ll l = it->l, r = it->r, v = it->v;
    tree.erase(it); // 删除该节点
    tree.insert(node(l, pos - 1, v)); // 插入<l,pos-1,v>和<pos,r,v>
    return tree.insert(node(pos, r, v)).first; // 返回以pos开头的那个节点的迭代器
                                               // insert默认返回值是一个pair，第一个成员是我们要的
}
1
2
3
4
5
6
void assign(ll l, ll r, ll v)
{
    auto end = split(r + 1), begin = split(l); // 顺序不能颠倒，否则可能RE
    tree.erase(begin, end); // 清除一系列节点
    tree.insert(node(l, r, v)); // 插入新的节点
}
1
2
3
4
5
6
void add(int l, int r, LL val)
{
    IT itl = split(l),itr = split(r+1);
    for (; itl != itr; ++itl) 
        itl->v += val;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll kth(ll l, ll r, ll k)
{
    auto end = split(r + 1);
    vector<pair<ll, ll>> v; // 这个pair里存节点的值和区间长度
    for (auto it = split(l); it != end; it++)
        v.push_back(make_pair(it->v, it->r - it->l + 1));
    sort(v.begin(), v.end()); // 直接按节点的值的大小排下序
    for (int i = 0; i < v.size(); i++) // 然后挨个丢出来，直到丢出k个元素为止
    {
        k -= v[i].second;
        if (k <= 0)
            return v[i].first;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll kth(ll l, ll r, ll k)
{
    auto end = split(r + 1);
    vector<pair<ll, ll>> v; // 这个pair里存节点的值和区间长度
    for (auto it = split(l); it != end; it++)
        v.push_back(make_pair(it->v, it->r - it->l + 1));
    sort(v.begin(), v.end()); // 直接按节点的值的大小排下序
    for (int i = 0; i < v.size(); i++) // 然后挨个丢出来，直到丢出k个元素为止
    {
        k -= v[i].second;
        if (k <= 0)
            return v[i].first;
    }
}
1
2
3
4
5
6
7
8
ll sum_of_pow(ll l, ll r, ll x, ll y)
{
    ll tot = 0;
    auto end = split(r + 1);
    for (auto it = split(l); it != end; it++)
        tot = (tot + qpow(it->v, x, y) * (it->r - it->l + 1)) % y; // qpow自己写一下
    return tot;
}

离散化

1
2
3
4
5
6
// a[i] 为初始数组,下标范围为 [1, n]
// len 为离散化后数组的有效长度
std::sort(a + 1, a + 1 + n);
len = std::unique(a + 1, a + n + 1) - a -1;  // 离散化整个数组的同时求出离散化后本质不同数的个数。
for (int i = 1; i <= n; ++i)
L[i]=std::lower_bound(a + 1, a + len + 1, x) - a;  // 查询 x 离散化后对应的编号
1
2
3
4
5
// std::vector<int> a, b; // b 是 a 的一个副本
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
for (int i = 0; i < n; ++i)
  b[i] = std::lower_bound(a.begin(), a.end(), b[i]) - a.begin();

最短路

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
vector <pair<int, int> > G[2001];
int T,n,m,u,v,w;
int dis[10000];
int cnt[10000];
bool in[10000];
void spfa()
{
	memset(dis, 0x3f3f, sizeof(dis));
	memset(in, 0, sizeof(in));
	memset(cnt, 0, sizeof(cnt));
	queue <int> q;
	q.push(1);
	dis[1]=0;
	in[1]=1;
	cnt[1]=1;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		in[u]=0;
		for(int i=0;i<G[u].size();i++)
		{
			v=G[u][i].first;
			w=G[u][i].second;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
			if(!in[v])
			{
				cnt[v]++;
				q.push(v);
				in[v]=1;
				if(cnt[v]>=n)
				{
					cout<<"YES"<<'\n';
						return;
				}
			}	
			}
		}	
	}	
	cout<<"NO"<<'\n';
}
int main()
{
	cin>>T;
	for (int  t = 0; t < T; t++){
		cin>>n>>m;
		for (int i = 1; i <= n; i++){
			G[i].clear();
		}
		for (int i = 0; i < m; i++){
			cin>>u>>v>>w;
			G[u].push_back(make_pair(v, w));
			if (w >= 0){
				G[v].push_back(make_pair(u, w)); 
			} 
		}
		spfa();
	}

Dij

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
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int ,int>
const int INF=1e10;
const int N=1000010;
int n,m,s;
int dis[N];
int vis[N];
vector<PII>E[N];
void dj(int s)
{
	for(int i=1;i<=n;i++)
	{
		dis[i]=INF;
		vis[i]=0;
	}
    //初始化每个点都没有去过
	dis[s]=0;
    //距离为0
	priority_queue<PII,vector<PII>,greater<PII> >q;
	q.push({0,s});
    //放进去
	while(!q.empty())
{
int t=q.top().second;
	q.pop();
		if(vis[t])
        {
			continue;
		}
        //访问过就跳过
		vis[t]=1;	
        //不然标记为已经访问过哦
	for(int i=0,l=E[t].size();i<l;i++)
        //枚举他到的边
	{
		int v=E[t][i].first;
        //这是到哪个边
		int w=E[t][i].second;
        //权值
		if(dis[v]>dis[t]+w)
		{		
			dis[v]=dis[t]+w;
            //如果当前这个点离这个边的距离比我们到当前点的距离+权值还大
			q.push({dis[v],v});
            //更新并放入		
		}		
		}		
	}	
	}
int main()
{
	 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>s;
int u,v,w;
for(int i=0;i<m;i++)
{
	cin>>u>>v>>w;
	E[u].push_back({v,w});
    //邻接表存储到哪个边和权值
	}	
	dj(s);
    //然后进入算法，直接从s开始
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<" ";
        //计算距离，单源
	}
	return 0;
}

Floyd

1
2
3
4
5
6
7
8
9
10
for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);//松弛
			}
		}
	}

组合数选举

1
2
3
4
5
6
7
8
9
10
11
void init()
{
    rep(i,0,N)
{
    c[i][0]=1;
rep(j,1,i)
{
    c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
}