演算法模板：堆，最小生成樹(Prim,Kruskal)，快速冪-有解無憂

堆

堆一般以二叉堆的形式存在，也可以說是一個“優先佇列”，堆中資料以一定順序存放，比如小根堆(根節點小于子節點)
堆涉及到的基本操作：
- 上浮：新插入元素時在底，上浮到相應的位置
- 下沉：洗掉元素時，洗掉最小元素(根節點)，以堆底元素作為臨時的root,然后進行下沉調整堆

基本模板：

堆結構：一個陣列，heap[0]來存盤堆中元素個數，heap[heap[0]]是堆底元素，heap[heap[0]/2]是堆底元素的父節點

int heap[MAXN];

上浮：

void swim(int x) {
    int p = x >> 1;
    while(p>0 && heap[x]<heap[p]) {
        swap(heap[x],heap[p]);//子節點<父節點，則互換位置
        x = p;
        p = x >> 1;  //繼續上浮
    }
}

下沉：

void sink(int x) {
    int c = x << 1;
    while(c <= heap[0]) {
        if(c+1<=heap[0] && heap[c+1]<heap[c]) c++;
        if(heap[c] < heap[x]) {
            swap(heap[c],heap[x]);
            x = c;
            c = x << 1;
        } else {
            break;
        }
    }
}

插入：

void insert(int x) {
   	heap[0] ++;
    heap[heap[0]] = x;
    swim(heap[0]);
}

洗掉

void pop() {
    swap(heap[1],heap[heap[0]--]);
    sink(1);
}

最小生成樹

Prim && Kruskal :
- Prim: 以連接節點的臨邊找最小值
- Kruskal: 直接排序邊
- 稠密圖用Prim,稀疏圖用Kruskal
Prim :
- 1、從任意一個頂點開始構造生成樹，假設就從1號頂點吧，首先將頂點1加入生成樹中，用一個一維陣列vis來標記哪些頂點已經加入了生成樹，
  2、用陣列dis記錄生成樹到各個頂點的距離，最初生成樹中之后1號頂點，有直連邊時，陣列dis中存盤的就是1號頂點到該頂點的邊的權值，沒有直連邊的時候就是無窮大，即初始化dis陣列，
  3、從陣列dis中選出離生成樹最近的頂點（假設這個頂點為j）加入到生成樹中（即在陣列dis中找到最小值），再以j為中間點，更新生成樹到每一個非樹頂點的距離（就是松弛啦），即如果dis[k]>e[j][k]則更新dis[k]=e[j][k]，
  4、重復第三步，直到生成樹中有n個頂點為止，
- 以鏈式前向星存圖
```
struct Edge
{
    int val,prev,next;
}e[MAXN];
```
- 添加一條邊
```
void add(int p,int n,int v) {
    e[++k].prev = first[p];
    first[p] = k;
    e[k].next = n;
    e[k].val = v;
}
```
- ```
  priority_queue<pair<int,int> > q;
  
  int prim() {
      q.push(make_pair(0,1));
      while(!q.empty() && cnt<n) {
          int now = q.top().second;
          int v = q.top().first;
          q.pop();
          if(vis[now]) continue;
          vis[now] = 1;
          ans += v;
          cnt ++;
          for(int i=first[now]; i; i=e[i].prev) {
              if(!vis[e[i].next]) 
                  q.push(make_pair(-e[i].val,e[i].next));  //優先佇列默認大根堆
          }
      }
      return -ans;
  }
```

Kruskal:

主要思路：kruskal就是基于并查集的貪心演算法
1. 輸入邊
2. 結構體排序，以小到大排邊
3. 建并查集，聯通樹
存盤邊

struct edge {
    int val, prev, next;
} e[MAXN];

bool cmp(const edge& a, const edge& b) { return a.val < b.val; }

并查集

int pre[MAXN];
int find(int x) {
    while (x != pre[x]) {
        x = pre[x] = pre[pre[x]];
    }
    return x;
}

kruskal:

void kruskal() {
    for (int i = 1; i <= m; i++) {
        int fx = find(e[i].prev);
        int fy = find(e[i].next);
        if (fx != fy) {
            ans += e[i].val;
            cnt++;
            pre[fx] = fy;
        } else {
            continue;
        }
        if (cnt == n-1) break; 
    }
}

快速冪 || 快速冪取余

每一步把指數折半，而相應的底數平方，從而減少回圈次數

eg. 3^10 == (33)^5 == 9 * (99)^2 == 9 * 81 * 81 * 81

取余公式：

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p

模板：

LL quickPower(LL base,LL power,LL modk) {
    LL ans = 1;
    while(power > 0) {
        if(power & 1) { //奇數次乘入結果
            ans = ans * base % modk;
        }
        power >>= 1; //power折半
        base = (base * base) % modk; //底數平方
    }
    return ans%modk;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/106368.html

標籤：其他

上一篇：剛入行的軟體測驗工程師，如何自學軟體測驗？

下一篇：應屆大學生，在醫藥零售公司做MOM開發人員，請問這個職業怎么發展的？本人對技術感興趣想往技術方向走是否要轉崗啊？