AcWing 算法基础笔记_综合

第一章基础算法

快速排序

#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int n;
int a[N];void quick_sort(int q[],int l, int r){
    if(l == r) return;int x = q[(l + r)/2] , i = l - 1 ,j = 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);
}int main(){
    scanf("%d", &n);for(int i = 0 ; i < n ; i ++ ){
    scanf("%d", &a[i]);}quick_sort(a,0,n-1);for(int i = 0 ; i < n ; i ++){
    printf("%d ", a[i]);}return 0;
}

测试数据量超过 10⁵ ，用 scanf

void quick_sort(int q[],int l, int r){
    if(l == r) return;int x = q[(l + r + 1)/2] , i = l - 1 ,j = 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,i - 1);quick_sort(q,i,r);
}

如果递归的边缘条件更改，取的 base 值要注意更换，以免越界。
base 值取为中值或者随机值实际上会更快。中值更稳定。

归并排序

#include<bits/stdc++.h>
using namespace std;const int N = 1e5;
int q[N],tmp[N];
int n;void sort(int q[] , int l , int r ){
    if(l == r) return;int mid = l + r >> 1;sort(q,l,mid);sort(q,mid + 1,r);int i = l , j = mid + 1 , k = 0;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 main(){
    scanf("%d",&n);for(int i = 0 ; i < n ; i ++ ) scanf("%d",&q[i]);sort(q,0,n-1);for(int i = 0 ; i < n ; i ++ ) printf("%d ",q[i]);return 0;
}

for(i = l , j = 0 ; i <= r ; i ++ , j ++ ) q[i] = tmp[j]; 每次迭代返回 q 的 l 到 r 。
和 sort 一样快

整数二分

int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;

int mid = l + r + 1 >> 1;
if(check(mid)) r = mid - 1;
else l = mid;

第三章搜索与图论

DFS stack 空间O(n)
BFS queue 空间O(aⁿ) 最短路

DFS + 回溯

全排列

#include<bits/stdc++.h>
using namespace std;const int N = 10;
int n;
int path[N];
bool st[N] = {
    0};void dfs(int u){
    if(u == n){
    for(int i = 0 ; i < n ; i ++ ){
    printf("%d ", path[i]);}cout << endl ;return;}for(int i = 1 ; i <= n ; i ++){
    if(!st[i]){
    path[u] = i ;st[i] = true ;dfs(u + 1);st[i] = false;}}
}int main(){
    cin >> n;dfs(0);return 0;
}

剪枝：提前判断

DFS + 剪枝 + 回溯

N皇后

在全排列的基础上改变 O( n*n! )

#include<bits/stdc++.h>
using namespace std;const int N = 20;
int n ;
char g[N][N];
bool col[N] , dg[N] , udg[N] ;void dfs(int u){
    if(u == n){
    for(int i = 0 ; i < n ; i ++) puts(g[i]);puts("");return ;}for(int i = 0 ;i < n ; i ++){
    if( !col[i] && !dg[u + i] && !udg[n - u + i]){
    g[u][i] = 'Q';col[i] = dg[u + i] = udg[n - u + i] = true;dfs(u + 1);col[i] = dg[u + i] = udg[n - u + i] = false;g[u][i] = '.';}}}
int main(){
    cin >> n;for(int i = 0 ; i < n ; i ++){
    for(int j = 0 ; j < n ; j ++){
    g[i][j] = '.';}}dfs(0);return 0;	
}

BFS

迷宫

#include<bits/stdc++.h>
using namespace std ;typedef pair<int,int> PII ;
const int N = 110 ;int n , m ;
int g[N][N] ;
int d[N][N] ;
PII q[N * N] ;int bfs(){
     //手动模拟queueint hh = 0 , tt = 0 ;q[0] = {
    0,0} ;memset(d, -1, sizeof d) ;d[0][0] = 0 ;int dx[4] = {
    -1 , 0 , 1 , 0} , dy[4] = {
    0, 1, 0, -1} ;while(hh <= tt){
    auto t = q[hh ++] ;for(int i = 0 ; i < 4 ; i ++){
    int x = t.first + dx[i] , y = t.second + dy[i] ;if(x >= 0 && x < n && y >= 0 && y < m && d[x][y] == -1){
    d[x][y] = d[t.first][t.second] + 1 ;q[ ++ tt] = {
    x,y} ;}}}return d[n - 1][m - 1] ;
}int main(){
    cin >> n >> m ;for(int i = 0 ; i < n ; i ++){
    for(int j = 0 ; j < m ; j ++){
    cin >> g[i][j] ;}}cout << bfs() << endl ;return 0 ;
}

邻接表

#include<bits/stdc++.h>
using namespace std ;const int N = 100010 , M = N * 2 ;int h[N], e[M], ne[M], idx ;void add(int a, int b){
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ; 
}int main(){
    idx = 0 ;memset(h , -1 , sizeof h) ;return 0 ;
}

dfs + 邻接

void dfs(int u){
    st[u] = true ;for(int i = h[u] ; i != -1 ; i = ne[i]){
    int j = e[i] ;if(!st[j]) dfs(j) ;}
}

树的重心

去除当前结点后，所有子树中最大的点数，为当前结点的值。
所有值中最小的值为树的重心。

#include<bits/stdc++.h>
using namespace std ;const int N = 100010 , M = N * 2 ;int n ;
int h[N], e[M], ne[M], idx ;
bool st[N] ;
int ans = N ;void add(int a, int b){
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ; 
}int dfs(int u){
     // 以 u 为根子数中点数的数量st[u] = true ;int sum = 1 , res = 0 ; // sum 初始值只有 u 1个// res 最大子数点的数量for(int i = h[u] ; i != -1 ; i = ne[i]){
    int j = e[i] ;if(!st[j]) {
    int s = dfs(j) ;res = max (res , s) ;sum += s ;}}res = max (res, n - sum) ;ans = min (ans, res) ;return sum ;
}int main(){
    cin >> n  ; memset(h , -1 , sizeof h) ;for(int i = 0 ; i < n - 1 ; i ++){
    int a , b ;cin >> a >> b ;add(a,b) ; add(b,a) ; // 无向图，a,b连通}dfs(1) ;cout << ans << endl ;return 0 ;
}

BFS + 邻接

树的层度

#include<bits/stdc++.h>
using namespace std ;const int N = 100010 ;
int n , m ; 
int h[N] , e[N] , ne[N] , idx ;
int d[N] , q[N] ;void add(int a , int b){
    e[idx] = b ; ne[idx] = h[a] ; h[a] = idx ++ ;  
}void bfs(){
    int hh = 0 , tt = 0 ;q[0] = 1 ;memset(d, -1, sizeof d) ;d[1] = 0 ;while(hh <= tt){
    int t = q[hh ++];for(int i = h[t] ; i != -1 ; i = ne[i]){
    int j = e[i] ;if(d[j] == -1){
    d[j] = d[t] + 1 ;q[++ tt] = j ;}}}return d[n] ;
}int main(){
    cin >> n >> m ;idx = 0 ;memset(h , -1 , sizeof h) ;for(int i = 0 ; i < m ; i ++){
    int a , b ; cin >> a >> b ;add(a,b) ;}cout << bfs() << endl ;return 0 ;
}

有向图拓扑序列

有向无环图一定存在拓扑序列

入度为0的结点入队，BFS

bool topsort()
{
    int hh = 0, tt = -1;// d[i] 存储点i的入度for (int i = 1; i <= n; i ++ )if (!d[i])q[ ++ tt] = i;while (hh <= tt){
    int t = q[hh ++ ];for (int i = h[t]; i != -1; i = ne[i]){
    int j = e[i];if (-- d[j] == 0)q[ ++ tt] = j;}}// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。return tt == n - 1;
}

最短路

在这里插入图片描述

稀疏图堆优化dij
稠密图朴素dij （ m 接近 n² ）

朴素dij 带权有向图

#include<bits/stdc++.h>
using namespace std ;const int N = 510 ;
int dist[N] ; // 当前该点的最短距离
bool st[N] = {
    0} ;
int g[N][N] ;
int n , m ;int dijkstra(){
    memset(dist, 0x3f, sizeof dist) ;dist[1] = 0 ;for(int i = 0 ; i < n ; i ++){
    int t = -1 ;for(int j = 1 ; j <= n ; j ++){
    //寻找未标记节点中距离出发点最近的节点if(!st[j] && (t == -1 || dist[j] < dist[t])){
    t = j ;}}st[t] = true ;for(int j = 1 ; j <= n ; j ++){
    dist[j] = min(dist[j], dist[t] + g[t][j]) ;} // 拿该点更新所有点 }if(dist[n] == 0x3f3f3f3f) return -1 ;else return dist[n] ;
}int main(){
    scanf("%d%d",&n,&m) ;memset(g, 0x3f, sizeof g) ;while(m --){
    int a, b, c ;scanf("%d%d%d",&a,&b,&c) ;g[a][b] = min(c, g[a][b]) ;}int t = dijkstra() ;printf("%d\n",t) ;return 0 ;
}

memset(0x3f)即初始值为0x3f3f3f3f,而注意到dist[j] = min(dist[j], dist[t] + g[t][j])这里的dist+g 刚好是 2 * 0x3f3f3f3f <= INT_MAX，如有三个相加，则会超INT_MAX，最大值需要变小，或者取ll。

AcWing 算法基础笔记

第一章 基础算法

第三章 搜索与图论