遇到的问题

结构体LIS的问题

已解决

对于$n^2$可以解决的$LIS$问题，可以记录答案数组。

结构体LIS问题，利用二维偏序即可。

记忆化搜索实现起来更加方便，复杂度可能偏大，(递归)。

$O(nlogn+n)$实现LIS加上输出对应答案数组，注意LIS的d[]数组储存的是对应LIS长度的最小末尾元素，要输出答案数组还需要记录每个元素对应的LIS长度。

https://harris.blog.csdn.net/article/details/106444512

---

$dp$的常见范围 $n^2 (5\times 10^3,10^3)$

https://codeforces.ml/problemset/page/21?tags=dp,1500-2000

---

子串问题

$n(10^6)$

$O(n)$的递推问题，可能需要用到辅助数组，栈来递推。

如括号匹配的dp问题。

子串的dp问题，往往是类似区间合并，利用辅助数组来合并状态。

C. Looking for Order

状压的好题，跟顺序没有关系，所以可以直接剪枝跑。

---

给定一棵二叉搜索树的形态和序列，对应的填数是唯一确定的。

D. How many trees? 本题由上述知识可知，题意转化为求$n$个结点组成高度$\ge h$的二叉树形态个数。

树形dp问题：求不相交两个路径最大乘积。

枚举割边，分成两个连通块，然后dfs求两个连通块的直径乘积。

维护一个最大和次大子结点路径。

sum表示该子树的直径：分情况讨论，经过该结点，不过经过该节点。

int dp;
int dfs(int u,int fa){
    int sum=0,mx1=0,mx2=0;
    for(int v:e[u]){
        if(v==fa) continue;
        sum=max(sum,dfs(v,u));//不经过该结点.
        if(dp+1>mx1) mx2=mx1,mx1=dp+1;
        else if(dp+1>mx2) mx2=dp+1; 
    }
    sum=max(sum,mx1+mx2),dp=mx1;
    return sum;
} 

---

https://codeforces.ml/problemset/problem/14/E

多维dp问题。

波峰，波谷，需要维护最后两个变量来递推。

---

https://codeforces.ml/contest/16/problem/E

状压dp解决概率问题的好题。

貌似还有一个递推求二进制1的方法。

https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode/

复习一波：

int cnt=0;
while(x) x&=x-1,cnt++;
return cnt;

for(int i=1;i<=n;i++)    //O(n)
    bit[i]=b[i>>1]+(i&1);
for(int i=1;i<=n;i++)    //O(n)解决.
    bit[i]=bit[i&(i-1)]+1;

---

贪心+高精度

https://codeforces.ml/contest/18/problem/D

遇到贡献为2^x 的最值问题，考虑贪心。因为$2^x>2^{x-1}+2^{x-2}\dots 2^2+2^1+2^0$.

此题给贡献从大到小排序，然后贪心地选择，每选择一就将该区间标记。

然后高精度加法预处理 $2^x=2^{x-1}+2^{x-1}$。

---

https://codeforces.ml/contest/18/problem/E

dp的好题，按行dp，因为每行必须两种颜色，$dp[i][x][y]$

---

尺取，队列维护区间的答案。

https://ac.nowcoder.com/acm/contest/9983/B

---

//V>=n下的最小价值,一个限制条件+物品选不选的问题(01背包)

---

把一个序列切一刀分成两个和相等的子数组，枚举切的位置即可。

把一个序列切两刀分成三个和相等的子数组的方案数：因为子数组的和是可以确定的：$\dfrac{sum}{3}$，然后求可以预处理出前后缀和，后缀和等于$\dfrac{sum}{3}$的个数，枚举对于每个前缀和$=\dfrac{sum}{3}$的位置$i$，有多少个$suf[j]=\dfrac{sum}{3},j\ge i+2$。

---

==Hint：把一个序列分成两个不相交且非空的和相等子数组的方案数？==

一个暴力的想法，枚举所有区间，然后找另外相等区间与其相等的个数。

复杂度大约在：$O(n^4)$。。。。

---

求最大零矩阵周长。

暴力$O(nm)^3$，考虑类似二维前缀和$dp$优化。

确定起始点$(i,j)$，终点$(x,y)$成立的条件是$a[x][y]=0$且$dp[x-1][y]$成立且$dp[x][y-1]$成立。

时间复杂度：$O(nm)^2$。

---

https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/

滑动窗口经典题，维护定长区间的和，找到最值。

---

https://www.luogu.com.cn/problem/U148619?contestId=40088

断环成链，ST表预处理出区间最值，然后二分找到len. [x-len,x+len]，注意因为i!=j,所以是找[i-len,i-1],[i+1,i+len]的区间最值。

ST表习题待练习。

---

分块(暴力大法好！)待学。

https://www.luogu.com.cn/blog/cyffff/ti-xie-t2-diao-da-post

---

https://atcoder.jp/contests/abc191/tasks/abc191_c

这是什么神仙思维题？？

---

并查集重新建图跑dfs，注意标记边剪枝叶。

计算sz的时候可以不用再合并的时候算，而是类似桶把s[i]扫一遍。

---

spfa 可求最长路判正环，求最短路判负环。

---

背包问题，不能按$\dfrac{value}{weight}$的比值排序贪心做。

只有两种$weight$的背包问题，只需要分组，然后按$value$从大到小排序，然后第一组的个数，确定第二组的个数，取最值即可。

---

最小有向边生成树，很简单，除了根之外其他每个结点有且仅有一个父亲，所以存一下每个结点的最小边权父亲，然后除了根之外求和。

---

神奇构造题，用$1\times 2,2\times 1,2\times 2$填矩阵$n\times m$。

1.矩阵面积得为奇数。

2.$n,m$若存在奇数：

$n$为奇数，至少要$a-=\dfrac{m}{2}$

$m$为奇数，至少$b-=\dfrac{n}{2}$。

然后先假设都用$c$涂，一个小$tips$，$4$个$4$个的涂，且相连小正方形不同色，这样便于后面$a,b$来覆盖。

---

类似归并排序的模拟 比赛排名题，不是很熟。

每轮相邻的人比赛，最开始$(1,2)(3,4)(5,6)\dots$，胜者相邻后的继续比。

则第$k$轮可能比赛的人是$[(x-1)2^k+1,x2^k]$。

都减$1$,$[(x-1)2^k,x2^k-1]$

如何确定两个人是否能在第$k$轮遇到$:\dfrac{a-1}{2^k},\dfrac{b-1}{2^k}$。

---

构造题杀我。

傻逼树上博弈杀我。

思维杀我。

傻逼数学。

暴力dp是啥玩意，数据结构玩不动。

---

https://baike.baidu.com/item/%E7%93%B6%E9%A2%88%E7%94%9F%E6%88%90%E6%A0%91/2397900

最小生成树一定是瓶颈生成树。

BZOJ2429

最小支撑树？

---

https://blog.csdn.net/twtsa/article/details/8120269

极大化子矩形 论文。

悬线法 $O(nm)$

求最大不含障碍的子矩形。

枚举每个点向上扩展的最大高度(矩形的宽)$up[i][j]$，这个递推即可。

然后该悬线能向两边扩展的最大长度(矩形的长)。

递推$l[i][j]=l[i][j-1],r[i][j]=r[i][j+1]$。

$ans=max(ans,up[i][j]\times (r[i][j]-l[i][j]+1))$。

https://www.cnblogs.com/zhenglw/p/10102833.html

单调栈也可解决，还是需要预处理$up[i][j]$，

一行一行的维护，维护一个单调递增栈，当前待处理的矩形高如果$\le$栈顶就更新答案，然后弹出。

---

基环树，省选-黑题难度，待学。

https://www.luogu.com.cn/blog/ShadderLeave/ji-huan-shu-bi-ji

---

https://www.luogu.com.cn/blog/xww666/post-tuan-dui-t167649-qu-ti-xie

期望dp，树上高斯消元。

---

树形dp，好难写。

---

费用流问题

取反边的费用还有讲究吗？

---

神仙路径统计问题

https://www.luogu.com.cn/blog/wolfind/yi-suo-ge-lu-jing-ji-shuo-wen-ti

---

https://leetcode-cn.com/problems/longest-repeating-character-replacement/

滑窗

---

Hash需要练习

---

求两点斜率的更好写法。！

会不会有精度误差。

---

类似线段树的区间修改 lzay tag一样。

树也可以实现 lazy 标记子树操作加。

---

要初始化才能用。—-

---

leetcode 的isalpha 大小写都只会返回1024 醉了。

---

multiset 能logn 维护区间的最大，最小值。

两个单调队列能O(1) 维护最大，最小值。

---

单调队列能解决的问题：

区间最值。

dp优化：转移时：$dp[i]=max(dp[j])+a[i] ,j\in[l,r]$

---

区间平均值最大的区间长度 。

假了：肯定是最大那一个数，长度为1是最优的。

定区间 最大值最小。

​ 最小值最大。

---

常数优化：连续访问内存

$a[20][N]$优于$a[N][20]$。

---

网络流解决区间差分问题。

---

关于max,min 的宏定义问题

#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:bd

一般变量，宏定义较快，若参数为函数，因为宏定义在比较时会计算一次，返回计算值时也会计算一次，所以函数会执行两次，若为递归函数，则时间非常可怕。

所以一般还是用自带的比较函数。

---

lucas定理。

分形递归题。

---

二维矩形并，交，周长，面积，重合问题。

---

扩欧复杂度 ？ log(a+b)

---

EK EK EK EK 写板子

Dinic Dinic Dinic Dinic

---

用了IOS 之后不能用puts 了，不然会出错。

用若干变量初始化 vector

vector<int>v={a,b,c};

表达式排序

sort(a.begin(),a.end(),[](const auto &b,const auto &c){
            return b[0]==c[0]?b[1]>c[1]:b[0]<c[0];
        });

CDQ CDQ CDQ CDQ 分治

---

有向图求入度为0的点的个数，可以用floyd或者tarjan

并查集可用于无向图判环(因为并查集能维护双向关系)，但是不能判自环，因为初始赋值就是。

种类并查集 可以维护 敌对关系，朋友关系，单向关系。

---

两个栈实现 队列，一个栈为输入栈，另一个栈为输出栈，当输出栈不为空时 pop,peek操作直接取输出栈的栈顶，否则把输入栈的元素都丢入输出栈。

质因数分解求所有质因数复杂度最坏是$\sqrt{n}$的，如$n$为质数。

用埃氏筛可以$O(nloglogn)$预处理出每个数的所有质因数。

---

循环数组 仍然可以用单调栈求向左/右 第一个比它大/小的元素 ，只需要断环成链即可。

---

==期望dp==

一般是倒着。

==区间 MEX==

Treap(待复习)

https://www.luogu.com.cn/record/list?user=257206&language=&orderBy=0&page=6

---

除0错误 也会导致RE

---

组合数+周期+取模 等问题！

---

生成函数—–

$n$个结点的二叉树个数$C_n$卡特兰数，$n$个结点所有不同二叉树的叶子总数$nC_{n-1}$