刘浩伟ACwing算法板子
快速排序算法模板
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
归并排序算法模板 ——
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
整数二分算法模板
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点数二分算法
bool check(double x)
double bsearch_3(double l, double r)
{
const double eps = 1e-6;
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
DFS经典题型(全排列)
#include<stdio.h>
int n,path[100];
int s[100]={0};
void dfs(int t)
{
if(t==n)
{
for(int i=0;i<n;i++)
{
printf("%d ",path[i]);
}
printf("\n");
return;
}
for(int i=1;i<=n;i++)
{
if(s[i]==0)
{
s[i]=1;
path[t]=i;
dfs(t+1);
s[i]=0;
}
}
}
int main()
{
scanf("%d",&n);
dfs(0);
return 0;
}
BFS经典题型(走迷宫)
#include<stdio.h>
#include<string.h>
const int N=110;
int g[N][N];
int d[N][N];
struct elem
{
int x;
int y;
};
struct elem q[N*N];
int bfs(int n,int m)
{
memset(d,-1,sizeof d);
int hh=0,tt=0;
d[0][0]=0;
q[hh].x=0,q[hh].y=0;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
while(hh<=tt)
{
struct elem j=q[hh++];
for(int i=0;i<4;i++)
{
int x=j.x+dx[i];
int y=j.y+dy[i];
if(x>=0&&y>=0&&x<n&&y<m&&g[x][y]==0&&d[x][y]==-1)
{
d[x][y]=d[j.x][j.y]+1;
q[++tt].x=x;
q[tt].y=y;;
}
}
}
return d[n-1][m-1];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&g[i][j]);
}
}
printf("%d",bfs(n,m));
return 0;
}
试除法判定质数
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
试除法分解质因数
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
朴素筛法求素数
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
