小康迷糊了的復習小結
1.字典樹
2.線段樹
3.KMP演算法
4.字串哈希
5.二分圖匹配
6.最長遞增子序列
7.最長公共子串/子序列
8.拓展歐幾里得
9.快速冪
10.組合數學問題（卡特蘭數）
11.樹的直徑
12.最短路問題
13.最小生成樹
14.并查集
15.歐拉回路
16.連通塊問題
17.多源bfs問題
18.差分，二分
19.前綴和
1.字典樹模板
#include <bits/stdc++.h>
using namespace std;
const int N=27;
struct trienode
{
char val;
trienode** son;
int cnt;
trienode(char c)
{
val=c;
son=new trienode*[N];
for(int i=0;i<N;i++)
son[i]=NULL;
cnt=0;
}
};
trienode* root;
void insert(string s)
{
trienode* p=root;
for(int i=0;i<s.size();i++)
{
int c=s[i]-'a';
if(!p->son[c])
{
p->son[c]=new trienode(c);
}
p=p->son[c];
}
p->cnt++;
}
int quy(string q)
{
trienode* p=root;
for(int i=0;i<q.size();i++)
{
int a=q[i]-'a';
if(!p->son[a])
return 0;
p=p->son[a];
}
return p->cnt;
}
int main()
{
root=new trienode(' ');
for(int i=0;i<3;i++)
{
string s;
getline(cin,s);
insert(s);
}
for(int i=0;i<3;i++)
{
string s;
getline(cin,s);
cout<<quy(s)<<endl;
}
return 0;
}
2.線段樹
1.單點修改，區間查詢
#include <bits/stdc++.h>
#define N 10000
using namespace std;
int maxv=0;
void bulid(int arr[],int tree[],int node,int start,int end)
{ if(start==end)
{
tree[node]=arr[start];
}
else
{int mid=(start+end)/2;
int left_node=2*node+1;
int right_node=2*node+2;
bulid(arr,tree,left_node,start,mid);
bulid(arr,tree,right_node,mid+1,end);
tree[node]=max(tree[left_node],tree[right_node]);
}
}
void update(int arr[],int tree[],int node,int start,int end,int idx,int val)
{
if(start==end)
{
arr[idx]=val;
tree[idx]=val;
}
else{
int mid=(start+end)/2;
int left_node=2*node+1;
int right_node=2*node+2;
if(idx>=start&&idx<=mid)
{
update(arr,tree,left_node,start,mid,idx,val);
}
if(idx>mid&&idx<=end)
{
update(arr,tree,right_node,mid+1,end,idx,val);
}
tree[node]=max(tree[left_node],tree[right_node]);
}
}
int qry(int arr[],int tree[],int node,int start,int end,int L,int R)
{
if(L<=start&&end<=R)
return tree[node];
else
{
int mid=(start+end)/2;
int left_node=node*2+1;
int right_node=node*2+2;
if(L<=mid)
maxv=max(maxv,qry(arr,tree,left_node,start,mid,L,R));
if(R>mid)
maxv=max(maxv,qry(arr,tree,right_node,mid+1,end,L,R));
}
return maxv;
}
int main()
{
int arr[]={1,3,5,7,9,11};
int size=6;
int tree[N]={0};
bulid(arr,tree,0,0,size-1);
cout<<qry(arr,tree,0,0,size-1,4,5)<<endl;
return 0;
}
2.區間修改
3.線段樹求區間最大值
#include <bits/stdc++.h>
#define N 10000
using namespace std;
int maxv=0;
void bulid(int arr[],int tree[],int node,int start,int end)
{ if(start==end)
{
tree[node]=arr[start];
}
else
{int mid=(start+end)/2;
int left_node=2*node+1;
int right_node=2*node+2;
bulid(arr,tree,left_node,start,mid);
bulid(arr,tree,right_node,mid+1,end);
tree[node]=max(tree[left_node],tree[right_node]);
}
}
void update(int arr[],int tree[],int node,int start,int end,int idx,int val)
{
if(start==end)
{
arr[idx]=val;
tree[idx]=val;
}
else{
int mid=(start+end)/2;
int left_node=2*node+1;
int right_node=2*node+2;
if(idx>=start&&idx<=mid)
{
update(arr,tree,left_node,start,mid,idx,val);
}
if(idx>mid&&idx<=end)
{
update(arr,tree,right_node,mid+1,end,idx,val);
}
tree[node]=max(tree[left_node],tree[right_node]);
}
}
int qry(int arr[],int tree[],int node,int start,int end,int L,int R)
{
if(L<=start&&end<=R)
return tree[node];
else
{
int mid=(start+end)/2;
int left_node=node*2+1;
int right_node=node*2+2;
if(L<=mid)
maxv=max(maxv,qry(arr,tree,left_node,start,mid,L,R));
if(R>mid)
maxv=max(maxv,qry(arr,tree,right_node,mid+1,end,L,R));
}
return maxv;
}
int main()
{
int arr[]={1,3,5,7,9,11};
int size=6;
int tree[N]={0};
bulid(arr,tree,0,0,size-1);
cout<<qry(arr,tree,0,0,size-1,4,5)<<endl;
return 0;
}
3.kmp演算法（字串匹配）
#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char text[100];
char pattern[100];
int i,n,m,j;
int sum=0;
void pre_table(char pattern[],int pre[],int n)
{
int len=0;
i=1;
pre[0]=0;
n=strlen(pattern);
while(i<n)
{if(pattern[i]==pattern[len])
{
len++;
pre[i]=len;
i++;
}
else
{
if(len>0)
{
len=pre[len-1];
}
else
{
pre[len]=len;
i++;
}
}
}
}
void move_pre(char pattern[],int pre[])
{
int n=strlen(pattern);
for(int i=n-1;i>0;i--)
pre[i]=pre[i-1];
pre[0]=-1;
}
int kmp(char text[],char pattern[],int pre[])
{
//n=strlen(pattern);
//m=strlen(text)
i=0;j=0;
while(i<m)
{
if(j==n-1&&pattern[j]==text[i])
{
sum++;
j=pre[j];
}
if(pattern[j]==text[i]||j==-1)
{
i++;
j++;
}
else
{
j=pre[j];
}
}
return sum;
}
int main()
{
int N;
cin>>N;
while(N--)
{scanf("%s",pattern);
scanf("%s",text);
n=strlen(pattern);
m=strlen(text);
int pre[n]={0};
pre_table(pattern,pre,n);
move_pre(pattern,pre);
kmp(text,pattern,pre);
cout<<sum<<endl;}
return 0;
}
4.字串哈希
以poj_3461為例
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef unsigned long long ll;
const int base = 31;
const int maxn = 1000050;
char sub[maxn],str[maxn];
ll xp[maxn];
ll hash[maxn];
int main()
{
int T,i;
scanf("%d",&T);
xp[0]=1;
for(i=1;i<maxn;i++)
xp[i]=xp[i-1]*base;
while(T--)
{
memset(sub,0,sizeof(sub));
memset(str,0,sizeof(str));
scanf("%s",sub);
scanf("%s",str);
int L=strlen(sub);
int n=strlen(str);
ll sub_num=0;
for(i=L-1;i>=0;i--)
{
sub_num=sub_num*base+sub[i];
}
hash[n]=0;
for(i=n-1;i>=0;i--)
{
hash[i]=hash[i+1]*base+str[i];
}
int ans=0;
for(i=0;i<=n-L;i++) ///Caution!!! it is (i<=n-L) or (i<n-L+1)
{
if(sub_num==hash[i]-hash[i+L]*xp[L])
ans++;
}
printf("%d\n",ans);
}
return 0;
}
5.二分圖匹配（匈牙利演算法，km演算法）
匈牙利演算法
#include <stdio.h>
#include <stdlib.h>
int e[101][101];
int match[101];
int book[101];
int dfs(int u)
{
int i;
for(i=1;i<=n;i++)
{
if(book[i]==0&&e[u][i]==1)
{
book[i]=1;
if(match[i]==0||dfs(match[i]))
{
match[i]=u;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,t1,t2,sum=0;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&t1,&t2);
e[t1][t2]=1;
}
for(i=1;i<=n;i++)
match[i]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
book[j]=0;
if(dfs(i))
sum++;
}
printf("%d",sum);
return 0;
}
KM演算法
//以hdu 2255為例
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int G[N][N];
int Lx[N],Ly[N];
bool visX[N],visY[N];
int linkX[N],linkY[N];
bool dfs(int x){
visX[x]=true;
for(int y=1;y<=n;y++){
if(!visY[y]){
int temp=Lx[x]+Ly[y]-G[x][y];
if(temp==0){
visY[y]=true;
if(linkY[y]==-1 || dfs(linkY[y])){
linkX[x]=y;
linkY[y]=x;
return true;
}
}
}
}
return false;
}
void update(){
int minn=INF;
for(int i=1;i<=n;i++)
if(visX[i])
for(int j=1;j<=n;j++)
if(!visY[j])
minn=min(minn,Lx[i]+Ly[j]-G[i][j]);
for(int i=1;i<=n;i++){
if(visX[i])
Lx[i]-=minn;
if(visY[i])
Ly[i]+=minn;
}
}
int KM(){
memset(linkX,-1,sizeof(linkX));
memset(linkY,-1,sizeof(linkY));
for(int i=1;i<=n;i++){
while(true){
memset(visX,false,sizeof(visX));
memset(visY,false,sizeof(visY));
if(dfs(i))
break;
else
update();
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans+=G[linkY[i]][i];
return ans;
}
int main(){
while(scanf("%d",&n)!=EOF&&(n)){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&G[i][j]);
printf("%d\n",KM());
}
return 0;
}
最長遞增子序列（LIS）動態規劃實作
#define MAX 10000
#include<iostream>
#include<vector>
using namespace std;
int n,a[MAX+1],L[MAX];
int list()
{
L[0]=a[0];
int length=1;
for(int i=1;i<n;i++)
{
if(L[length-1]<a[i])
L[length++]=a[i];
else{
L[lower_bound(L,L+length,a[i])-a]=a[i];
}
}
return length;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<list()<<endl;
return 0;
}
最長公共子串/子序列（動態規劃）
//最長公共子串
int n=strlen(b);
int m=strlen(a);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(i==0||j==0)
dp[i][j]=0;
if(b[i]==a[j])
dp[i][j]=dp[i-1][j-1]+1;
if(b[i]!=a[j])
dp[i][j]=0;
max1=max(max1,dp[i][j]);
//最長公共子序列
int n=strlen(b);
int m=strlen(a);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(i==0||j==0)
dp[i][j]=0;
if(b[i]==a[j])
dp[i][j]=dp[i-1][j-1]+1;
if(b[i]!=a[j])
dp[i][j]=max(dp[i-1][j]+dp[i][j-1]);
max1=max(max1,dp[i][j]);
8.拓展歐幾里得
#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int temp=x;
x=y;
y=temp-(a/b)*y;
return r;
}
int main()
{
int g,a,b;
int x,y;
cin>>a>>b;
g=exgcd(a,b,x,y);
cout<<x<<endl;
return 0;
}
9.快速冪
#include <iostream>
using namespace std;
typedef long long LL;
int mod=100000;
int qmi(int a,int k)
{
int res=1;
while(k)
{
if(k&1) res=(ll)res*a%mod;
a=(ll)a*a%mod;
k>>=1;
}
return res;
}
10.組合數學（卡特蘭數）
f(n)=Cn2n/n+1
#include<iostream>
using namespace std;
typedef long long ll;
ll g(ll a,ll b)
{
ll n=1;
if(b>a/2+1)
{
b=a-b;
}
for(ll i=1;i<=b;i++)
{
n*=(a-i+1);
n/=i;
}
return n;
}
int main()
{
int a,b,c;
cin>>a>>b;
c=g(a,b);
cout<<c<<endl;
return 0;
}
11.樹的直徑
//bfs求法
#include <iostream>
#include<queue>
#include<vector>
using namespace std;
#define MAX 10000
#define INFTY (1<<30)
int tgt;
struct edge
{
int t,w;
edge(int a,int b)
{
t=a;
w=b;
}
};
vector<edge> g[MAX];
int n,d[MAX];
bool vis[MAX];
int cnt;
void bfs(int s)
{
for(int i=0;i<n;i++)
d[i]=INFTY;
queue<int> q;
q.push(s);
d[s]=0;
int u;
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=0;i<g[u].size();i++)
{
edge e=g[u][i];
if(d[e.t]==INFTY)
{d[e.t]=d[u]+e.w;
q.push(e.t);
}
}
}
}
void solve()
{
bfs(0);
int maxv=0;
int temp=0;
bfs(0);
for(int i=0;i<n;i++)
{
if(d[i]==INFTY)
continue;
if(maxv<d[i])
{
maxv=d[i];
tgt=i;
}
}
bfs(tgt);
maxv=0;
for(int i=0;i<n;i++)
{
if(d[i]==INFTY)
continue;
maxv=max(maxv,d[i]);
}
cout<<maxv<<endl;
}
int main()
{
int s,t,w;
cin>>n;
for(int i=0;i<n-1;i++)
{
cin>>s>>t>>w;
g[s].push_back(edge(t,w));
g[t].push_back(edge(s,w));
}
solve();
return 0;
}
//dfs求法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1e5+10;
int vis[maxn];
int dis[maxn];
struct node{
int to;
int val;
node(){}
node(int a,int b){
to=a;
val=b;
}
};
vector<node> v[maxn];
void dfs(int u){
for(int i=0;i<v[u].size();i++){
node tmp=v[u][i];
int to=tmp.to;
int val=tmp.val;
if(!vis[to]){
vis[to]=1;
dis[to]=dis[u]+val;
//cout<<dis[to]<<endl;
dfs(to);
}
}
}
int main(){
int n;
int a,b,c;
cin>>n;
for(int i=0;i<n-1;i++){
cin>>a>>b>>c;
v[a].push_back(node(b,c));
v[b].push_back(node(a,c));
}
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[1]=1;
dfs(1);
int tmp=0,u;
for(int i=1;i<=n;i++){
if(dis[i]>tmp) tmp=dis[i],u=i;
}
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[u]=1;
dfs(u);
tmp=0;
for(int i=1;i<=n;i++){
if(dis[i]>tmp) tmp=dis[i];
}
return 0;
}
12.最短路問題
迪杰斯特拉（單源最短路）
#include<stdio.h>
int main()
{
int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;
int inf=999999;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;i<=n;j++)
{
if(i==j)
{
e[i][j]=0;
}
else
e[i][j]=inf;
}
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
for(i=1;i<=n;i++)
dis[i]=e[1][i];
for(i=1;i<n;i++)
{
book[i]=0;
}
book[1]=1;
for(i=1;i<=n-1;i++)
{
min=inf;
for(j=1;j<=n;j++)
{
if(book[j]==0&&dis[j]<min)
{
min=dis[j];
u=j;
}
}
book[u]=1;
for(v=1;v<=n;v++)
{
if(e[u][v]<inf)
{
if(dis[v]>dis[u]+e[u][v])
dis[v]=dis[u]+e[u][v];
}
}
}
for(i=1;i<=n;i++)
printf("%d",dis[i]);
return 0;
}
弗洛伊德（多源最短路）
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
{
e[i][j]=e[i][k]+e[k][j];
}
最小生成樹
克魯斯卡爾演算法
#include<stdio.h>
struct edge
{
int u;
int v;
int w;
}node[100];
int n,m;
int f[7]={0};
int sum=0;
int count=0;
int getf(int v)
{
if(f[v]==v)
return v;
else{
f[v]=getf(f[v]);
return f[v];
}
}
int join(int v,int u)
{
int t1=getf(v);
int t2=getf(u);
if(t1!=t2)
{
f[t2]=t1;
return 1;
}
return 0;
}
int cmp(struct edge a,struct edge b)
{
return a.w>b.w;
}
int main()
{
int i;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&node[i].u,&node[i].v,&node[i].w);
}
sort(node+1,node+m+1,cmp);
for(int i=1;i<=m;i++)
{
f[i]=i;
}
for(i=1;i<=m;i++)
{
if(join(e[i].u,e[i].v))
{
count++;
sum+=e[i].w;
}
if(count==n-1)
break;
}
printf("%d",sum);
return 0;
}
14.并查集
//藍橋杯 修改陣列
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int a[maxn],f[maxn];
int getf(int x)
{
return f[x] = f[x] == x ? x:getf(f[x]);
}
int main()
{
for(int i=1;i<=maxn-1;i++)
f[i] = i;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
int nf = getf(a[i]);
a[i] = nf;
f[a[i]] = getf(nf+1);
}
for(int i=1;i<=n;i++) {
cout << a[i];
if(i != n)
cout << " ";
}
return 0;
}
15.歐拉路
#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
int in[1005];
int out[1005];
int main()
{
int n ,m;
int a,b;
int flag = 0;
int innum = 0,outnum = 0;
scanf("%d %d",&n,&m);
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(int i = 0;i < m;i++)
{
cin>>a>>b;
out[a]++;
in[b]++;
}
for(int i = 1;i <= n;i++)
{
if(in[i] == 0 && out[i] == 0)
{
flag = 1;
}
if(in[i] == out[i])
{
continue;
}
if(in[i] - out[i] == 1)
{
innum ++;
}
if(out[i] - in[i] == 1)
{
outnum ++;
}
}
if(innum + outnum > 2)
{
flag = 1;
}
if(flag)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
return 0;
}
16.連通塊問題（dfs)
#include<iostream>
using namespace std;
int n, m;
int ans;
char grass[110][110];
int vis[110][110];
int nx[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
bool in(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dfs(int x, int y) {
for (int i = 0; i <= 3; i++) {
int nowx = x + nx[i][0];
int nowy = y + nx[i][1];
if (in(nowx, nowy) && grass[nowx][nowy] == '#' && !vis[nowx][nowy]) {
vis[nowx][nowy] = 1;
dfs(nowx, nowy);
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> grass[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (grass[i][j] == '#' && !vis[i][j]) {
ans++;
vis[i][j] = 1;
dfs(i, j);
}
}
}
cout << ans;
return 0;
}
多源bfs問題
p1332為例
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
int sx[100005][3];
bool vis[505][505];
int maps[505][505];
int fx[4][2] = {{0,-1},{0,1},{1,0},{-1,0}};
struct node{
int x,y,steps;
};
queue <node> Q;
void p(int __x,int __y){
node _tmp;
_tmp.x = __x;
_tmp.y = __y;
_tmp.steps = 0;
Q.push(_tmp);
vis[__x][__y] = true;
return;
}
void bfs(){
while(!Q.empty()){
node tmp;
node t;
for(int i=0;i<=3;i++){
t = Q.front();
int xx = t.x+fx[i][0];
int yy = t.y+fx[i][1];
if(xx>=1&&xx<=n && yy>=1&&yy<=m && !vis[xx][yy]){
vis[xx][yy] = true;
tmp.x = xx;
tmp.y = yy;
tmp.steps = t.steps+1;
Q.push(tmp);
}
}
maps[t.x][t.y] = t.steps;
//cout<<"x: "<<t.x<<" y: "<<t.y<<endl;
Q.pop();
}
}
int main(){
memset(vis,false,sizeof(vis));
cin>>n>>m>>a>>b;
int _x,_y;
for(int i=1;i<=a;i++){
cin>>_x>>_y;
p(_x,_y);
}
for(int i=1;i<=b;i++){
cin>>sx[i][1]>>sx[i][2];
}
bfs();
for(int i=1;i<=b;i++){
cout<<maps[sx[i][1]][sx[i][2]]<<endl;
}
}
更新到這里，繼續學習會繼續更新，（借鑒了不少代碼，如果發現雷同，沒錯，我承認是我借鑒的哈哈哈哈）----主要是為了自我復習，學習演算法思想，所以代碼可能不嚴謹等等，勿噴勿噴！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/278903.html
標籤：其他