日期问题：

1.算具体天数问题:从一年一月一日（公元第一天）到当前日期经过的天数即可
题目：日期差值
2.判断日期是否合法问题：暴力枚举所有可能的情况，模板check一下判断是否合法即可
题目：日期问题,回文日期
附一个枚举回文数的方法:

for (int i = 0; i < 10000; i ++ )
    {
        int x = i, r = i;
        for (int j = 0; j < 4; j ++ ) r = r * 10 + x % 10, x /= 10;
        if (r >= date1 && r <= date2 && check(r)) res ++ ;
    }

3.打表+check:蓝桥杯填空

Flood fill

一般用vector存下来:
例如星空之夜，可以在dfs完使用vector找到的联通块，再下次dfs前清空即可。
奶牛选美:两个联通块，所以要开两个vector，然后dfs完再用.

哈希

四平方和：模拟哈希表的方式，数组代替（因为数据范围允许），总和为键，乘数为值，初始化哈希表为-1，直接查找键发现不为-1就是存在（相当于hash.count()）实现快速查找$O(1)$


例如：扫雷这题最多有1e10条边，建图存的话会爆空间，是不可行的，所以要把比边关系信息用hash表存起来

二分

1e5 ~ 1e6,答案具有二段性，最小值/最大值，$O(nlogn)$

注意点：

二分范围：冶炼金属,此题把左边界l设置为0会出现被除数mid为0的情况，出现float指针异常，所以要确定好边界。
能否二分到答案：数的范围,好像还有一个周赛题;
浮点数二分：

双指针

一般用于优化时间复杂度

十分灵活的用法：

可以在降一维优化：统计子矩阵
可以while + if:判断子序列
也可以if + while:日志统计
可以有前缀和的作用:子串简写

前缀和

差分

为一段连续区间添加同一个数
二维差分，记得要多开一个二维数组，然后前缀和逆着做：差分矩阵
差分 + 贪心：重新排序;

区间问题

区间合并

贪心

区间dp

线性dp

二分 前缀和

单调队列

单调栈：

找出左/右边第一个比当前元素大/小的元素

滑动窗口：

动态维护一段区间内的最大/小值

并查集

数据范围可以1e6,维护集合关系
模板：并查集，注意find和father[]的区别

递归

表达式问题：正则问题;
全排列 + 数位：带分数;
分治

约数

if(i!=x/i) res.push_back(x/i);//不能写i，不然重复放入了

约数之和，约数个数

一般要存指数和底数，用hash表存

快速幂

时间复杂度1e18
题目：转圈游戏

快速幂求逆元：

要满足mod为质数
及时取模

exgcd

扩展欧几里得定理
线性同余方程

博弈论

定理1：

先手0局面必败
先手非0局面必胜

定理2：

最坏情况选最优

欧拉函数

分解质因数求欧拉函数

for(int i = 2;i <= x / i;i++)
        {
            if(x % i == 0) 
            {
                res = res / i * (i - 1);
                while(x % i == 0) x /= i;
            }
        }
        if(x > 1) res = res / x * (x - 1);

线性求欧拉函数 $O(N)$

LL get_eulers(int n)
{
    eulers[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!st[i]) 
        {   
            primes[ cnt++ ] = i;
            eulers[i] = i - 1;
        }
        for(int j = 0;primes[j] <= n / i;j++)
        {
            int t = primes[j] * i;
            st[t] = true;
            if(i % primes[j] == 0)
            {
                eulers[t] = primes[j] * eulers[i];
                break;
            }
            eulers[t] = (primes[j] - 1) * eulers[i];
        }
    }

基本数论知识：

互质的数的最大公约数为1

基本算数原理：

裴蜀定理：ax + by = gcd(a,b)

进制转换

十六进制转十进制：进制

最短路（不应该放在这，之后整理）

只会默写模板朴素dijkstra

状态压缩DP

一般数据范围<30,不是状压dp，就是dfs + 剪枝
只会最短Hamilton路径模型
题目：毕业旅行问题

组合数

当a,b比较小时，采用递推，背包模型：组合数1
反之：预处理 + 快速幂求逆元:组合数2
贴个板子:

//预处理
void init()
{
    fact[0] = 1,infact[0] = 1;
    for(int i = 1;i < N;i++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i,mod - 2,mod) % mod;
    }
}

搜索（最重要的一集，我贴各种搜索方式，记就完了）

先来奶酪这道题：

有时候不得不感叹，有人的代码就是精简，目的性极强,例如这个判断能否相连：

bool calc(int x,int y,int z)
{
    return pow(x,2) + pow(y,2) + pow(z,2) <= 4 * (LL)r * r;
}

开始想着排个序，优化下搜索顺序，其实数据范围正常的dfs不用考虑这些，而这道题本质就是经典深度优先遍历，所以不用恢复现场

bool dfs(int u)
{
    if(circle[u].z + r >= h) return true;

    st[u] = true;

    for(int i = 1;i <= n;i++)
    {
        int x = circle[u].x - circle[i].x, y = circle[u].y - circle[i].y,z = circle[u].z - circle[i].z;
        if(!st[i] && calc(x,y,z))
            if(dfs(i)) return true;
    }

    return false;
}

对先前做这道题的分析：

bool dfs(int last,int x1,int y1,int z1)//当前位于哪个位置
{
    if(last >= h) return true;

    for(int i = 0;i < n;i++)
    {
        int x2 = circle[i].x,y2 = circle[i].y,z2 = circle[i].z;
        if(!st[i] && calc(x1,y1,z1,x2,y2,z2) >= r)
        {
            st[i] = true;
            if(dfs(last + circle[i].z + r,x2,y2,z2)) return true;
            st[i] = false;
        }
    }
    return false;
}

可知四个参数完全是多此一举，以上的四个参数分别代表当前的高度，上一个点的x,y,z坐标，而这些完全传入一个结构体的下标就行，判断条件改成(circle[u].z + r >= h)与原来等价。

优化一下变成

bool dfs(int last,int u)//当前位于哪个位置
{
    if(last >= h) return true;

    st[u] = true;
    for(int i = 0;i < n;i++)
    {
        int x2 = circle[i].x,y2 = circle[i].y,z2 = circle[i].z;
        if(!st[i] && calc(x1,y1,z1,x2,y2,z2) >= r)
            if(dfs(last + circle[i].z + r,i)) return true;
            st[i] = false;
    }
    return false;
}

这时候发现长得跟单词接龙这题代码很像，其实完全不一样
单词接龙还得恢复现场，知道原因了吗，由题目性质决定（附代码）：

void dfs(string loong,int last)
{
    ans = max((int)loong.size(),ans);

    used[last]++;

    for(int i = 0;i < n;i++)
        if(g[last][i] && used[i] < 2)
            dfs(loong + words[i].substr(g[last][i]),i);

    used[last]--;
}

这便是多刷用dfs做题，多练暴力的原因，没个暴力步骤，参数都是不一样的。

小猫爬山

void dfs(int u,int k)
{
    //最优性剪枝
    if(u >= ans) return;
    if(k == n)
    {
        ans = u;
        return;
    }

    for(int i = 0;i < u;i++)
    {
        //可行性剪枝
        if(sum[i] + w[k] <= m)
        {
            sum[i] += w[k];
            dfs(u,k + 1);
            sum[i] -= w[k];//恢复现场
        }
    }

    sum[u] = w[k];//新开一辆车
    dfs(u + 1,k + 1);
    sum[u] = 0;//恢复现场
}

飞机降落:

bool dfs(int u, int last)
{
    if (u == n) return true;

    for (int i = 0; i < n; i ++ )
    {
        int t = p[i].t, d = p[i].d, l = p[i].l;
        if (!st[i] && t + d >= last)
        {
            st[i] = true;
            if (dfs(u + 1, max(last, t) + l)) return true;
            st[i] = false;
        }
    }
    return false;
}

分成互质组;
马走日:
机器分配:

//给第son家子公司分配时，剩下sum个设备，分配前已经获得利益为val
void dfs(int son, int sum, int val) {
    if (sum == 0) {
        if (ans < val) {
            ans = val;
            for (int i = 1; i <= n; ++ i) res[i] = temp[i];
        }
    }
    else if (son > n) return;
    else {
        for (int i = 0; i <= sum; ++ i) {
            temp[son] = i;
            dfs(son + 1, sum - i, val + nums[son][i]);
            temp[son] = 0;  //恢复现场
        }
    }
}

dfs(1, m, 0);。

背包模型

目前遇到的题，和已知的理解

bool
方案数
价值
不高于，恰好：
有依赖背包：有点像树形dp，我可以称其就是树上背包？这个有点难。
二维费用：就是多一层状态，然后多一层枚举，跟体积一样倒着枚举就行。
完全背包，注意定义的数据范围即可

线性DP

lis 记得分清状态表示，最后要再枚举一遍
lds：最长下降子序列,倒着求即可
lcs 状态计算划分为四个，对症下药，很好理解
lics：一个交给a对付，一个给b对付
乌龟棋比较特别

数字三角形

注意求最大值要初始化0x3f
方格取数两个人一起走，不太会刚学。

就到这了吧。。已经过载了，感觉还得多写模板。

接下来多写暴力，多背模板，多学点填空题，最后看看我的动态，剩下交给天意。