数论算法

1、线性筛

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=200005;
int prime[maxn];
bool not_prime[maxn];
int main()
{
int n,cnt=0;
scanf("%d",&n);
memset(not_prime,0,sizeof(not_prime));
not_prime[1]=true;
for(inti=2;i<=n;i++)
{
if(!not_prime[i])
prime[++cnt]=i;
for(intj=1;j<=cnt;j++)
{
if(prime[j]*i>n) break;
not_prime[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
for(inti=1;i<=cnt;i++)
printf("%d ",prime[i]);
return 0;
}

2、埃氏筛

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
inline int read()
{
char c;
c=getchar();
for(;c>'9'||c<'0';c=getchar());
int sum=0;
for(;c<='9'&&c>='0';c=getchar())sum=sum*10+c-48;
return sum;
}
int n,m;
bool f[10010000];
int main()
{
n=read(),m=read();
memset(f,true,sizeof(f));
f[0]=f[1]=false;
for(inti=2;i<=n;i++)
if(f[i])
for(intj=2;i*j<=n;f[i*j]=false,j++);
for(inti=1;i<=m;i++)
{
int x;
x=read();
if(f[x])printf("Yes\n");
elseprintf("No\n");
}
return 0;
}

3、拓展欧几里得算法

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int x,y;
int exgcd(int a,int b)
{
if(!b)
{
x=1;
y=0;
return a;
}
else
{
int t;
intd=exgcd(b,a%b);
t=x;
x=y;
y=t-a/b*x;
return d;
}
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
exgcd(a,b);
// cout<<__gcd(a,b)<<endl;
cout<<x<<" "<<y<<endl;
return 0;
}

4、GCD&LCM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int gcd(int a,int b)
{
if(!b) returna;
else returngcd(b,a%b);
}
int lcm(int a,int b)
{
returna/gcd(a,b)*b;
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
cout<<gcd(a,b)<<" "<<lcm(a,b)<<endl;
return 0;
}

5、分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int main()
{
long long n;
scanf("%lld",&n);
for(long longi=2;i<=n;i++)
{
while(n!=i)
{
if(n%i==0)
{
printf("%lld*",i);
n=n/i;
}
elsebreak;
}
}
printf("%lld",n);
return 0;
}

6、大数翻倍法

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[233],mo[233];
int gcd(int a,int b)
{
if(!b) returna;
else returngcd(b,a%b);
}
int lcm(int a,int b)
{
returna/gcd(a,b)*b;
}
int main()
{
int n;
scanf("%d",&n);
for(inti=1;i<=n;i++)
scanf("%d%d",&a[i],&mo[i]);
intans=0,nowmo=1;
for(inti=1;i<=n;i++)
{
intother=a[i],othermo=mo[i];
if(othermo>nowmo)
{
swap(ans,other);
swap(nowmo,othermo);
}
while(ans%othermo!=other)
ans+=nowmo;
nowmo=lcm(nowmo,othermo);
}
printf("%d",ans);
}

7、快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>    
using namespace std;
const int MOD = 1007;
int xx(int a,int n,int MOD)
{
int ret=1;
int tmp=a%MOD;
while(n)
{
if(n&1)
ret=ret*tmp%MOD;
tmp=tmp*tmp%MOD;
n>>=1;
}
return ret;
}
int main()
{
int m,n;
while(scanf("%d%d",&m,&n)==2)
{
printf("%d\n",xx(m,n,MOD));
}
}

高精度算法

1、高精度加法

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
//只限两个非负整数相加
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int L=110;
string add(string a,string b)
{
string ans;
int na[L]={0},nb[L]={0};
int la=a.size(),lb=b.size();
for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
int lmax=la>lb?la:lb;
for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
if(na[lmax]) lmax++;
for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
return ans;
}
int main()
{
string a,b;
while(cin>>a>>b) cout<<add(a,b)<<endl;
return 0;
}

2、高精度减法

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
//只限大的非负整数减小的非负整数 
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int L=110;
string sub(string a,string b)
{
string ans;
int na[L]={0},nb[L]={0};
int la=a.size(),lb=b.size();
for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
int lmax=la>lb?la:lb;
for(int i=0;i<lmax;i++)
{
na[i]-=nb[i];
if(na[i]<0) na[i]+=10,na[i+1]--;
}
while(!na[--lmax]&&lmax>0) ;lmax++;
for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
return ans;
}
int main()
{
string a,b;
while(cin>>a>>b) cout<<sub(a,b)<<endl;
return 0;
}

3、高精度乘法

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
//高精度乘法a,b,均为非负整数
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int L=110;
string mul(string a,string b)
{
string s;
int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();/
fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);
for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';
for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
for(int i=1;i<=La;i++)
for(int j=1;j<=Lb;j++)
nc[i+j-1]+=na[i]*nb[j];
for(int i=1;i<=La+Lb;i++)
nc[i+1]+=nc[i]/10,nc[i]%=10;
if(nc[La+Lb]) s+=nc[La+Lb]+'0';
for(int i=La+Lb-1;i>=1;i--)
s+=nc[i]+'0';
return s;
}
int main()
{
string a,b;
while(cin>>a>>b) cout<<mul(a,b)<<endl;
return 0;
}

4、高精度除法

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<iostream>  
#include<cstring>
#include<algorithm>
using namespace std;
const int L=110;
int sub(int *a,int *b,int La,int Lb)
{
if(La<Lb) return -1;
if(La==Lb)
{
for(int i=La-1;i>=0;i--)
if(a[i]>b[i]) break;
else if(a[i]<b[i]) return -1;
}
for(int i=0;i<La;i++)
{
a[i]-=b[i];
if(a[i]<0) a[i]+=10,a[i+1]--;
}
for(int i=La-1;i>=0;i--)
if(a[i]) return i+1;
return 0;
}
string div(string n1,string n2,int nn)
{
string s,v;
int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;
fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);
for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';
for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';
if(La<Lb || (La==Lb && n1<n2)) {
//cout<<0<<endl;
return n1;}
int t=La-Lb;
for(int i=La-1;i>=0;i--)
if(i>=t) b[i]=b[i-t];
else b[i]=0;
Lb=La;
for(int j=0;j<=t;j++)
{
int temp;
while((temp=sub(a,b+j,La,Lb-j))>=0)
{
La=temp;
r[t-j]++;
}
}
for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10;
while(!r[i]) i--;
while(i>=0) s+=r[i--]+'0';
//cout<<s<<endl;
i=tp;
while(!a[i]) i--;
while(i>=0) v+=a[i--]+'0';
if(v.empty()) v="0";
//cout<<v<<endl;
if(nn==1) return s;
if(nn==2) return v;
}
int main()
{
string a,b;
while(cin>>a>>b) cout<<div(a,b,1)<<endl;
return 0;
}

图论算法

1、图的遍历-BFS

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
#include<iostream>
#include <queue>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
int visited[N + 1] = {0, };
void BFS(int start)
{
queue<int> Q;
Q.push(start);
visited[start] = 1;
while (!Q.empty())
{
int front = Q.front();
cout << front << "";
Q.pop();
for (int i = 1; i <= N; i++)
{
if (!visited[i] &&maze[front - 1][i - 1] == 1)
{
visited[i] = 1;
Q.push(i);
}
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
BFS(i);
}
return 0;
}

2、图的遍历-DFS

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<iostream>
#include <stack>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = {0, };
void DFS(int start)
{
stack<int> s;
s.push(start);
visited[start] = 1;
bool is_push = false;
while (!s.empty())
{
is_push = false;
int v = s.top();
for (int i = 1; i <= N; i++)
{
if (maze[v - 1][i - 1] == 1&& !visited[i])
{
visited[i] = 1;
s.push(i);
is_push = true;
break;
}
}
if (!is_push)
{
cout << v << " ";
s.pop();
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}

3、最小生成树-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
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
#include<cstdio>  
#include<iostream>
using namespace std;
const int MAXN = 30;
int pa[MAXN];
int rank[MAXN];
int n,sum;
struct node{
int x,y;
int w;
}edge[MAXN*MAXN];
bool cmp(node p,node q){
return p.w<q.w;
}
void make_set(int x)
{
pa[x] = x;
rank[x] = 0;
}
int find_set(int x)
{
if(x != pa[x])
pa[x] = find_set(pa[x]);
return pa[x];
}
void union_set(int x, int y,int w)
{
x = find_set(x);
y = find_set(y);
if(x == y)return ;
if(rank[x] > rank[y])
{
pa[y] = x;
}
else
{
pa[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
sum+=w;
}
int main()
{
// freopen("input.txt","r",stdin);
while(cin>>n){
if(!n) break;
char ch;
int m,k=0;
for (int i = 0; i < n - 1; i++)
{
cin >> ch >> m;
for (int j = 0; j < m; j++)
{
cin >> ch >> edge[k].w;
edge[k].x = i;
edge[k].y = ch - 'A';
k++;
}
}
sort(edge,edge+k,cmp);
for(int i=0;i<MAXN;i++)
make_set(i);
sum=0;
for(int i=0;i<k;i++)
union_set(edge[i].x,edge[i].y,edge[i].w);
cout<<sum<<endl;
}
}

4、最小生成树-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<cstdio>  
using namespace std;
const int maxn=30;
const int INF=1000000;
int graph[maxn][maxn];
int lowcost[maxn],closet[maxn];
int visited[maxn];
int n;
void createGraph(){
memset(graph,0,sizeof(graph));
memset(lowcost,0,sizeof(lowcost));
memset(closet,0,sizeof(closet));
memset(visited,0,sizeof(visited));
int a;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
scanf("%d",&a);
if(a==0)
graph[i][j]=graph[j][i]=INF;
else
graph[i][j]=graph[j][i]=a;
}
}
void prim(){
int sum=0;
visited[0]=1;
for(int i=0;i<n;i++){
lowcost[i]=graph[i][0];
closet[i]=0;
}
for(int i=1;i<n;i++){
int minn=lowcost[0],k=0;
for(int j=0;j<n;j++){
if(!visited[j] && lowcost[j]<minn){
minn=lowcost[j];
k=j;
}
}
sum+=minn;
visited[k]=1;
for(int t=0;t<n;t++){
if(!visited[t] && lowcost[t]>graph[t][k]){
lowcost[t]=graph[t][k];
closet[t]=k;
}
}
}
printf("%d\n",sum);
}
int main()
{
// freopen("input.txt","r",stdin);
while(~scanf("%d",&n)){
if(!n) break;
createGraph();
prim();
}
}

5、最短路径-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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=100005;
struct dqs
{
int f,t,c;
}hh[maxn];
int tot=0,first[maxn],next[maxn],d[maxn];
bool used[maxn];
void build(int f,intt,int c)
{
hh[++tot]=(dqs){f,t,c};
next[tot]=first[f];
first[f]=tot;
}
queue<int>q;
int n,m,s,e;
void spfa(int s)
{
d[s]=0;
q.push(s);
used[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
used[x]=0;
for(int i=first[x];i;i=next[i])
{
int u=hh[i].t;
if(d[u]>d[x]+hh[i].c)
{
d[u]=d[x]+hh[i].c;
if(!used[u])
{
q.push(u);
used[u]=1;
}
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
for(int i=1;i<=n;i++)
d[i]=1e9;
for(int i=1;i<=m;i++)
{
int f,t,c;
scanf("%d%d%d",&f,&t,&c);
build(f,t,c);
build(t,f,c);
}
spfa(s);
printf("%d\n",d[e]);
return 0;
}

6、最短路径-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
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100005;
struct dqs
{
int f,t,c;
}hh[maxn];
int tot=0,first[maxn],next[maxn],d[maxn];
bool used[maxn];
void build(int f,intt,int c)
{
hh[++tot]=(dqs){f,t,c};
next[tot]=first[f];
first[f]=tot;
}
int n,m,s,e;
void Dijkstra()
{
for(int i=1;i<=n;i++)
d[i]=1e9;
d[s]=0;
while(true)
{
int x=-1;
for(int i=1;i<=n;i++)
{
if(!used[i])
if(x==-1||d[i]<d[x])
x=i;
if(x==-1) break;
used[x]=1;
for(int i=first[x];i;i=next[i])
{
int u=hh[i].t;
if(d[u]>d[x]+hh[i].c)
d[u]=d[x]+hh[i].c;
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
......
}

7、最短路径-Floyd

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<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=1005;
int d[maxn][maxn];
int n,m,s,e;
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&i!=k&&k!=j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=1e9;
for(int i=1;i<=m;i++)
{
int f,t,c;
scanf("%d%d%d",&f,&t,&c);
d[f][t]=c;
d[t][f]=c;
}
floyd();
printf("%d\n",d[s][e]);
return 0;
}

8、最近公共祖先(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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=250010;
struct dqs
{
int f,t,c;
}hh[maxn<<1];
int tot=0,fa[maxn][31],next[maxn],first[maxn],f[maxn],d[maxn];
void build(int ff,inttt,int cc)
{
hh[++tot]=(dqs){ff,tt,cc};
next[tot]=first[ff];
first[ff]=tot;
}
int deep[maxn];
void dfs(int x,int sd)
{
deep[x]=sd;
int u;
for(int i=first[x];i;i=next[i])
{
u=hh[i].t;
if(!deep[u]&&u)
{
f[u]=x;
d[u]=d[x]+hh[i].c;
dfs(u,sd+1);
}
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y])
swap(x,y);
int deepcha=deep[x]-deep[y];
for(int i=0;i<=30;i++)
{
if(1<<i&deepcha)
x=fa[x][i];
}
for(int i=30;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
if(x!=y)
return f[x];
return x;
}
int main()
{
int n;
scanf("%d",&n);
int u,v,c;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&c);
build(u,v,c);
build(v,u,c);
}
dfs(0,0);
for(int i=0;i<n;i++)
fa[i][0]=f[i];
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
int xx=lca(u,v);
printf("%d\n",d[u]+d[v]-2*d[xx]);
}
return 0;
}

排序算法

1、快速排序

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<cstdio>
inline void Rd(int&res){
res=0;char c;
while(c=getchar(),c<48);
dores=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
}
int res[100005];
void qsort(int L,intR){
if(L>=R)return;
int key=res[L],low=L,high=R;
while(low<high){
while(low<high&&key<=res[high])--high;
if(low<high)res[low++]=res[high];
while(low<high&&key>=res[low])++low;
if(low<high)res[high--]=res[low];
}
res[low]=key;
qsort(L,low-1),qsort(low+1,R);
}
int main(){
int n;Rd(n);
for(int i=1;i<=n;i++)Rd(res[i]);
qsort(1,n);
for(int i=1;i<=n;i++)
printf("%d%c",res[i],i==n?'\n':' ');
}

2、归并排序

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
#include<cstdio>
inline void Rd(int&res){
res=0;char c;short f=1;
while(c=getchar(),c<48&&c!='-');
do if(c=='-')f=-1;
elseres=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
res*=f;
}
const int M=1000005;
int a[M],b[M];
void Merge(int L,intR){
if(L==R)return;
int mid=L+R>>1;
Merge(L,mid);Merge(mid+1,R);
int low=L,high=mid+1,c=L;
while(low<=mid&&high<=R)//[L,low)
if(a[low]<=a[high])b[c++]=a[low++];
else b[c++]=a[high++];
while(low<=mid)b[c++]=a[low++];
while(high<=R)b[c++]=a[high++];
for(int i=L;i<=R;i++)a[i]=b[i];
}
int main(){
int n;Rd(n);
for(int i=1;i<=n;i++)Rd(a[i]);
Merge(1,n);
for(int i=1;i<=n;i++)
printf("%d%c",a[i],i==n?'\n':' ');
}

3、堆排序

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
#include<cstdio>
inline void Rd(int&res){
res=0;char c;
while(c=getchar(),c<48);
dores=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
}
struct Heap{
static const int M=100005;
int heap[M],sz;
Heap(){sz=0;}
inline void swap(int *a,int *b){
if(a==b)return;
int t=*a;*a=*b;*b=t;
}
int top(){return heap[1];}
void push(int val){
heap[++sz]=val;
int pos=sz;
while(pos>>1){
int nxt=pos>>1;
if(heap[nxt]>heap[pos])swap(&heap[nxt],&heap[pos]);
else break;
pos=nxt;
}
}
void pop(){
int pos=1;
heap[pos]=heap[sz--];
while((pos<<1)<=sz){
int nxt=pos<<1;
if(nxt+1<=sz&&heap[nxt+1]<heap[nxt])++nxt;
if(heap[nxt]<heap[pos])swap(&heap[pos],&heap[nxt]);
else break;
pos=nxt;
}
}
}q;
int main(){
int n;Rd(n);
for(int i=1,x;i<=n;++i)Rd(x),q.push(x);
for(int i=1;i<=n;i++){
printf("%d",q.top());
putchar(i==n?'\n':' ');
q.pop();
}
}

4、基数排序

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<cstdio>
inline void Rd(int&res){
res=0;char c;
while(c=getchar(),c<48);
dores=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
}
static const intM=100005,S=10;
inta[M],s[S][M],sz[S];
int main(){
int n;Rd(n);
for(int i=1;i<=n;++i)Rd(a[i]);
for(int base=1,i=1;i<S;i++,base*=10){
for(int j=0;j<S;j++)sz[j]=0;
for(int j=1;j<=n;j++){
int step=a[j]/base%10;
s[step][++sz[step]]=a[j];
}
int tot=0;
for(int j=0;j<S;j++)
for(int k=1;k<=sz[j];k++)
a[++tot]=s[j][k];
}
for(int i=1;i<=n;i++)
printf("%d%c",a[i],i==n?'\n':' ');
}

STL容器

STL 容器是一些模板类,提供了多种组织数据的常用方法。常用的STL容器包括pair(组合)、list(列表,类似于链表)、vector(向量,类似于数组)、priority_queue(优先队列)、set(集合)、map(映射)、stack(栈)等,通过模板的参数我们可以指定容器中的元素类型。

1、pair

相当于一个Struct,访问方式举个例子:pair p; 那么第一个成员便是p.first、第二个p.second,pair使用起来很方便,简单快速高效,可以当做一个二元struct使用,而且它定义了比较的方法,先根据第一个成员比较,在根据第二个,所以如果你的比较运算符是这样,那么你就不需要定义比较函数了,而struct是不能直接进行比较的,构造pair的方法:make_pair。例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>  
#include <algorithm>
#include <cstring>
#include <utility>
#include <functional>
using namespace std;
const int N = 1010;
typedef pair<int, int> p;
p a[N];
int main() {
int k = 0;
a[k++] = p(3, 4);
a[k++] = p(3, 100);
a[k++] = p(1, 2);
a[k++] = p(4, 10);
sort(a, a+k, greater<p>());
for (int i = 0; i < k; i++) printf("%d %d\n", a[i].first, a[i].second);
return 0;
}

2、List

list是一个循环链表。这个容器的特点:快速插入和删除。作用和vector差不多,但内部是用链表实现。这个容器不支持随机访问,你不能[]或者利用通用算法操作,比如说要排序的话你只能利用成员函数比如list.sort(),而且很重要的一点,list的size()函数是线性的,因为是以遍历函数distance实现的。
例:HDU 5127

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
#include <cstdio>  
#include <algorithm>
#include <cstring>
#include <list>
#include <utility>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> p;
list<p> l;
int main() {
int n;
while (scanf("%d", &n), n) {
l.clear();
for (int i = 0; i < n; i++) {
LL a, b;
int t;
scanf("%d %I64d %I64d", &t, &a, &b);
if (t == 1) l.push_back(p(a, b));
else if (t == -1) l.erase(find(l.begin(), l.end(), p(a, b)));
else {
list<p>::iterator i = l.begin();
LL ans = i->first * a + i->second * b;
for (++i; i != l.end(); i++) ans = max(ans, i->first * a + i->second * b);
printf("%I64d\n", ans);
}
}
}
return 0;
}

3、vector

相当于一个不定长数组,利用这个你可以添加任意多的元素,容器以连续数组的方式存储元素序列,可以将vector 看作是以顺序结构实现的线性表。当我们在程序中需要使用动态数组时,vector将是一个理想的选择。这个完全相当于把一个数组当成一个元素来进行使用了,可以直接相等,赋值操作等。比较经典的使用包括:
a、利用vector防止递归爆栈。
b、利用vector来实现邻接表。
c、利用vector存储空间占用比较大的矩阵。

4、priority_queue

优先队列其实就是堆,在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先被删除。优先队列具有最高级先出(first in, largest out)的行为特征。重载有两种方式:直接在struct或者class内部定义;定义比较结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//内部定义:  
struct node{
int x, y;
node(int x = 0, int y = 0) : x(x), y(y) {}
bool operator < (const node &a) const { return x > a.x; }
};
priority_queue<node> q;
//定义比较结构
struct node{
int x, y;
node(int x = 0, int y = 0) : x(x), y(y) {}
};
struct cmp {
bool operator () (const node &a, const node &b) { return a.x< b.x; }
};

priority_queue,cmp> q;
priority_queue的应用:贪心
例1:POJ 2010
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
#include <cstdio>  
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
int l[N], r[N];
struct calf {
int s, a;
}ca[N];
bool cmp(calf x, calf y) { return x.s < y.s; }
int main() {
int n, c, f;
scanf("%d %d %d", &n, &c, &f);
for (int i = 1; i <= c; i++) scanf("%d %d", &ca[i].s, &ca[i].a);
sort(ca+1, ca+1+c, cmp);
n >>= 1;
priority_queue <int> q;
int sum = 0;
for (int i = 1; i <= n; i++) q.push(ca[i].a), sum += ca[i].a;
l[n] = sum;
for (int i = n+1; i <= c-n-1; i++) {
if (ca[i].a >= q.top()) l[i] = sum;
else {
sum -= q.top() - ca[i].a;
q.pop(); q.push(ca[i].a);
l[i] = sum;
}
}
sum = 0;
while (!q.empty()) q.pop();
for (int i = c; i >= c-n+1; i--) q.push(ca[i].a), sum += ca[i].a;
r[c-n+1] = sum;
for (int i = c-n; i >= n+2; i--) {
if (ca[i].a >= q.top()) r[i] = sum;
else {
sum -= q.top() - ca[i].a;
q.pop(); q.push(ca[i].a);
r[i] = sum;
}
}
int ans = -1;
for (int i = c-n; i >= n+1; i--) {
if (r[i+1] + l[i-1] + ca[i].a <= f) {
ans = ca[i].s;
break;
}
}
printf("%d\n", ans);
return 0;
}

priority_queue的应用:加速搜索
例2:CSU 1780
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 <cstdio>    
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
struct po{
int x, y, w, di;
bool operator > (const po &a)const {return w > a.w;}
};
int n, m, vis[505][505], v[505][505][4];
int maze[510][510], r1, c1, r2, c2, t;
char st[5];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int bfs()
{
priority_queue <po, vector<po>, greater<po> > q;
q.push((po){r1, c1, maze[r1][c1], 0});
memset(vis, 0, sizeof(vis));
vis[r1][c1] = 1;
while (!q.empty()){
po t = q.top(); q.pop();
if (t.x==r2 && t.y==c2) return t.w;
for (int i = 0; i < 4; i++){
int nx = t.x+dx[i], ny = t.y+dy[i];
if (nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny] || maze[nx][ny]==-1) continue;
q.push((po){nx, ny, t.w+maze[nx][ny], 0}); vis[nx][ny] = 1;
}
}
return -1;
}
int bfs1()
{
memset(v, 0, sizeof(v));
priority_queue <po, vector<po>, greater<po> > q;
q.push((po){r1, c1, maze[r1][c1], -1});
v[r1][c1][0] = v[r1][c1][1] = v[r1][c1][2] = v[r1][c1][3] = 1;
while(!q.empty()){
po t = q.top(); q.pop();
if (t.x==r2 && t.y==c2) return t.w;
for(int i = 0;i < 4;i ++){
if(i == t.di) continue;
int nx = t.x+dx[i], ny = t.y+dy[i];
if(nx<1 || nx>n || ny<1 || ny>m || v[nx][ny][i] || maze[nx][ny]==-1) continue;
q.push((po){nx, ny, t.w+maze[nx][ny], i}); v[nx][ny][i] = 1;
}
}
return -1;
}
int main()
{
while (~scanf("%d %d %d %d %d %d", &n, &m, &r1, &c1, &r2, &c2)){
memset(maze, -1, sizeof(maze));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j){
scanf("%s", st);
if (st[0] != '*') sscanf(st, "%d", &maze[i][j]);
}
printf("Case %d: %d %d\n", ++t, bfs(), bfs1());
}
return 0;
}

5、set

set,顾名思义,集合,无重复元素,插入的元素自动按增序排列。内部实现: 红黑树,一种平衡的二叉排序树。容器最主要的功能就是判重,也可以进行二分查找。要允许重复元素,选用multiset即可。容器性能:set与map的查找、删除、插入性能都是对数复杂度。没有定义比较方式的元素需要进行重载,重载方式和优先队列一样。
set的应用:判重
例:UVA 11572

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>  
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
int a[1000001];
set<int> s;
int main() {
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", a+i);
s.clear();
int st = 0, en = 0, ma = 0;
while (en < n) {
while (en < n && !s.count(a[en])) s.insert(a[en++]);
ma = max(ma, en-st);
s.erase(a[st++]);
}
printf("%d\n", ma);
}
return 0;
}

6、map

这个容器适用于那些需要进行映射(可以根据Key找到对应的Value,作为hash还是不错的),因此map是关联数组。要允许重复元素,使用multimap。
map的应用:映射
例:HDU 4460

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
#include <cstdio>  
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
const int N = 1010;
int vis[N], d[N];
map <string, int> mp;
vector<int> G[N];
int solve(int x, int n) {
int ma = 0, res, cnt = 1;
queue<int> q; q.push(x);
memset(vis+1, 0, sizeof(int) * (n+1));
memset(d+1, 0, sizeof(int) * (n+1));
vis[x] = 1;
while (!q.empty()) {
int t = q.front(); q.pop();
for (int i = 0; i < G[t].size(); i++) {
int y = G[t][i];
if (vis[y]) continue;
vis[y] = 1;
d[y] = d[t] + 1;
if (ma < d[y]) res = y, ma = d[y];
q.push(y); cnt++;
}
}
return cnt != n ? -1 : x == 1 ? res: ma;
}
int main() {
int n;
while (scanf("%d", &n), n) {
mp.clear();
for (int i = 1; i <= n; i++) G[i].clear();
char s[15], str[15];
for (int i = 1; i <= n; i++) scanf("%s", s), mp[s] = i;
int m;
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%s %s", s, str);
G[mp[s]].push_back(mp[str]);
G[mp[str]].push_back(mp[s]);
}
int ans = solve(1, n);
ans == -1 ? puts("-1") : printf("%d\n", solve(ans, n));
}
return 0;
}

7、stack

stack,栈在STL里面它属于容器适配器,对容器的重新包装,后进先出结构。
stack的应用:单调栈的实现
例:POJ 2559

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 <cstdio>  
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
using namespace std;
typedef long long LL;
const int N = 100010;
stack<int> s;
template <class T>
inline void read(T &res) {
char c; res = 0;
while (!isdigit(c = getchar()));
while (isdigit(c)) res = res * 10 + c - '0', c = getchar();
}
int l[N], r[N];
LL h[N];
int main() {
int n;
while (read(n), n) {
for (int i = 0; i < n; i++) read(h[i]);
while (!s.empty()) s.pop();
for (int i = 0; i < n; i++) {
while (!s.empty() && h[s.top()] >= h[i]) s.pop();
l[i] = s.empty() ? 0 : s.top()+1;
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n-1; i >= 0; i--) {
while (!s.empty() && h[s.top()] >= h[i]) s.pop();
r[i] = s.empty() ? n : s.top();
s.push(i);
}
LL ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, (LL)h[i] * (r[i] - l[i]));
printf("%I64d\n", ans);
}
return 0;
}

字符串算法

1、trie树

例:HDU 1075

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
#include <cstdio>
#include <string>
using namespace std;
struct trie
{
trie * next[26];
int index;
};
trie *thead;
char dic[1000000][20];
inline trie * newnode()
{
int i;
trie *t;
t=(trie*)malloc(sizeof(trie));
memset(t,0,sizeof(trie));
return t;
}
void insert(trie * s,char x[],int pos)
{
int i;
trie *t;
for(i=0; x[i] ;i++) {
if(s->next[ x[i]-'a' ] ) s=s->next[ x[i]-'a' ];
else{
t=newnode();
s->next[x[i]-'a' ]=t;
s=t;
}
}//for
s->index=pos;
}
void deltrie(trie * s)
{
int i;
for(i=0; i < 26;i++) {
if(s->next[i] ) deltrie(s->next[i]);
}
free(s);
s=NULL;
}
int find(trie *s, char x[])
{
int i;
if(x[0] == 0)return -1;
for(i=0; x[i] ;i++) {
if(s->next[ x[i]-'a' ] ) s=s->next[ x[i]-'a' ];
elsebreak;
}
if(x[i]==0) returns->index;
else return -1;
}
int main()
{
int t,n,i,j,all;
charword[20],mars[20],ch;
thead=newnode();
while(scanf("%s",word)==1)
if(word[0]=='S')break;
i=1;
while(scanf("%s",dic[i])==1&& dic[i][0]!='E') {
scanf("%s",mars);
insert(thead,mars,i);
i++;
}
all=i;
while(scanf("%s",word)==1)
if(word[0]=='S')break;
getchar(); j=0;
while(scanf("%c",&ch)==1&& ch!='E') {
if(ch>='a'&& ch<='z') {
mars[j]=ch;j++;
}
else {
mars[j]=0;
t=find( thead , mars );
j=0;
if(t>0)printf("%s",dic[t]);
else if(mars[0]!=0)printf("%s",mars);
printf("%c",ch);
}
}//while
deltrie(thead);
}

2、KMP

例:HDU 2087

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
#include<iostream>  
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=1000+10;
char s1[maxn],s2[maxn];
int next[maxn],ans;
void Kmp()
{
int n=strlen(s1);
int m=strlen(s2);
if(m>n) return ;
int j=0;
for(int i=0;i<n;++i)
{
while(j&&s1[i]!=s2[j]) j=next[j];
if(s1[i]==s2[j]) j++;
if(j==m) {ans++;j=0;}
}
}
void getnext()
{
int n=strlen(s2);
next[0]=next[1]=0;
for(int i=1;i<n;++i)
{
int j=next[i];
while(j&&s2[i]!=s2[j]) j=next[j];
next[i+1]=(s2[i]==s2[j])?j+1:0;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(~scanf("%s",s1))
{
if(s1[0]=='#') break;
scanf("%s",s2);
ans=0;
getnext();
Kmp();
printf("%d\n",ans);
}
return 0;
}

3、AC自动机

例:UVA 11468

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
#include<iostream>  
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=2000+10;
double p[110],dp[maxn][110];
bool vis[maxn][110];
int ch[maxn][63],val[maxn],next[maxn],size,n;
int idx(char c)
{
if(c>='0'&&c<='9') return c-'0';
if(c>='a'&&c<='z') return c-'a'+10;
return c-'A'+10+26;
}
void Init()
{
memset(vis,0,sizeof(vis));
memset(ch[0],0,sizeof(ch[0]));
memset(next,0,sizeof(next));
memset(val,0,sizeof(val));
memset(p,0,sizeof(p));
size=0;
}
void insert(const char *s)
{
int u=0,len=strlen(s);
for(int i=0;i<len;++i)
{
int c=idx(s[i]);
if(!ch[u][c])
{
ch[u][c]=++size;
memset(ch[size],0,sizeof(ch[size]));
val[size]=0;
}
u=ch[u][c];
}
val[u]=1;
}
void build()
{
queue<int>q;
for(int i=0;i<62;++i)
{
if(ch[0][i]) q.push(ch[0][i]);
}
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<62;++i)
{
int v=ch[u][i];
if(!v) {ch[u][i]=ch[next[u]][i];continue;}
q.push(v);
int j=next[u];
while(j&&!ch[j][i]) j=next[j];
next[v]=ch[j][i];
val[v]|=val[next[v]];
}
}
}
double f(int u,int L)
{
if(L==0) return 1.0;
if(vis[u][L]) return dp[u][L];
vis[u][L]=true;
dp[u][L]=0;
for(int i=0;i<62;++i)
{
if(!val[ch[u][i]])
dp[u][L]+=p[i]*f(ch[u][i],L-1);
}
return dp[u][L];
}
char str[110];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t,tcase=0;
scanf("%d",&t);
while(t--)
{
tcase++;
Init();
int K;
scanf("%d",&K);
for(int i=0;i<K;++i)
{
scanf("%s",str);
insert(str);
}
scanf("%d",&n);
char c[3];
for(int i=0;i<n;++i)
{
scanf("%s",c);
scanf("%lf",&p[idx(c[0])]);
}
build();
int L;
scanf("%d",&L);
double ans=f(0,L);
printf("Case #%d: %lf\n",tcase,ans);
}
return 0;
}