模板整理
1.并查集
int fa[maxn];
int n;
void init()
{
for(int i=0;i<n;i++)
{
fa[i]=i;
}
}
int findd(int i)
{
if(fa[i]==i)
{
return i;
}
else return fa[i]=findd(fa[i]);
}
int unione(int x,int y)
{
int fx=findd(x),fy=findd(y);
if(fx!=fy)
{
fa[fx]=fy;
}
}
2.Dijkstra算法（n^2复杂度）
int maps[1005][1005]={0};
int vis[1005];
int dist[1005];
void fun()
{
int i,j;
for(i=0;i<1005;i++)
{
for(j=0;j<1005;j++)
{
if(i==j)
{
maps[i][j]=0;
}
}
}
}
void dijstra(int n)
{
memset(vis,0,sizeof(vis));
fill(dist,dist+1005,100000);
dist[1]=0;
while(1)
{
int v=-1,i;
for(i=1;i<=n;i++)
{
if(!vis[i]&&(dist[i]<dist[v]||v==-1))
{
v=i;
}
}
if(v==-1)
{
break;
}
vis[v]=1;
for(i=1;i<=n;i++)
{
if(maps[i][v]!=-1)
{
dist[i]=min(dist[i],dist[v]+maps[i][v]);
}
}
}
}
3.Floyd算法
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
//if(dp[i][k]<inf&&dp[k][j]<inf)
//{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
//}
}
}
}
4.扩展欧几里得
int ex_gcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int ans=ex_gcd(b,a%b,x,y);//获得x2,y2;
int temp=x;//存储x2
x=y;//x1=y2
y=temp-(a/b)*x;//y1=x2-(a/b)*y2
return ans;
}
5.KMP
void getnex()
{
int i = 0, j = -1;
nex[0] = -1;
while(i < n)
{
if(j == -1 || s[i] == s[j])
{
i++, j++;
nex[i] = j;
}
else j = nex[j];
}
}
void getnt()
{
int i = 0, j = -1;
nex[0] = -1;
while(s[i])
{
if(j == -1 || s[i] == s[j])
{
i++, j++;
nex[i] = j;
}
else j = nex[j];
}
l1=i;
}
bool kmp(int l1,int l2)
{
int i=0;
int j=0;
getnex(l2);
for(i=0;i<l1;i++)
{
while(j&&s[i]!=t[j])
{
j=nex[j];
}
if(s[i]==t[j]) j++;
if(j==l2) return true;
}
return false;
}
int kmp(char t[],char p[])
{
int n=strlen(t+1),m=strlen(p+1);
prefix(p);
int sum=0;
for(int i=1,q=0;i<=n;i++)
{
while(q>0 && p[q+1]!=t[i])
q=nex[q];
if(p[q+1]==t[i])
q++;
if(q==m)
{
sum++;
q=nex[q];
}
}
return sum;
}
6.欧拉筛
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n;
int prime[10000005];
bool vis[10000005];
void primejudge(int n)
{
memset(vis,false,sizeof(vis));
int cnt=0;
vis[1]=true;
int i,j;
for(i=2;i<=n;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
}
for(j=0;j<cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]==0)
{
break;
}
}
}
}
int main()
{ int m;
scanf("%d%d",&n,&m);
primejudge(n);
while(m--)
{ int x;
scanf("%d",&x);
if(!vis[x])
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
return 0;
}
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n;
int prime[10000005];
bool vis[10000005];
void primejudge(int n)
{
memset(vis,false,sizeof(vis));
int cnt=0;
vis[1]=true;
int i,j;
for(i=2;i<=n;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
}
for(j=0;j<cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]==0)
{
break;
}
}
}
}
int main()
{ int m;
scanf("%d%d",&n,&m);
primejudge(n);
while(m--)
{ int x;
scanf("%d",&x);
if(!vis[x])
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
return 0;
}
7.SG博弈
//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
2 //SG[]:0~n的SG函数值
3 //S[]:为x后继状态的集合
4 int f[N],SG[MAXN],S[MAXN];
5 void getSG(int n){
6 int i,j;
7 memset(SG,0,sizeof(SG));
8 //因为SG[0]始终等于0，所以i从1开始
9 for(i = 1; i <= n; i++){
10 //每一次都要将上一状态 的 后继集合 重置
11 memset(S,0,sizeof(S));
12 for(j = 0; f[j] <= i && j <= N; j++)
13 S[SG[i-f[j]]] = 1; //将后继状态的SG函数值进行标记
14 for(j = 0;; j++) if(!S[j]){ //查询当前后继状态SG值中最小的非零值
15 SG[i] = j;
16 break;
17 }
18 }
19 }
欧拉函数打表
int p[maxn];
void phi()
{
for(int i=2;i<maxn;i++)
p[i]=0;
p[1]=1;
for(int i=2;i<maxn;i++)
{
if(!p[i])
for(int j=i;j<=maxn;j+=i)
{
if(!p[j])p[j]=j;
p[j]=p[j]/i*(i-1);
}
}
}
逆元求组合数
#include <iostream>
#include <bits/stdc++.h>
#define maxn 1000005
typedef long long ll;
using namespace std;
const ll mod=1e9+7;
ll fac[maxn],inv[maxn];
ll pow_mod(ll a,ll n)
{
ll ret =1;
while(n)
{
if(n&1) ret=ret*a%mod;
a=a*a%mod;
n>>=1;
}
return ret;
}
void init()
{
fac[0]=1;
for(int i=1;i<maxn;i++)
{
fac[i]=fac[i-1]*i%mod;
}
}
ll C(ll x, ll y)
{
return fac[x]*pow_mod(fac[y]*fac[x-y]%mod,mod-2)%mod;
}