在二位平面中，逆时针给定四边形的顶点，判断是否为凸四边形

bool check(point a,point b,point c,point d){
    double l1,l2,l3,l4;

    l1=(double)((b.x-a.x)*(d.y-a.y)-(d.x-a.x)*(b.y-a.y));
    l2=(double)((d.x-a.x)*(c.y-a.y)-(c.x-a.x)*(d.y-a.y));
    l3=(double)((d.x-b.x)*(c.y-b.y)-(c.x-b.x)*(d.y-b.y));
    l4=(double)((c.x-b.x)*(a.y-b.y)-(a.x-b.x)*(c.y-b.y));

    if(l1*l2*l3*l4>0) return true;
    return false;

}

时间复杂度的计算

当排序的元素值域很小时，使用桶排序最优

TCP协议是OSI七层模型中的应用层

求乘法逆元的新方法

infact[i]=(P-P/i)*infact[P%i]%p

二叉堆的插入为$log_n$,合并是$n$

有$N$个数的数组，排序比较的最少次数为$log2_n$

huffman编码不允许一个编码是另一个编码的前缀

博弈论中必胜状态和必败状态

1. 必胜状态，先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
2. 必败状态，先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

费马小定理

$a^p$ $\equiv$ $a$ ($mod$ $p$)

完全二叉树是一种特殊的二叉树

完全二叉树是一种特殊的二叉树，其中除最后一层外，每一层上

的节点数均达到最大值，且最后一层上的节点从左到右连续排列

，没有缺失的节点。

费马大定理

$x^n$ + $y^n$ = $z^n$ $($n$>2)$ 无解

组合计数公式

排列数

$A^a_{b}$= $\frac{n!}{(n-m)!}$ = ${a * (a-1) * (a-2) * … (a-b+1)}$

组合数

$C^a_{b}$= $\frac{n!}{m!(n-m)!}$

有$n$个节点的二叉树共有 $C^n_{2n}$ - $C^{n-1}_{2n}$ 种形态

有$n$个节点的无根树共有$n^{n-2}$种

有$n$个节点的树有$(n-1)!$个形态个数

运算优先级

1. 单目运算符 ! ~ ++ – + - & sizeof

2. 乘除法 / %

3. 加减法 + -

4. 移位运算符<< >>

5. 关系运算符<<= >>=

6. 相等运算符 == !=

7. 位运算符 & ^

8. 逻辑运算符 &&

9. 条件运算符 ?

10. 赋值运算符 = += -= = /= %=<<= >>= &= ^= |=

unsigned short 的范围是[0,$2^{16}$-1]

有$2n$个数中找数组的最大值和最小值,最少需要比较$3n-2$次

二分的另一个模板

while (l <= r)
{
    int mid = l + r  >> 1;
    if (check(mid)) l = mid+1;
    else r = mid - 1;
}

卡特兰数

计算公式：$\frac{C^n_{2n}}{n+1}$

应用：

1. 出栈次序
2. 括号匹配
3. 矩阵链乘
4. 二叉树生成问题 ($n$个节点构成的二叉树，共有多少种情形？$h$($n$))
5. 满二叉树个数 ($n+1$个叶子的满二叉树个数为多少？)
6. 圆划分问题 (在圆上选择$2n$个点，将这些点成对连接起来使得所得到的$n$条线段不相交的方法数？$h$($n$))
7. 排队方式

如何判断IP地址是否合法

AAA-BBB-CCC-DDD
1. $1<=AAA<=254$
2. $0<=BBB<=255$
3. $0<=CCC<=255$
4. $1<=DDD<=254$

判断IP为第几类

A类：1.0.0.1 ~ 126.255.255.254
B类：128.1.0.1 ~ 191.255.255.254
C类：192.0.0.1 ~ 223.255.255.254

127.0.0.1是本机的环回地址(用来访问自己的，不能设置为网关)

子网的地址为主机的IP地址和掩码的交集$(二进制位)$

洛谷P1052的代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define inf 0x3f3f3f3f

using namespace std;
const int N = 110;

int L;
int S,T,M;
int a[N];

//f[i]的含义：当前踩在第i块石子上，的最小步数 
int f[N]; 
//f中的数不超过100 
int f2[N];

int main()
{
    ios :: sync_with_stdio(false);

    cin >> L >> S >> T >> M;
    for(int i=1;i<=M;i++) cin >> a[i];
    a[M+1]=inf;

    memset(f,inf,sizeof f);
    memset(f2,inf,sizeof f2);

    f[0]=0;

    for(int i=1;i<=M+1;i++)
    {
        //当前石子坐标为a[i] 
        for(int j=S;j<=T;j++)
        {
            if(a[i]-j>=0)
            {
                int k=lower_bound(a,a+M,a[i]-j)-a;

                f[i]=min(f[k]+1,f[i]);
            }
        }
    }


    f2[M+1]=0;  

    for(int i=M;i>=1;i--)
    {
        for(int j=S;j<=T;j++)
        {
            if(a[i]+j<=L)
            {
                int k=upper_bound(a+1,a+M+1,a[i]+j)-a;
                f2[i]=min(f2[k]+1,f2[i]);
            }
        }
    }
    //取答案
    int res=inf;
    for(int i=1;i<=M;i++)
    {
        res=min(f[i]+f2[i]-1,res);
        if(f[i]==inf && f2[i]==inf) res=0;
    }

    cout << res << endl;    
    return 0;
}

算24点的程序

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 5;
int a[N];
bool st[N];
bool flag=false;
unordered_map<int,char> m{
    {1,'/'},{2,'+'},{3,'-'},{4,'*'}
};
struct Node{
    vector<int> v;
    vector<int> c;
    int val;
};
vector<int> v1;
vector<int> c1;
void dfs(int cnt,Node num)
{
    if(cnt == 4)
    {
        if(num.val == 24) 
        {
            v1 = num.v;c1 = num.c;
            flag = true;
            return;
        }
        return;
    }
    for(int i=1;i<=4;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            int  k = num.val;
            num.v.push_back(a[i]);
            if(k % a[i] == 0) num.val/=a[i],num.c.push_back(1),dfs(cnt+1,num),num.val*=a[i],num.c.pop_back();
            num.val+=a[i],num.c.push_back(2),dfs(cnt+1,num),num.val-=a[i],num.c.pop_back();
            if(k-a[i]>0) num.val-=a[i],num.c.push_back(3),dfs(cnt+1,num),num.val+=a[i],num.c.pop_back();
            num.val*=a[i],num.c.push_back(4),dfs(cnt+1,num),num.val/=a[i],num.c.pop_back();
            st[i]=false;
            num.v.pop_back();
        }
    }
}
int calc(int a,int b,int c)//a,b为数字，c为符号
{
    cout << a  << m[c] << b << "=" ;
    int ne=0;
    switch(c)
    {
        case 1: ne = a/b;break;
        case 2: ne = a+b;break;
        case 3: ne = a-b;break;
        case 4: ne = a*b;break;
    }
    cout << ne << endl;
    return ne;
}
int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=4;i++) cin >> a[i];
    for(int i=1;i<=4;i++)
    {
        memset(st,false,sizeof st);
        st[i]=true;
        Node num;
        num.val = a[i];num.v.push_back(a[i]);
        dfs(1,num);
        if(flag == true) 
        {
            if(v1[0] < v1[1]) swap(v1[0],v1[1]);
            int k=calc(v1[0],v1[1],c1[0]);
            for(int i=2;i<v1.size();i++){
                if(k < v1[i]) swap(v1[i],k);
                 k = calc(k,v1[i],c1[i-1]);
            }
            return 0;
        }
    }
    cout << "No answer!" << endl;
    return 0;
}