算法刷题

ACM笔记

初探ACM

GCD / LCM 求法


int gcd(int a,int b)
{
    return a % b == 0 ? b : gcd(a % b, b);
}

求LCD的方法： LCM = a * b / gcd(a, b)

快速幂

123^{11}\rightarrow(123)^{(1011)_2}\rightarrow(123)^{(8+2+1)}

幂次拆分，提升效率。

非递归形式实现：


xxxxxxxxxx
int qsm(int a, int n ) {
    int ans = 1;
    while(n) {
        if (n&1) ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

循环节

抽屉原理：总共n个抽屉，往里面随便放n+1个物体，则必然存在一个抽屉，它包含两个物体

一般看到 mod 就要想到用循环节做。

贪心算法

常见模型

问题1：FatMouse Trade 问题，解法：求性价比，降序排列，从性价比最高的开始买，钱不够时全部按比例折算购买。（hdu FatMouse's Trade）

问题2：最长事件序列问题，解法：最长的事件序列必然包含最早结束的事件序列。(hdu 今年暑假不Ac)

问题3：田忌赛马问题，策略：

A的慢马比B的慢马慢：让他和B的快马比赛，输的代价最小！
A的慢马比B的慢马快：让他和B的慢马比赛，赢的代价最小！
A的慢马和B的慢马一样快：
- A的慢马比B的快马慢：让他和B的快马比赛，输的代价最小！
- A的快马比B的快马快：让他和B的快马比赛，赢的代价最小！
- 其他情况：退出

来源： https://blog.csdn.net/liangbopirates/article/details/10035865

Havel Hakimi 定理

问题3：求图的连通性，给出连通性关系矩阵。(poj 1659)

Havel-Hakimi算法的依据：给出G，G是一个递减序列：
$G = (S_{1},S_{2},S_{3},...,S_{n})$
并且G是连通图，那么当且仅当递减序列G alt中的数是非负整数且G alt 也连通。G alt 序列是递减的，并且从第一个数 S1 开始的连续 S1 个数都减少 1：
$G_{alt} = (S_2-1,S_3-1....S_{2+S_1}-1,S_{2+S_2},S_{2+S_3},...,S_n)$

根据 Havel 定理，如果 G 连通，那么不断向前递推，必然能得到一个全部是 0 的序列。否则 G 不能连通。

解法：


x
#include <stdio.h>
typedef struct {
    int index;
    int weight;
}Point;
void selection_sort(Point* a, int start, int end) {/*排序，省略*/}
int main()
{
    int count;
    Point map[20];
    scanf("%d", &count);
    while(count--){
        int matrix[20][20]={0};
        int pcount;
        scanf("%d", &pcount);
        for(int i=0; i<pcount; i++) {
            map[i].index = i;
            scanf("%d", &map[i].weight);
        }
        int flag = 1;
        //--核心代码--
        for(int i=0; i<pcount; i++) {
            selection_sort(map, i, pcount);
            if(map[pcount-1].weight<0){
                //降序排列后，如果最后一个数都小于0，则图不能连通
                flag = 0;
                break;
            }
            if(map[i].weight == 0){
                //降序排列后，如果第一个数是0，则序列全为0，图连通
                break;
            } else {
                //如果不是结束的情况，则从第i个数开始，与向后i个数做点的连接（假设能连通）
                int j = i+1;
                while(map[i].weight > 0){
                    map[i].weight -= 1;
                    map[j].weight -= 1;
                    matrix[map[i].index][map[j].index] = 1;
                    matrix[map[j].index][map[i].index] = 1;
                    j++;
                }
            }
        }
        //--核心代码结束--
        if(flag == 1){
            printf("YES\n");
            for(int i=0; i<pcount; i++) {
                for(int j=0; j<pcount; j++) {
                    printf("%d ",matrix[i][j]);
                }
                printf("\n");
            }
        } else {
            printf("NO\n");
        }
        if(count!=0) {
            printf("\n");
        }
    }
}

快速排序

后来我发现用选择排序效率低导致超时，因此使用快速排序，成功Ac，快速排序如下：

直接用#include <algorithm> 的 sort() 最好。


xxxxxxxxxx
//降序的快速排序，参数左右都包含
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] <= x) // 从右向左找第一个小于x的数
                j--;
            if(i < j)
                s[i++] = s[j];
            while(i < j && s[i] > x) // 从左向右找第一个大于等于x的数
                i++;
            if(i < j)
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用
        quick_sort(s, i + 1, r);
    }
}

递推问题

简单递推

求Fibonacci数列的第n项：应使用递推 O (n) 而不是递归 O (2^n)

求n条直线能把平面分成多少部分：F(n) = F(n-1) + n

求n条折现能把平面分成多少部分：F(n) = F(n-1) + 4(n-1) + 1 （新增一条折线增加四个点，增加点数+1个段数）（HDUOJ 2045）

条件递推

Children's Queue 问题：女生必须两个以上连着排在一起，求n个人有几种可能的排法？

Lele的RPG难题：有RPG三种颜色，填在一行中，每一格颜色不同且首位颜色不同，求n个格子有几种可能的排法？

思路：以前面合法 + 前面不合法为分析基础，得出递推公式：

F(n) = F(n-1) + F(n-2)*2

思路解释：第n种情况由两种类型组成：

n-1情况正常，结尾加上唯一可能的字母；
n-1情况结尾和首字母相同时（即n-1不合法但n-2情况合法），最后加上两种可能的字母。

大兔生小兔问题：F(n) = F(n-1) + F(n-2)

骨牌拼接问题：有2x1，2x2两种骨牌，铺2xn的房间，如果最后一块放2x1，只有一种方法，而当最后一块放2x2则有两种方法（横着的两块2x1，或者一块2x2），所以F(n) = F(n-1) + 2 x F(n-2)

Catalan数

前几项Catalan数：1 2 5 14 42 132 429 ... ...
$Catalan(n) = \frac{C(2n, n)}{n+1}$

F(n) = F(0) * F(n-1) + F(1) * F(n-2) + F(2) * F(n-3) + ... + F(n-1) * F(0)

前几项Catalan数：1 2 5 14 42 132 429 ... ...

Catalan数模板题1： HDUOJ 1134 一圈上的点连线，线不相交（划分子问题）


xxxxxxxxxx
#include<stdio.h>
typedef long long ll;
int main(){
    ll c[100] ={0};
    c[0] = 1;
    int a;
    for(int i=1; i<100; i ++){
        for(int j=0; j<i; j++){
            c[i] += (c[j] * c[i-j-1]);
        }
    }
    while(scanf("%d", &a), a!=-1){
        printf("%lld\n", c[a]);
    }
}

注意：上面的代码不能 Ac，因为后面数字太大，即便是 long long都放不下。建议用 Java bigInteger类实现。

Catalan数模板题2： HDUOJ 2067 只允许下三角行走方格的最短路线数（也可用Dp）

其他题目

加括号的方式

N行N列网格路线（只允许下三角行走）

N个节点的二叉树的形态种类

HDOJ 1133 Buy the Ticket

相关练习 1023 1130 1131 1134 1133 1267 2067**

动态规划

DP问题适用的条件：

1.重叠子问题

2.无后效性

3.最佳子结构

DP经典1：数塔问题

问题描述：有一个数塔，每个节点有一个权值，怎么走路线长度最大？

分析：贪心算法会导致短视，应当采用DP，自顶向下分析，自底向上计算，从已知最优解推未知最优解。


xxxxxxxxxx
#include<stdio.h>
#include<math.h>
#define N 101
int main(){
    int count, height;
    int num[N][N];
    int dp[N][N];
    scanf("%d", &count);
    while(count--){
        //input
        scanf("%d", &height);
        for(int i=0; i<height; i++){
            for(int j=0; j<i+1; j++){
                scanf("%d", &num[i][j]);
            }
        }
        //dp init
        for(int i=0; i<height; i++){
            dp[height-1][i] = num[height-1][i];
        }
        //dp begin
        if(height == 1){
            printf("%d\n", num[0][0]);
            continue;
        }
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<=i; j++){
                int tmpmax;
                int lchild, rchild;
                lchild = dp[i+1][j], rchild = dp[i+1][j+1];
                tmpmax = lchild>rchild? lchild: rchild;
                dp[i][j] = tmpmax + num[i][j];
            }
        }
        printf("%d\n", dp[0][0]);
    }
    return 0;
}

HDUOJ 免费披萨 作为例题参考：

问题描述：有一个一维坐标0~10，Gameboy在坐标5，每单位时间只能左右移动一格或者不动。输入的数据是披萨出现的时间点和位置，问Gameboy最多能抢到多少披萨？

分析：输入的数据可以转换成 时间 + 位置的数塔，而GameBoy的移动策略则正好成为状态转移方程的一部分（数塔层之间的关联）。因此这个问题本质上就是DP模板。


xxxxxxxxxx
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 100
#define max(a,b) (((a) > (b)) ? (a) : (b))
int main(){
    int a;
    int data[N][11];
    int dp[N][11];
    while(scanf("%d", &a), a!=0){
        memset(data, 0, sizeof(data));
        memset(dp, 0, sizeof(dp));
        int maxtime=1;
        for(int i=0; i<a; i++){
            int time, pos;
            scanf("%d%d", &pos, &time);
            maxtime = max(time, maxtime);
            data[time][pos] ++;
        }
        for(int i=maxtime; i>=0; i--){
            for(int j=0; j<=10; j++){
                if(j==0){dp[i][j] = data[i][j] + max(dp[i+1][j],dp[i+1][j+1]);}
                else if(j<10){dp[i][j] = data[i][j] + max(dp[i+1][j], max(dp[i+1][j-1], dp[i+1][j+1]));}
                else {dp[i][j] = data[i][j] + max(dp[i+1][j-1],dp[i+1][j]);}
            }
        }
        printf("%d\n", dp[0][5]);
    }
    return 0;
}

DP经典2：最长递增子序列问题

问题描述：给定一个数组，求数组最长递增子序列的所有序列元素的和。

分析：求n个元素的最长子序列之和，可以化为求n-1个中最长子序列之和加上某个元素，并可以继续向小规模问题转化。求1个元素的最长子序列之和是最小的子问题。方法仍然是自顶向下分析，自底向上递推。


xxxxxxxxxx
#include<stdio.h>
#define N 1005
int main(){
    int count;
    int data[N];
    int dp[N];
    while(scanf("%d", &count), count != 0){
        for(int i=0; i<count; i++){
            scanf("%d", &data[i]);
            dp[i] = data[i];
        }
        //dp start
        int m = 0;
        for(int i=0; i<count; i++){
            for(int j=0; j<i; j++){
                if(data[j]<data[i] && dp[j]+data[i]>dp[i]){
                    dp[i] = dp[j] + data[i];
                }
            }
            if(dp[i]>m){
                m = dp[i];
            }
        }
        printf("%d\n", m);
    }
    return 0;
}

问题描述：给出老鼠速度和质量，要求找出最长序列，要求老鼠速度递增但质量递减，并给出老鼠ID。

分析：本质是最长递增子序列，但要求回溯路径。


xxxxxxxxxx
#include "stdio.h"
#include "algorithm"
#define N 1010
using namespace std;
typedef struct {
    int s,w,index;
} mice;
int comp(mice a, mice b){
    return a.w < b.w;
    return a.s > b.s;
}
int main(){
    mice mouse[N];
    int dp[N], pre[N], res[N];
    int a, b, ind=1;
    pre[0] = -1;
    while(scanf("%d%d", &a, &b) && a != 0 && b != 0){
        mouse[ind].w = a;
        mouse[ind].s = b;
        mouse[ind].index = ind;
        dp[ind] = 1;
        pre[ind] = 0;
        ind ++;
    }
    sort(mouse+1, mouse+1+ind, comp);
    //Dp progress
    int maxlen = 0;
    int maxend = 0;
    for(int i=1; i<ind+1; i++){
        for(int j=1; j<i; j++){
            if(mouse[j].w < mouse[i].w && mouse[j].s > mouse[i].s && dp[j] + 1 > dp[i]){
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
        if(dp[i] > maxlen){
            maxlen = dp[i];
            maxend = i;
        }
    }
    //Dp backtrace
    int t=maxend;
    int i=0;
    while(t != 0){
        res[i++] = t;
        t = pre[t];
    }
    printf("%d\n", i);
    while(i>0){
        i--;
        printf("%d\n", mouse[res[i]].index);
    }
    return 0;
}

DP经典3：最长公共字符串子序列问题

问题描述：给定两个字符串，求最长公共字符串子序列。

分析：状态转移方程如下：

\begin{equation} \left\{ \begin{array} \\ dp[i][j] = dp[i-1][j-1] + 1\space (if\space str1[i-1] = str2[j-1]) \\ dp[i][j] = Max(dp[i][j-1],dp[i-1][j])\space (if \space str1[i-1]\neq str2[j-1]) \\ \end{array} \right. \end{equation}


xxxxxxxxxx
#include<stdio.h>
#include<string.h>
#define N 1000
int max(int a, int b){
    return a > b? a: b;
}
int main(){
    char str1[N], str2[N];
    int a, b;
    while(a = scanf("%s", str1), b = scanf("%s", str2), a != EOF && b != EOF){
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        int dp[N][N];
        for(int i=0; i<=len1; i++){
            dp[0][i] = 0;
        }
        for(int i=0; i<=len2; i++){
            dp[i][0] = 0;
        }
        for(int i=1; i<=len1; i++){
            for(int j=1; j<=len2; j++){
                char c1 = str1[i-1];
                char c2 = str2[j-1];
                if(c1 == c2){
                    dp[i][j] = dp[i-1][j-1]+1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        printf("%d\n", dp[len1][len2]);
    }
    return 0;
}

背包问题

有一个容量为V的背包和若干个物品，在一定限制条件下，最多能放多少物品？

01背包

每种物品有且仅有一个，可以选择买或者不买。

状态转移方程：

F[i][v]=max\{F[i-1][v],\space F[i-1][v-c[i]]+w[i]\}

式中，F ( i , v ) 表示前 i 件物品装入容量为 v 的背包的价值。c( i ) 表示费用，w ( i ) 表示价值。

01样板代码：

注意要从 j 要从0开始，要考虑 0 背包大小。


xxxxxxxxxx
#include<stdio.h>
#include<string.h>
#define itemNumber 100
#define capacity 100
int main(){
    int dp[itemNumber][capacity];
    int cost[itemNumber], value[itemNumber];
    memset(dp, 0);
    //input
    //... ... ...
    //end input
    for(int i=1; i<=itemNumber; i++){
        for(int j=0; j<capacity; j++){
            if(j < cost[i]){
                //cant load !
                dp[i][j] = dp[i-1][j];
            } else {
                //can load, choose: 1.buy 2.dont buy
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i]] + value[i]);
            }
        }
    }
}

01背包优化代码，不容易理解但使用推荐这个：


xxxxxxxxxx
for(int i=1; i<=number; i++){
    for(int j=capacity; j>=volume[i]; j--){
        dp[j] = max(dp[j], dp[j-volume[i]]+value[i]);
    }
}

完全背包

一个物品可以取无数个，此外和01背包一样。


xxxxxxxxxx
#include<stdio.h>
#include<string.h>
#define itemNumber 100
#define capacity 100
int main(){
    int dp[itemNumber][capacity];
    int cost[itemNumber], value[itemNumber];
    memset(dp, 0);
    //input
    //... ... ...
    //end input
    for(int i=1; i<itemNumber; i++){
        for(int j=0; j<capacity; j++){
            for(int k=1; k*cost[i]<capacity ;k++){
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*cost[i]]+value[i]);
            }
        }
    }
}

优化代码，建议使用这个：


xxxxxxxxxx
for(int i=1; i<itemNumber; i++){
    for(int j=cost[i]; j<=capacity; j++){
        dp[j] = max(dp[j], dp[j-cost[i]]+value[i]);
    }
}

多重背包

一个物品可以买特定的数量。一种方法是逐个将堆叠的物品转化为独立的数量为1的物品，从而变为01背包；优化的方法是将堆叠物品用2的倍数分割。

以下样板代码，将情况分为多重背包 + 01背包。


xxxxxxxxxx
//dp
for(int i=0; i<type; i++){
    if(stock[i] * cost[i] >= capacity){
        //Comp DP, because 
        for(int j=cost[i]; j<=capacity; j++){
            dp[j] = max(dp[j], dp[j-cost[i]]+value[i]);
        }
    } else {
        //One Zero DP Transform
        int k = 1;
        int _num = stock[i];
        //item seperation
        while(k < _num){
            for(int j=capacity; j>=k*cost[i]; j--){
                dp[j] = max(dp[j], dp[j-k*cost[i]]+k*value[i]);
            }
            _num -= k;
            k *= 2;
        }
        //One Zero DP for rest items
        for(int j=money; j>=_num*cost[i]; j--){
            dp[j] = max(dp[j], dp[j-_num*cost[i]]+_num*value[i]);
        }
    }
}

二维背包

物品的限制有两种，如背包的承重，背包的容量两类限制。

状态转移方程变为三维：

F[i][v][u]=max\{F[i-1][v][u],\space F[i-1][v-c[i]][u-d[i]]+w[i]\}

搜索

BFS

BFS是基于队列的。下面的代码是二叉树的层次遍历：


xxxxxxxxxx
Status LevelFristTraverse(BTree T){
    if(T == null){return ERROR;}
    queue<int> Q;
    Q.push(T);
    while(queue.empty() == false){
        BTree tmp = Q.front();
        printf("%d", tmp.data);
        Q.pop();
        Q.push(T.lchild);
        Q.push(T.rchild);
    }
    return True;
}

二分查找

前提是单调性。


xxxxxxxxxx
//Recursive B-Search.
//assume arr[] is ascend.
int binarySearch(int tgt, int arr[], int left, int right){
    if(left >= right){return -1;}
    int pos = (left+right)/2
    if(arr[pos] - tgt == 0){
        return (left+right)/2;
    } else if (tgt < arr[pos]) {
        return binarySearch(tgt, arr, left, (left+right)/2);
    } else {
        return binarySearch(tgt, arr, (left+right)/2, right);
    }
}


xxxxxxxxxx
//B-Search using WHILE.
//assume arr[] is ascend.
int binarySearch2(int tgt, int arr[], int left, int right){
    while(right - left != 0){
        int pos = (right + left)/2;
        if(arr[pos] == tgt){return (left + right) / 2;}
        else if(arr[pos] > tgt){left = pos;}
        else {right = pos;}
    }
    return -1;
}

三分查找

前提是求导一次后符合单调性。

LeftThird = Left+(Right-Left)\div3

RightThird = Right-(Right-Left)\div3


xxxxxxxxxx
double solve(){
    // solve value of a function ...
}
double trinarySearch(int arr[], int left, int right, int eps){
    while(right-left > eps){
        int k = (right - left)/3;
        int lmid = l + k;
        int rmid = r - k;
        if(solve(lmid) > solve(rmid)){
            right = lmid;
        } else {
            left = rmid;
        }
    }
    return left;
}

DFS

深度优先搜索是基于栈的。

优化

筛选法求N以内所有素数

判断素数的优化：只需判断到 sqrt( N ) 即可。
筛选法：设置一个数组，值为1时认定为素数，值为0时认定为非素数。先全部置1，然后遍历判断，当前下标单元值为0时无需处理，如果是1，则将其倍数全部置为0，因为不论这个数是不是质数，他的倍数一定不是质数。
筛选法的优化版本：


xxxxxxxxxx
#define MAX_N 10000
int allPrime(int N){
    int a[MAX_N];
    for(int i=1; i<=N; i++){
        a[i] = 1;
    }
    for(int i=2; i<=sqrt(N); i++){
        if(a[i] == 1){
            //下面可以这样写，是因为j<i*i的部分一定在之前的循环中判断过了
            for(int j=i*i; j<=N; j+=i){
                a[j] = 0;
            }
        }
    }
    a[1] = 1;
    for(int i=1; i<=N; i++){
        if(a[i] == 1){
            printf("%d\n", i);
        }
    }
}

筛选法+统计求N以内素数的个数

首先通过筛选法进行预处理。
在筛选法进行过程中，统计直到当前 i 位置，总共出现的质数的个数。
处理完毕后，输入的数据直接从数组中寻找并输出即可。

并查集与最小生成树

\{1,2\}\{3,4,5\}\{6\}\{7,8,9,10\}

From	1	2	3	4	5	6	7	8	9	10
Master	1	1	3	3	3	6	7	7	7	7

每个元素都用其所属集合中最小的元素来标记。


xxxxxxxxxx
//查找元素x的最终所属集合
int findMaster(int bin[], int x){
    while(x != bin[x]){
        x = bin[x];
    }
    return x;
}
//查找元素x的最终所属集合的树深度压缩法，减少时间复杂度
int findMasterBetter(int bin[], int x){
    if(bin[x] == x){
        return x;
    } else {
        int tmp = findMasterBetter(bin[x]);
        bin[x] = tmp;
        return tmp;
    }
}
//合并x所在集合与y所在集合
int merge(int bin[], int from, int to){
    int fromMaster = findMaster(bin, from);
    int toMaster = findMaster(bin, to);
    if(fromMaster < toMaster){
        bin[toMaster] = fromMaster;
    } else {
        bin[fromMaster] = toMaster;
    }
}

Kruskal算法

利用并查集实现。

先把所有边从小到大排序，依次选择从小到大的边，如果边的两个顶点不在一个集合中，则合并两个集合并作记录，否则放弃选择。按上述步骤得到的即为最小生成树。

增加一个方法，判断是否属于同一个集合：


xxxxxxxxxx
int isSame(int a, int b){
    if (findMaster(a) == findMaster(b)){
        return 1;
    }
    return 0;
}

因为有count个点，所以最少需要c-1条路。每个循环中，先在邻接矩阵中找到不在同一集合中的最小距离的两个点，进行合并。


xxxxxxxxxx
//kruskal
int sum = 0;
for(int p=0; p<count-1; p++){
    int min = 200;
    int xpos = -1, ypos = -1;
    for(int i=1; i<=count; i++){
        for(int j=1; j<=count; j++){
            if(map[i][j] < min && !isSame(i, j)){
                min = map[i][j];
                xpos = i;
                ypos = j;
            }
        }
    }
    if(xpos != -1){
        sum += map[xpos][ypos];
        mergeSet(xpos, ypos);
    }
}

Prim算法

计算几何

给定两条有向线段 A-->B，B-->C：

问题1：求A-->B在B-->C的顺时针方向还是逆时针方向：

(A-->B) x (B-->C) = (A-->B)(B-->C) sin(theta) > 0 ==> sin(theta) > 0 ==>

Assert theta < rad90, then theta > 0 ==> (A-->B) clockwise (B-->C), vice versa, qed.

问题2：A-->B-->C，判断B点是左转还是右转：

(B-->C) x (B-->A) > 0 ==> (B-->C)(B-->A) sin(theta) > 0 ==> sin(theta) > 0 ==>

Assert theta < rad90, then theta > 0 ==> (B-->C) clockwise (B-->A) ==> B - LeftTurn qed.

问题3：判断A--B && B--C是否相交：

若不存在某个点位于某条线段的相交情况，则有：

if (A-->B) x (A-->C) * (A-->C) x (A-->D) < 0 && (C-->D) x (C-->A) * (C-->D) x (C-->B) < 0 then A--B intersect B--C

若存在某个点位于某条线段上的相交情况，则在上面情况的基础上，增加：

if (A-->B) x (A-->C)

问题4：多边形面积计算：

原理是三角形划分，用到了叉乘的带符号面积，且以原点为中心。

Area = \left|\sum_{i=0}^{i=n}\frac{(x_{i},y_{i})\times(x_{i+1},y_{i+1})}2\right|

问题5：凸包问题算法

Graham Scan Algorithm --- O(nlogn)
1. 选取一个y坐标最小的点（数学坐标系），将其与其他点连线，根据连线与极坐标正方向的夹角大小排序（两个向量叉乘，根据正负判断是顺时针方向还是逆时针方向）。
2. 将前两个点加入栈S，判断栈顶两个点连成的向量与栈顶点和第三个点连成的向量是否构成逆时针旋转，如果是，将第三个点压入栈，否则开始退栈。
3. 直到所有点遍历完毕，栈中的点元素就是凸包上的点。
Jarvis March Algorithm --- O(n^2)
选y值最小的点，开始从0rad顺时针旋转，每次第一个相遇的点作为新的点，加入容器后继续上述操作，直到与第一个点相遇，即得到凸包。

拓扑排序

找入度为0的点，找到后删除，继续查找，若不存在入度为0的点，并且已经找完所有点，则原有向无环图可以进行拓扑排序，反之，原图存在环，不能进行拓扑排序。


xxxxxxxxxx
int aa[505][505];  //邻接矩阵的形式表示图 
int in_degree[505]; //存放各个节点的入度 
int ans[505];  //存放排列的顺序 
int n,m;// 顶点个数,边的数目
//读入并存储图
void scanG()
{
    // 初始化
    memset(aa, 0, sizeof(g));
    memset(in_degree, 0, sizeof(in_degree));
    memset(ans, 0, sizeof(ans));
    int u, v;
    for(int i = 1; i <= m; i++) 
    {
        scanf("%d%d", &u, &v);
        aa[u][v] = 1;
        in_degree[v]++;  //计算入度
    }
}
void topsort()
{
    for(int i=1;i<=n;i++) {
        int k=1;
        while(in_degree[k]!=0) k++;
        ans[i]=k;
        in_degree[k]=-1;
        for(int j=1;j<=n;j++) {
            if(aa[k][j]) in_degree[j]--;
        }
    }
}

博弈

必胜点N点：上一个人将取胜的点。

必败点P点：下一个人将失败的点。

终结点必定是必败点；必胜点至少有一种方法可以进入必败点；必败点只能进入必胜点。

组合游戏解法：

所有终结位置标为P，所有一步操作能进入P的点的标为N点。
如果从某个点开始所有的一步操作只能进入N点，则将该点标为P点。

[例] 假设某取子游戏一次只能取1、3、4张牌，先取完的人获胜，则 N P 标注方式如下：

0	1	2	3	4	5	6	7	8	9	10	11
P	N	P	N	N	N	N	P	N	N	P	N

NimSum = x_!\oplus x_2 \oplus x_3

定理1：对于nim游戏的某个位置（x1 x2 x3）当且仅当各部分的 nim-sum = 0时，当前位置是必败点。

状态转移图

Sprague-Grundy函数

Sg(x) = min\{n>=0: n!=g(y)\space for\space y \space in \space F(x)\}

最短路 - Dijkstra

关键：更新最短路径的方式——两边之和小于第三边：

distance[j] = Math.min(distance[minpos] + map[minpos][j],distance[j])

例如上图，A --> C 的最短路径从100更新到50+10=60


xxxxxxxxxx
int dijkstra(int map[MAX][MAX], int len, int start, int end){
    int distance[MAX];
    int fin[MAX];
    int minpos;
    //fill distance
    for(int i=0; i<len; i++){
        distance[i] = map[start][i];
        fin[i] = 0;
    }
    fin[start] = 1;
    distance[start] = 0;
    //start dijkstra
    for(int i=0; i<len; i++){
        //find min
        int min=INF;
        minpos=0;
        for(int j=0; j<len; j++){
            if(!fin[j] && distance[j]<min){
                min = distance[minpos=j];
            }
        }
        if(min == INF) {break;}
        fin[minpos] = 1;
        //update
        for(int j=0; j<len; j++){
            if(!fin[j] && distance[j] > min + map[minpos][j]){
                distance[j] = min + map[minpos][j];
            }
        }
    }
    return (distance[end] == INF? -1: distance[end]);
}

二分图-匈牙利算法


xxxxxxxxxx
int edge[MAXN][MAXN];
int visited[MAXN];
int cx[MAXN], cy[MAXN];
int nx, ny;
int path(int u){
    //扫描Y点集
    for(int v=0; v<ny; v++){
        //如果能访问并且能连通
        if(edge[u][v] && !visited[v]){
            visited[v] = 1;
            if(cy[v] == -1 || path(cy[v])){
                cx[u] = v;
                cy[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int maxmatch(){
    int res = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    //扫描X点集
    for(int i=0; i<nx; i++){
        if(cx[i] == -1){
            memset(visited, 0, sizeof(visited));
            res += path(i);
        }
    }
    return res;
}

复习心得

做作业惩罚最少：用贪心算法，根据惩罚力度降序，最佳的策略是截止当天做完作业，所以从截止日期开始往前推，如果这一天有空，就安排在这天做作业（用一个数组管理），如果递推完了都没空，就放弃这作业。