cf1304D 题目给出n-1个‘<’‘>’约束，第i个位置的<意味着结果串中a[i]<a[i+1]，要求用1~n个数构造出两个串，分别拥有最小和最大的LIS。 思路：我们将升序1~n中连续>的区间执行reverse操作，执行完毕后的结果就是拥有最大LIS的满足约束的结果串。 证明：这种方法利用了全部的上升区间，及下降区间的一侧边界。我们知道对于连续下降区间，最多只能有一个元素被选入LIS，因此整体利用率达到最大。 最短的类似，首先降序n~1，然后不满足约束的reverse。 1 2 3 4 5 6 7 8 9 10 11...

lca即最近公共祖先，倍增法可以在O(n)的预处理后以每次logn的代价进行查询操作。 思路：预处理出fa[n][i]数组，表示第n号点的第（1<<i）个父亲，之后在寻找u、v的lca时，可以对二进制上的每一位进行向上跳跃。 例题：cf1304E 给出一棵树，有q个询问，格式（x，y，a，b，k）。意为对x，y点连边，求问此时从a到b有无一条长为k的路径，边可以重复走。 分析：边可以重复走说明如果一条路径长度小于k，且与k奇偶性相同，那么就可以重复走某些边来满足要求。添加bian（x，y）后，我们一共有三条可行的基础路径（a，b）、（a，x）+1+（y，b）、（a，...

二分用于在单调序列上以logn的时间确定某个值，三分则用在凸函数上，即先增后减序列，可以找它的极值。我们需要mid=(l+r)/2和midmid=(mid+r)/2这两个分界点，前者大则令r=midmid，否则令l=mid。 例题：cf939E 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include<bits/stdc++.h> using namespace...

​ 直接介绍复杂度最低（O(n+m)）的Hierholzer方法。它能帮我们找到一条欧拉回路。 ​ 欧拉回路指不重复经过所有边的一条回路，在有向图中，如果满足每个点入度=出度则存在欧拉回路。在无向图中，满足每个点度数为偶数则存在欧拉回路。它具有这样的性质，即从一个欧拉图中去除一个小欧拉图，剩下的仍是欧拉图，去除一个点及其所连边同样。由此产生了Hierholzer算法。 ​ 算法整体是一个dfs过程，总是尝试用一个回路来代替点u，于是我们对从u发出的边，只要是未标记的，就沿着它去搜下一个点，同时利用“引用”技巧将搜过确定下来的边删除，这样复杂度就不会退化。如果需要记录路径，选择用栈，在搜...

本质是记忆化搜索，一般求解区间[l,r]内有多少数字满足要求。我们可以拆分问题为solve(r)-solve(l-1)或solve(r)-solve(l)+judge(l)。注意到整个区间（例如[0,999]）在很多地方重复使用，所以对它记录。 例题：cf628D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 5...

题目 这道题不管从内容还是数据范围看起来都像是区间dp，可一时想不出来怎么构造出一个满足无后效性的区间状态，看了一眼题解才顿悟。 分两步走，第一步我们求出所有的dp[l][r]，表示[l,r]区间可以最终转化为的一个数，如果无法转化则为零，这一步的巧妙就在于包含了足够的信息来“总结”这个区间。第二步我们用前缀dp，设dp2[i]表示前i个元素最少合并为几个点，容易求出。 #include<bits/stdc++.h> using namespace std; const int maxn=501; int dp[maxn][maxn]; int n; int a[max...

普通treap： 参考https://www.csdn.net/gather_2a/MtTacg3sMTE0NS1ibG9n.html cf702f： 将所有人的钱数放入平衡树，每次按照可选衣服的价格将树一分为二，对于有购买能力的一棵树上的人钱数减去衣服价格，然后将剩余钱数小于c-1的再塞回第一棵树，最后将这两棵树合并。由于是非持久性结构，所有的人的节点编号不会变，会变的只有他们的亲子关系，所以可以直接用一个数组记录每个人的剩余钱数和已购买的衣服数量。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...

知识背景：首先明确强连通分量(strongly connected component)的概念，从任一顶点能够到达任一其他顶点的有向图 的顶点子集，而任意有向图均可以分解成若干不相交的scc。把每个scc视作一个顶点，可得到一个DAG。 实现算法：两次dfs，第一次 dfs 遍历将顶点后序(post order)记录下来vs（vector），这里需要注意的是，不管从哪个点dfs，由于是后序记录，故最终得到的记录是一样的，vs中的顶点（按下标）从前至后对应在DAG中为从尾到头。第二次dfs对于vs中的元素从尾到头进行，使用反向边，故每次dfs只能访问到同一个强连通分量。因而每次dfs时给所到...

寻找连通图的割点和桥用的也是tarjan算法，我们计算每个点不经过父亲能到达点的最小dfs序，如果是大于等于父亲的，则说明去掉父节点，该点即无法同上面连通，所以父节点是割点。桥类似，我们对于每个点标记它到父亲的那条边是否是桥。 cf1277E： 给出一个图求对于两点ab，有多少对xy使得从x到y的每一条路径都必经ab。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 4...

cf1131D 给出一个n*m关系表，有<>=三种关系，要求为这n+m个对象分配一个值，使得满足约束关系且最大值最小。 用差分约束，＞转化为>=x+1。=转化为>=且<=。如果y要比x至少大1，就建立边x指向y。对于这样一张图，满足所有要求其实就意味着能走的边都走（满足关系），不能满足的点就松弛（变大），类似求最长路。 bfs版spfa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...

这个算法真是研究了好久才明白……众多博客真的不是面向小白的 模板拿cf600E举例子，问题是给一棵有根树（rt==1），每个节点有一个颜色值，树的节点数和颜色值的范围都是1e5。对于每个节点我们定义其子树中数量最多的那个颜色值为主颜色（可以有多个并列），现要给出每个节点的主颜色的值的和。 首先想到暴力做法，直接去挨个点算他们的子树的答案，统计子树中每种颜色的数量并维护当前主颜色的和。这种算法显然是$O(n^2)$的。同时我们注意到一个细节，每个点的访问计算中所用到的cnt数组，应该是一个公用的全局数组，因为节点和颜色值的上限都是1e5，我们没法建立一个cnt[maxn][maxcolo...

这个算法真是研究了好久才明白……众多博客真的不是面向小白的 模板拿cf600E举例子，问题是给一棵有根树（rt==1），每个节点有一个颜色值，树的节点数和颜色值的范围都是1e5。对于每个节点我们定义其子树中数量最多的那个颜色值为主颜色（可以有多个并列），现要给出每个节点的主颜色的值的和。 首先想到暴力做法，直接去挨个点算他们的子树的答案，统计子树中每种颜色的数量并维护当前主颜色的和。这种算法显然是​的。同时我们注意到一个细节，每个点的访问计算中所用到的cnt数组，应该是一个公用的全局数组，因为节点和颜色值的上限都是1e5，我们没法建立一个cnt[maxn][maxcolor]的数组（如果能...

长链剖分可以把维护子树中只与深度有关的信息做到线性的时间复杂度。 例题cf1009f 给一棵树，定义每个点的dom值为，以该点为根的子树重中，节点数最多的那一层的层数，即那一层距离这个根节点有几条边，如果多层节点数相同，取最小的层数。例如单独叶节点的dom值是0，一条垂直的链的dom值也是0（每层数量都是1，取最前面的） 定义dp[i][j]为i树第j层的节点数，如果暴力遍历复杂度是n^2。我们用类似启发式合并的思想，对于长链（最深而非最重的链）处理后的结果直接拿给父节点用，然后再去依次解决轻节点，并把这些轻节点向父节点暴力合并。由于所有的轻链合并到深链上之后就“失效”了，之后再也...

cf704D 给棋盘上n个棋子染色，红黑两种，代价不同，有m个约束，要求某一行或某一列的红黑棋子数差不能超过某一数值。求最小代价的染色方案。 上下界网络流的思路就是分别减去最低流量，剩余的放在图中跑最大流，对于原有大于零下界的边就通过新建超级源点ss和汇点tt解决，即出点多出的连向汇点，入点缺少的从源点补充。合法要求：源点s发出的必须能跑满，否则原有的平衡条件就打破了，无可行流。 对于原本就有源的情况如下图，先确立一个可行流，取t-s边的流量，再把t-s边去掉，跑最大流加上即可。 先明确建图方案。对某一行列的属性做文章的时候考虑裂点，我们用所有的xy坐标作点，原有的（x，y）点变成...