OI算法复习
2024-08-28 15:38:55
搜集一些算法，赛前背一背有好处的
转自各大网站
前排感谢：hzwer、风了咕凉
前辈。。。Orz
快速读入：
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
经典快排：虽说C++直接sort就好了。。。
#include <iostream> using namespace std; void Qsort(int a[], int low, int high)
{
if(low >= high)
return;
int first = low;
int last = high;
int key = a[first];
while(first < last)
{
while(first < last && a[last] >= key)
--last;
a[first] = a[last];
while(first < last && a[first] <= key)
++first;
a[last] = a[first];
}
a[first] = key;
Qsort(a, low, first-);
Qsort(a, first+, high);
}
归并排序：
template <typename T>
void MergeSort (T data[], int size)
{
if ( size> )
{
//预处理
int mid=size/;
int numOfleft=mid;
int numOfright=size-mid;
T* left=new T[numOfleft];
T* right=new T[numOfright];
//分
std::copy(data, data+numOfleft, left);
std::copy(data+numOfleft, data+size, right);
MergeSort(left, numOfleft);
MergeSort(right, numOfright);
//合
std::merge(left, left+numOfleft, right, right+numOfright, data);
//清理
delete[] left;
delete[] right;
}
}
堆排：
template <typename T>
void heap_down (T data[], int i, const int& size)
{
int p=i*+;
while ( p<size )
{
if ( p+<size )
{
if ( data[p]<data[p+] )
++p;
}
if ( data[i]<data[p] )
{
std::swap(data[p], data[i]);
i=p;
p=i*+;
}
else
break;
}
}
template <typename T>
void HeapSort (T data[], int size)
{
int i;
for (i=(size-)/; i>=; --i)
heap_down(data, i, size);
for (i=size-; i>; --i)
{
std::swap(data[], data[i]);
heap_down(data, , i);
}
}
拓扑排序：
#include<iostream>
#include<cstdio>
using namespace std; struct Edge
{
int to,next;
}E[];
int head[],r[],s[];
int node=; int n; void insert(int u,int v)
{
E[++node]=(Edge){v,head[u]};
head[u]=node;
r[v]++;
} void topsort()
{
int t=,top=;
for(int i=;i<=n;i++)
if(!r[i])
{
s[++top]=i;
}
while(t<=top)
{
int x=s[t++];
for(int i=head[x];i;i=E[i].next)
{
r[E[i].to]--;
if(!r[E[i].to])
{
s[++top]=E[i].to;
}
}
}
}
kahn算法（NOIP2013车站分级为例子）纯过程形式：
#include<iostream>
#include<cstring>
using namespace std; const int MAXN=+;
int n,m,ans=;
int B[MAXN]={},R[MAXN]={},SK[MAXN]={};//R储存入度 SK储存入度为0的点
bool A[MAXN]={},F[MAXN]={},E[MAXN][MAXN]={};//F判断点是否已被访问 E判断两点是否存在边 int main()
{
/*cin>>n>>m;
for(int i=1;i<=m;i++)
{
int s;
memset(A,0,sizeof(A));
cin>>s;
for(int j=1;j<=s;j++)
{
cin>>B[j];
A[B[j]]=1;
}
for(int j=B[1];j<=B[s];j++)
if(!A[j])
for(int k=1;k<=s;k++)
if(!E[j][B[k]])
{
E[j][B[k]]=1;
R[B[k]]++;
}
}*///初始化
int top;
while()
{
top=;
for(int i=;i<=n;i++)//遍历n个点
if(!R[i]&&!F[i])//如果入度为0且没有被访问过，则加入SK数组
{
SK[++top]=i;//加入SK数组
F[i]=;//i点已被访问
}
if(top==)break;//如果所有的点都被访问则跳出
for(int i=;i<=top;i++)
for(int j=;j<=n;j++)
if(E[SK[i]][j])//判断是否有边
{
E[SK[i]][j]=;//将边移除
R[j]--;//入度-1
}
ans++;
}
cout<<ans<<endl;
return ;
}
并查集：
int find(int x)
{
while(f[x]!=) x=f[x];
return x;
}
快速幂：
int modexp(int a,int b,int n)
{
int ret=;
int tmp=a;
while(b)
{
if(b&0x1) ret=ret*tmp%n;
tmp=tmp*tmp%n;
b>>=;
}
return ret;
}
欧几里得算法：
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
拓展欧几里德算法：
int gcd(int a,int b,int &x,int &y){
if (b==){
x=,y=;
return a;
}
int q=gcd(b,a%b,y,x);
y-=a/b*x;
return q;
}
spfa：
struct Edge
{
int to,w,next;
}E[];
int node=,head[]; void insert(int u,int v,int w)
{
node++;
E[node]=Edge{v,w,head[u]};
head[u]=node;
} int spfa(int s,int t)
{
int dist[];
bool vis[];
memset(dist,0x7f,sizeof(dist));
memset(vis,,sizeof(vis));
dist[s]=;vis[s]=;
queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int q=Q.front();Q.pop();
for(int i=head[q];i;i=E[i].next)
if(dist[E[i].to]>dist[q]+E[i].w)
{
dist[E[i].to]=dist[q]+E[i].w;
if(!vis[E[i].to])
{
Q.push(E[i].to);
vis[E[i].to]=;
}
}
vis[q]=;
}
return dist[t];
}
spfa_dfs判负环：
#include<iostream>
#include<cstring>
using namespace std; struct Edge
{
int to,w,next;
}E[];
int node=,head[],dist[];
bool vis[]; int n,m;
bool flag; void insert(int u,int v,int w)
{
E[++node]=(Edge){v,w,head[u]};
head[u]=node;
} void spfa_dfs(int s)
{
vis[s]=;
for(int i=head[s];i;i=E[i].next)
{
if(dist[E[i].to]>dist[s]+E[i].w)
{
if(vis[E[i].to]){flag=;return;}
else
{
dist[E[i].to]=dist[s]+E[i].w;
spfa_dfs(E[i].to);
}
}
}
vis[s]=;
} bool check()
{
flag=;
memset(dist,0x7f,sizeof(dist));
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
dist[i]=;
spfa_dfs(i);
if(flag) return ;
}
return ;
}
floyd:
const int maxn=,
INF=;
int n,Dist[maxn][maxn],Graph[maxn][maxn];
int minn=INF;
void floyd()
{
//memcpy(Graph,Dist,sizeof(Dist));
for(int k=;k<=n;k++)
{/*拓展求最小环
for(int i=1;i<k;i++)
for(int j=i+1;j<k;j++)
minn=min(minn,Dist[i][j]+Graph[j][k]+Graph[k][i]);*/
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
int temp=Dist[i][k]+Dist[k][j];
if(temp<Dist[i][j])
Dist[i][j]=Dist[j][i]=temp;
}
}
}
Dijkstra:
#include <iostream>
#include <cstring>
using namespace std; #define MAXN 10000000 int n,e;
int matrix[][];
int dist[]; void Dijkstra(int s)
{
int u,minn;
bool vis[];
memset(vis,,sizeof(vis));
for(int i=;i<n;i++)
if(matrix[s][i]>)
dist[i]=matrix[s][i];
else dist[i]=MAXN;
vis[s]=;dist[s]=;
for(int i=;i<n;i++)
{
minn=MAXN;
for(int j=;j<n;j++)
if(!vis[j]&&dist[j]<minn)
{
u=j;
minn=dist[j];
}
vis[u]=;
for(int j=;j<n;j++)
if(!vis[j]&&matrix[u][j]>&&minn+matrix[u][j]<dist[j])
dist[j]=minn+matrix[u][j];
}
} int main()
{
int v;
cin>>n;
cin>>e;
memset(matrix,,sizeof(matrix));
for(int i=;i<e;i++)
{
int x,y,w;
cin>>x>>y>>w;
matrix[x][y]=w;
}
Dijkstra();
cin>>v;
cout<<dist[v];
return ;
}
线段树：详见Codevs1082线段树练习3
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; struct node
{
int left,right,flag;
long long sum;
}tree[]; int n,q;
int a[]; void build(int node,int left,int right)
{
tree[node].left=left;tree[node].right=right;
if(left==right)
{
tree[node].sum=a[left];
return;
}
int mid=(left+right)>>;
build(node<<,left,mid);
build(node<<|,mid+,right);
tree[node].sum=tree[node<<].sum+tree[node<<|].sum;
} void pushdown(int node)
{
int x=tree[node].right-tree[node].left+;
tree[node<<].flag+=tree[node].flag;
tree[node<<|].flag+=tree[node].flag;
tree[node<<].sum+=(x-(x>>))*tree[node].flag;
tree[node<<|].sum+=(x>>)*tree[node].flag;
tree[node].flag=;
} void update(int node,int left,int right,int x)
{
int mid=(tree[node].left+tree[node].right)>>;
tree[node].sum+=(right-left+)*x;
if(tree[node].left==left&&tree[node].right==right)
{
tree[node].flag+=x;
return;
}
if(tree[node].left==tree[node].right) return;
if(tree[node].flag>) pushdown(node);
if(right<=mid) update(node<<,left,right,x);
else if(left>mid) update(node<<|,left,right,x);
else
{
update(node<<,left,mid,x);
update(node<<|,mid+,right,x);
}
tree[node].sum=tree[node<<].sum+tree[node<<|].sum;
} long long query(int node,int left,int right)
{
int mid=(tree[node].left+tree[node].right)>>;
if(tree[node].left==left&&tree[node].right==right)
return tree[node].sum;
if(tree[node].flag>) pushdown(node);
if(right<=mid)
return query(node<<,left,right);
else if(left>mid)
return query(node<<|,left,right);
else
return query(node<<,left,mid)+query(node<<|,mid+,right);
}
树状数组：
详见
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std; int n,m;
int f[]; int lowbit(int x)
{
return x&(-x);
} void update(int x,int num)
{
while(x<=n)
{
f[x]+=num;
x+=lowbit(x);
}
} int sum(int x)
{
int sum=;
while(x>)
{
sum+=f[x];
x-=lowbit(x);
}
return sum;
} int main()
{
n=read();
for(int i=;i<=n;i++)
update(i,read());
m=read();
for(int i=;i<=m;i++)
{
int a=read(),x=read(),y=read();
if(a==)update(x,y);
if(a==)printf("%d\n",sum(y)-sum(x-));
}
return ;
}
分块法：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std; int n,m,q,block;
int a[],b[],pos[],add[]; void reset(int x)
{
int l=(x-)*block+,r=min(x*block,n);
for(int i=l;i<=r;i++)
b[i]=a[i];
sort(b+l,b+r+);//对单个块内进行排序
} int find(int x,int z)//单个块内二分查找
{
int l=(x-)*block+,r=min(x*block,n);
int last=r;
while(l<=r)
{
int mid=(l+r)>>;
if(b[mid]<z) l=mid+;
else r=mid-;
}
return last-l+;
} void update(int x,int y,int z)
{
if(pos[x]==pos[y])//同个块则暴力修改
for(int i=x;i<=y;i++) a[i]=a[i]+z;
else//不同块修改左右两边的块
{
for(int i=x;i<=pos[x]*block;i++) a[i]=a[i]+z;
for(int i=(pos[y]-)*block+;i<=y;i++) a[i]=a[i]+z;
}
reset(pos[x]);reset(pos[y]);
for(int i=pos[x]+;i<pos[y];i++)//其余块用add标记，表示增加了z
add[i]+=z;
} int query(int x,int y,int z)
{
int sum=;
if(pos[x]==pos[y])//单个块暴力查找
{
for(int i=x;i<=y;i++)
if(a[i]+add[pos[i]]>=z) sum++;
}
else//多个块左右两边的块暴力查找
{
for(int i=x;i<=pos[x]*block;i++)
if(a[i]+add[pos[i]]>=z) sum++;
for(int i=(pos[y]-)*block+;i<=y;i++)
if(a[i]+add[pos[i]]>=z) sum++;
}
for(int i=pos[x]+;i<pos[y];i++)//其余块每个二分查找
sum+=find(i,z-add[i]);
return sum;
} int main()
{
scanf("%d %d",&n,&q);
block=(int)sqrt(n);//每个块的大小
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
pos[i]=(i-)/block+;
b[i]=a[i];
}
if(n%block) m=n/block+;//计算块的个数，如有多余则+1
else m=n/block;
for(int i=;i<=m;i++) reset(i);//对每个块进行块内排序
for(int i=;i<=q;i++)
{
char ch;int x,y,z;
scanf("\n%c %d %d %d",&ch,&x,&y,&z);
if(ch=='M') update(x,y,z);
else printf("%d\n",query(x,y,z));
}
return ;
}
倍增算法：
RMQ：这里借鉴了一下黄学长的模板。。。Orz膜拜前辈
#include<iostream>
#include<cmath>
#include<iostream>
using namespace std;
int A[];
int MX[][];
int n,q;
void RMP_INIT()
{
for(int i=;i<=n;i++)
MX[i][]=A[i];
int m=log(n)/log();
for(int i=;i<=m;i++)
for(int j=n;j>;j--)
{
MX[j][i]=MX[j][i-];
if(j+(<<(i-))<=n)MX[j][i]=max(MX[j][i],MX[j+(<<(i-))][i-]);
}
}
int RMP(int l,int r)
{
int m=log(r-l+)/log();
return max(MX[l][m],MX[r-(<<m)+][m]);
}
KMP算法：
#include<iostream>
#include<cstring>
using namespace std; char S[],T[];
int ls,lt;
int next[]; void initnext(char *t,int *next)
{
int j=;
int len=strlen(t);
memset(next,,sizeof(next));
for(int i=;i<len;i++)
{
while(j&&t[i]!=t[j]) j=next[j];
if(t[i]==t[j]) j++;
next[i+]=j;
}
} int KMP(char *s,char *t)
{
int j=,ans=;
int ls=strlen(s),lt=strlen(t);
for(int i=;i<ls;i++)
{
while(j&&s[i]!=t[j]) j=next[j];
if(s[i]==t[j]) j++;
if(j==lt)
{
ans++;
j=next[j];
}
}
return ans;
}
高斯消元：感谢浙大学长。。。Orz
#include<iostream>
#include<cmath>
using namespace std; #define eps 1e-9
const int MAXN=;
double a[MAXN][MAXN],x[MAXN]; //方程的左边的矩阵和等式右边的值，求解之后 x存的就是结果
int equ,var;//方程数和未知数个数
/* *返回0表示无解，1表示有解*/
int Gauss()
{
int i,j,k,col,max_r;
for(k=,col=;k<equ&&col<var;k++,col++)
{
max_r=k;
for(i=k+;i<equ;i++)
if(fabs(a[i][col])>fabs(a[max_r][col])) max_r=i;
if(fabs(a[max_r][col])<eps) return ;
if(k!=max_r)
{
for(j=col;j<var;j++) swap(a[k][j],a[max_r][j]);
swap(x[k],x[max_r]);
}
x[k]/=a[k][col];
for(j=col+;j<var;j++) a[k][j]/=a[k][col];
a[k][col]=;
for(i=;i<equ;i++)
if(i!=k)
{
x[i]-=x[k]*a[i][k];
for(j=col+;j<var;j++) a[i][j]-=a[k][j]*a[i][col];
a[i][col]=;
}
}
return ;
}
分解质因数：感谢浙大学长。。。Orz
long long fac[],fac_num;
void getfactor(int num)
{
fac_num=;
for(int i=;i*i<=num;i++)
{
if(num%i==)
{
fac[fac_num++]=i;
while(num%i==) num/=i;
}
}
if(num>) fac[fac_num++]=num;
}
欧拉函数：
/*1.欧拉函数是积性函数,但不是完全积性函数,即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立.
2.对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.
φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).
3.除了N=2,φ(N)都是偶数.
4.设N为正整数,∑φ(d)=N (d|N). 求小于等于N的与N互质的数的和 ：ans=N*phi(N)/2;*/
/* 欧拉phi(x)函数等于不超过x且和x互素的整数个数。 */
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; const int MAXN=;
int phi[MAXN]; /* 单个欧拉函数值*/
int euler_phi(int n)
{
int m=sqrt(n+0.5),ans=n;
for(int i=;i<=m;i++)
{
if(n%i==) ans=ans/i*(i-);
while(n%i==)n/=i;
}
if(n>) ans=ans/n*(n-);
return ans;
}
/*欧拉函数 表*/
void phi_table(int n)
{
memset(phi,,sizeof(phi));
phi[]=;
for(int i=;i<=n;i++)
if(!phi[i])
for(int j=i;j<=n;j+=i)
{
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
埃氏筛法：O（nlog(logn)）
#include<iostream>
#include<cstring>
using namespace std; const int MAXN=;
int isprime[MAXN];
void getprime(int n)
{
memset(isprime,,sizeof(isprime));
isprime[]=isprime[]=;
for(int i=;i*i<n;i++)
if(isprime[i])
for(int j=i*i;j<=n;j+=i)
isprime[j]=;
}
欧拉筛法：
const int MAXN=;
int cnt=;
int prime[MAXN];
bool mark[MAXN];
void Prime(int x)
{
for(int i=;i<=x;i++)
{
if(!mark[i]) prime[++cnt]=i;
for(int j=;j<=cnt&&prime[j]*i<=x;j++)
{
mark[prime[j]*i]=;
if(i%prime[j]==) break;
}
}
}
后缀数组：
#include<iostream>
#include<cstring>
using namespace std; const int MAXN=+;
int WA[MAXN],WB[MAXN],WV[MAXN],WS[MAXN];
int Rank[MAXN],Height[MAXN]; int cmp(int *r , int a, int b, int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void DA(char *r , int *sa , int n, int m)
{
int i, j, p, *x = WA, *y = WB;
for(i = ; i < m; i++) WS[i] = ;
for(i = ; i < n; i++) WS[x[i] = r[i]]++;
for(i = ; i < m; i++) WS[i] += WS[i-];
for(i = n-; i >= ; i--) sa[--WS[x[i]]] = i; for(j = ,p = ; p < n ; j <<= ,m = p)
{
for(p = , i = n - j; i < n; i++) y[p++]=i;
for(i = ; i < n; i++)
if(sa[i] >= j)
y[p++] = sa[i] - j;
for(i = ; i < n; i++) WV[i] = x[y[i]];
for(i = ; i < m; i++) WS[i] = ;
for(i = ; i < n; i++) WS[WV[i]]++;
for(i = ; i < m; i++) WS[i] += WS[i-];
for(i = n-; i >= ; i--) sa[--WS[WV[i]]] = y[i];
for(swap(x,y),p = ,x[sa[]] = ,i = ; i < n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
} void calheight(char *r,int *sa,int n)
{
int i,j,k=;
for(i=;i<=n;i++)Rank[sa[i]]=i;
for(i=;i<n;Height[Rank[i++]]=k)
for(k?k--:,j=sa[Rank[i]-];r[i+k]==r[j+k];k++);
return;
} char str[MAXN];
int sa[MAXN]; int main()
{
cin>>str;
int n=strlen(str);
str[n]=;
DA(str,sa,n+,);
calheight(str,sa,n); return ;
}
最大子串：
int maxSubstr() {
int sum = , answer = -INF;
for (int i = ; i <= n; i++) {
sum += a[i];
answer = max(answer, sum);
sum = max(sum,);
}
return answer;
}
SG函数：（转自SimonS大佬征战亚洲赛时用的模板
#define MAX 1005
/* 计算从1-n范围内的SG值。
Array(存储可以走的步数，Array[0]表示可以有多少种走法)
Array[]需要从小到大排序 */
/*HDU1847博弈SG函数
1.可选步数为1-m的连续整数，直接取模即可，SG(x) = x % (m+1);
2.可选步数为任意步，SG(x) = x;
3.可选步数为一系列不连续的数，用GetSG(计算) */ int SG[MAX], hash[MAX];
void GetSG(int Array[], int n = MAX-)
{
memset(SG, , sizeof(SG));
for(int i = ; i <= n; ++i)
{
memset(hash, , sizeof(hash));
for(int j = ; j <= Array[]; ++j)
{
if(i < Array[j]) break;
hash[SG[i - Array[j]]] = ;
}
for(int j = ; j <= n; ++j)
if(!hash[j]){ SG[i] = j;break; }
}
}
先占坑，慢慢填
最新文章
- 一步一步学FRDM-KE02Z(一)：IAR调试平台搭建以及OpenSDA两种工作模式设置
- md语法
- 单例实现c++
- 团队作业 -- beta版本
- oracle中用SQL实现两个日期间的日期形成一个数据集
- nessus网页报错： Scans can not be saved without a policy. Please create a policy before proce
- 分析windows宿主机Ping不通linux虚拟机的其中一种情况
- delphi 菜单的项目是否可用
- 个人笔记--Servlet之过滤器实现权限拦截
- leetcode_question_57 Insert Interval
- java基础知识拾遗(二)
- ctrl+c 和 ctrl+z 的区别
- js中判断鼠标滚轮方向的方法
- AppBoxFuture(五): 分布式文件存储-Store Everything
- vue翻页器，包括上一页，下一页，跳转
- AndroidStudio连不上Android设备真机
- Get请求，Post请求乱码问题解决方案
- JAVA修饰符、关键字和继承（一）
- BSGS 算法
- Android adb logcat使用技巧