欢迎光临!

闭合图 我们给出闭合图的定义:对于有向图中的点，其相邻的节点全部属于这个有向图，那么这个图就被称为闭合图。 也就是说这个图的终点一定是出度为0的。 最大权闭合子图 就是对于一个有向图，每个点有一个权值，权值属于实数，现在考虑选择一个闭合子图使得这个子图中的点的权值和最大。 我们尚且思考一下，不难发现我们选择一个点，那么这个点的后继节点我们全部需要选择，即它可以到达的点我们全部需要选择进来。 这样不免会选择到权值为负的边，那么我们怎么操作？ 我们可以考虑网络流的做法。先考虑建立超级源点和超级汇点。 对于所有权值为正的点，我们从 $S$ 向其建立一条容量为点权的边，然后对于所有点权为负的点，我们由其向 $T$ 连一条容量为其点权绝对值的边。 我们之后按照原图建边，容量为无... Read More

我们考虑一个问题 玩具装箱 我们很简单可以求出 $O(n^2)$ 的巨简单的做法。 我们设 $f_i$ 表示 \[f_i=min_{j<i}\{f_j+(sum_i-sum_j+i-j-1-L)^2\}\] 我们考虑用 $s_x$ 代替 $sum_x+x$, $L’$ 代替 $L+1$ ,并且把与 $j$ 无关的东西从右边拿到左边。得到： \[f_i-(s_i-L')=min_{j<i}\{f_j+s_j^2+2s_j(L'-s_i)\}\] 我们考虑用直线 $b=y-kx$ 的形式转换这个式子。 \[\begin{cases} x=s_j \\ y=f_j+s_j^2 \\ k=-2(L'-s_i) \\ b=f_i-(s_i-L)^2 \end{cas... Read More

我们对于一个要求的数论函数 $f(x)$,定义 $S(n)=\sum_{i=1}^nf(x)$ 然后我们考虑构造一个 $S(n)$ 关于 $S(\lfloor\frac{n}{i}\rfloor)$ 的一个递推式子。 我们发现，对于任意的一个数论函数 $g(x)$ ,我们有： \[\sum_{i=1}^{n}\sum_{d\mid i}g(d)f(\frac{i}{d})=\sum_{i=1}^n(g\times f)(i)\] 然后我们考虑先枚举 $d$ \[=\sum_{d=1}^{n}\sum_{k=1}^{kd\le n}g(d)f(\frac{kd}{d})\] \[=\sum_{d=1}^{n}\sum_{k=1}^{\lfloor\frac{n}{d}\rfl... Read More

优点: 1.回带比原版高斯消元少，速度更快(一般情况下) 2.精度更好 3.代码实现更简单 --- 代码如下：模板P3389 #include<bits/stdc++.h> using namespace std; #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) #define N 110 #define eps 1e-7 int n; double a[N][N]; inline void Swap(double &x,double &y) { double tmp=x;x=y;y=tmp; } int main() { scanf("%d",&a... Read More

当时考场上因为这个炸掉，一年后回来复仇。 这里提供一个与大多数人不一样的做法。 首先考虑一个简单一些的问题，怎么应付单个询问？ 不难想到，我们对于一个日期，让他从 $-4713$ 年 $1$ 月 $1$ 日开始，然后一年一年地加，年加不了了加月，月加不了了加日。这样很容易做，具体的细节可以看代码实现。这样就拿下了 $50pts$。 但是肯定不能满足于这 $50$ 分。对于数据过大造成的TLE，我们考虑扩展我们的做法。实际上，优化的本质是重复利用之前已经求过的东西。然后可以想到从每个询问入手。可以自己先思考一下再往下看。 我们可以考虑将询问离线然后排序，每次将上一次求出的答案为起始的日期，然后重复较为暴力的算法。但是由于有的月份的上限比别的月份高，又或者 $1582$ 年这种比... Read More

什么叫分层图最短路，我不会/kk 感觉自己做法和其他题解不大一样所以过来发篇题解了。 未刻意卡常拿下最优解 题目大意 就是说给你一个 $n \times n$ 的网格图和 $m$ 个可换乘点，然后你只能在同一行或同一列（如果在行上移动，就不能在列上移动；反之同理）上移动，除非这个点是可以换乘的。每次走一格花费 $2$ 费，换乘花费 $1$ 费，求从 $(sx,sy)$ 到 $(fx,fy)$ 的最小费用。 其中:$n \leqslant 20000,m \leqslant 100000$ 分析 可以发现如果对于每个格点都存储信息是不可行的，我们考虑优化空间：发现我们的路径实际上就是一直冲，然后只有在部分换乘点转弯，所以我们可以把换乘点联系起来，在换乘点之间跑最短路。 具... Read More

前言 本蒟蒻重学线段树，发现了这道题可以用线段树做。 虽然数据范围很小可以直接暴力，但由于在练习线段树所以打算用线段树写这道题。 本题解针对已经有线段树基础的巨佬，不懂线段树原理的话可以学习线段树后再阅读本题解。 审题 刚看题的时候以为大概是个线段树模板，结果发现事情并不简单。 题目要求的不是剩下多少棵树和砍掉了多少棵树木，而是要求剩下和砍掉了多少棵树苗。 并且需要注意区间是从0开始的。 那么注意到这些差不多就可以开始想做法了。 解决 因为种树人每次种树种植的都是树苗，所以只有最初的区间上会有一整个区间的树木。所以我们可以对于树木建立一棵线段树，再对于树木和树苗共同建立一棵线段树。这样在砍树的时候分别查询两棵线段树并且进行差分，就可以得到区间上砍掉的树苗的数量。最后... Read More

题意简述 $n$( $1≤n≤2×10^5$ )个点，每个点 $i$ 有一个点权 $a_i$ ( $1≤a_i≤2×10^{12}$ )，将两个点 $i$,$j$ 直接相连的花费是两个点的点权和 $a_i+a_j$，并且对于特别的$m$( $1≤m≤2×10^5$ )条边 $u_i$ , $v_i$ 可以通过花费 $w$ 点费用连接，求使得所有点互相连通的最小费用。 我们可以从数据范围看出需要注意的事项： 分析1.从$n$和$m$的范围可以看出我们最终的复杂度是带 log 的。 分析2.从$a_i$，很显然需要 long long。 接下来就从分析1导入正题。 Solution 看到关键词”连边”,”最小费用”,”边权”。 想到什么了？这不是我们可爱的最小生成树吗！ ... Read More

前置知识 矩阵乘法 矩乘快速幂 领接矩阵k次方的意义 因为我不知道怎么证明这个，就直接告诉你，若 $A$ 是一个领接矩阵,那么 $A^{n}_{i,j}$ 的意义为点 i，到达点 j 长度为 k 的路径数量。 是不是看着就觉得很好用 但是很显然 k 比较大的时候我们不可能一层一层乘上去。所以可以考虑矩乘快速幂优化。 长度小于等于k的路径计数 考虑建立虚点，使原始点与之连边，并使虚点对自己建立自环， 这样，长度小于k的方案数会通过进入虚点自环计入最后的答案。如果直接把原始点的自环连接起来，可能点在自环之后再继续遍历，导致方案数偏大。 最后统计答案就是 k 次方的领接矩阵上原始起点到原始终点，以及原始起点到虚点终点的方案数之和。 Read More

实际上就是个链表。 #include<bits/stdc++.h> using namespace std; int n,m; vector<bool>vis; vector<int>head,next,to,val; /* head[i]存储以i为起点的第一条边的编号 next[i]存储编号为i的边的同起点的下一条边 to[i]存储编号为i的边所连向的点的编号 val[i]存储编号为i的边的边权 */ void add(int u,int v,long long w) { next.push_back(head[u]); val.push_back(w); head[u]=to.size(); to.push_back(v); }//加边... Read More

费马小定理（模数是质数） long long power(long long a,long long b,long long c) { a=a%c; long long res=1; while(b>0) { if(b&1) res=(res*a)%c; a=(a*a)%c; b=b>>1; } return res%c; } long long niyuan(long long a,long long b)//a在(mod b)意义下的逆元 { return power(a,b-2,b); } 扩展欧几里得（gcd(a,b)|c） int exgcd(i... Read More

我们先把跳表入个门。 我们发现很多时候我们能不写平衡树就不写，像有的巨神喜欢用线段树一样（但是线段树的常数我们就不多说了），那我们就也整一点比较怪的东西。我们考虑用链表维护一些平衡树的信息。 最近学了链表之后发现这个东西就是个神，支持很多常数小的操作甚至直接配合其他算法整出各种优越于其他做法的复杂度。所以不例外的，我们用链表维护的速度比大多数平衡树都快。 废话就不多说了，进入正题。 首先介绍一下跳表的核心思想，其实就是通过跳过不必要的细节来达到目标，其思想类似倍增和二进制分组。但是这两个算法都是对于一个数来说的，现在我们是一个数据结构，扩展到了节点与节点之间的连接，我们如何维护？ 所以发明跳表的人很明智的想到了通过对链表分层来实现这种跳跃。 具体来说是怎么分层呢？每次我们将... Read More

引入 如果你已知一个序列，你已知其 $[2,6]$ 的区间和以及原序列，现在要你求$[2,7]$的区间和，你会怎么办？ 显然我们可以在 $[2,6]$ 的基础上加上原序列的第 7 位，就得到了 $[2,7]$ 的区间和。 同理，如果我们需要求出 $[2,5]$ 的区间和，我们只需要在 $[2,6]$ 的基础上减去原序列的第 5 位即可。 很好理解对吧，莫队的思想就是这样，每次这样一位一位的扩展。 优化 莫队可以用于解决一些区间问题。由于含有多次询问，莫队得以展现其优势。 但是对于一种类型的情况: 查询区间$[1,1] [n,n] [1,1] [n,m]$… 此时我们每次询问直接处理了整个序列，复杂度直接起飞$O(nm)$ 所以我们对询问进行离线，并对询问的左端点分块... Read More

狄利克雷卷积 定义: $(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)$ 很显然满足交换律和结合律。 积性函数 为积性函数的有: $I (n)$ (或$1(n)$ ),恒等于1，所以叫恒等函数 $\epsilon (n)$ (或者$e(n)$ ),当且仅当 $n=1$ 时，其值为 $1$,否则为 $0$,其满足($e*f=f$)(因此为狄利克雷卷积的单位元) $id(n)=n$ 为单位函数。 以上为完全积性函数。 完全积性函数: 对于任意整数 $a$ 和 $b$ 满足 $f(ab)=f(a)f(b)$ 以及： $\varphi (n)$ ,欧拉函数，小于 $n$ 的整数中与 $n$ 互质的数的个数。 $\mu (n)$ ,莫比乌斯函数，接... Read More

突然发现自己dp极其菜，背包一个不会/kk(我没开玩笑) 那全部学一遍。 01背包 问题:n 种物品，每种物品有一个大小 $v_i$，一个价值 $c_i$ 可以选择一个或不选，求背包容量为 m 的情况下(指所选物品大小之和小于等于m)选择的物品价值和的最大值。 我们可以设 $f_{i,j}$ 表示在前 $i$ 个物品中选择，背包容量为 $j$ 时可以取到的价值和最大值。 考虑选择一个物品带来的影响：会占用 $v_i$ 的容量，并且获得 $c_i$ 的价值。不选即无变化。不难推出转移方程。 \[f_{i,j}=max\{f_{i-1,j},f_{i-1,j-v_{i}}+c_{i}\}\] 发现 $f_{i,j}$ 只会受 $f_{i-1,x}$ 的影响，所以考虑省去一维。... Read More

终于来补线段树合并了，之前本来打算写的，结果懒了。 前置知识 动态开点线段树 算法操作 就是对于每个点维护一颗不全的线段树，对于每个节点记录其对应线段树的根节点。对于需要其子树贡献的节点，自下而上合并线段树，再查询。 很显然，和 Dsu on tree 是同类的算法. 具体实现 我们只需要知道线段树的合并即可，线段树大家再熟悉不过了吧。 我们考虑在叶子结点的时候将两线段树的节点信息合并，具体如何合并我们视题目而定。如果题目保证不再访问合并前的线段树，我们可以将其中一颗树作为载体合并，这样可以节约空间。对于其中一颗子树没有的节点，我们直接把它嫁接过来就可以了。 代码实现，和其他数据结构合并有异曲同工之妙: int merge(int x,int y){ if... Read More

就是对于一颗动态开点的线段树（而且一般为权值线段树），我们把它拆开拆成两份（一般来说：为了方便，按sz分裂） 可以用来干嘛呢，小编也很疑惑，或许是可以用于把这边线段树的区间转移到另一边？ 那么废话不多说直接开始。 实现原理 有点类似于求排名为 $k$ 的数的过程，考虑其左子树的值，如果这个值大于当前分裂线（我们设为 $k$），我们直接就是把右子树挂到新树上，进入左子树。否则就是直接进右子树。当然如果直接相等了，我们只需要挂上右子树即可。（我们可以使用 $Swap$ 来实现挂树的操作） 原理不难理解，那就直接 Code: void split(int x,int &y,LL k){ if(!x) return; y=new_node(); LL key=... Read More

支持修改区间加、区间乘、查询区间和的线段树结构体封装版 可以类比的写出其他操作 struct node { int l,r,mid; long long d,lazyadd,lazymul; }; struct tree { node t[N*4]; void build(int i,int l,int r) { t[i].l=l;t[i].r=r;t[i].mid=(l+r)>>1; t[i].d=t[i].lazyadd=0;t[i].lazymul=1; if(l==r) { t[i].d=a[l]; return; } build(i<<1,l,t[i].mid); build(i<<1|1,... Read More

用于维护异或的数据结构。（又是模拟赛保龄过来补） 废话多不多说了，直接上正题。 先说什么是线性基吧。() 就是说对于一个集合，如何它对于异或在线性基集合中封闭。那么我们认为之歌构造出的集合是线性基。对于异或封闭是什么意思？就是说它内的元素异或来异或去就只会得出原集合的东西。 怎么构造？ 考虑对于每一个数，我们考虑从高到低枚举数位，然后对于这一位没有数的数位，直接把当前数放到这一位中，否则我们异或上这一位的数，然后只需枚举数位。 Code: inline void ins(LL x){ for(int i=63;i>=0;--i){ if(!((x>>i)&1)) continue; if(!p[i]){ p[i]=x;break; ... Read More

封装一个矩阵，带乘法,加法和清空 struct matrix { int n,m; long long a[N][N]; friend matrix operator * (matrix x,matrix y) { matrix c; c.n=x.n;c.m=y.m; c.clear(0); for(int i=1;i<=c.n;++i) { for(int j=1;j<=x.m;++j) { if(x.a[i][j]) for(int k=1;k<=c.m;++k) ... Read More

普通生成函数 对于一个序列 $a$ ,其生成函数形如(本质上是个多项式): \[F(x)=\sum_{n}a_nx^n\] 用通俗一点的话来解释生成函数这个概念，其实就是把序列按照编号从小到大的顺序放到多项式次数从低到高的系数里。所以说，如果该序列有通项公式，那么其生成函数的系数就是通项公式。 又由于生成函数的本质是多项式，所以其加法和乘法等运算皆与多项式相同。 生成函数的封闭形式 我们发现对于 $<1,1,1,1,…>$ 的生成函数 $F(x)=1+x+x^2+…$ 有 $xF(x)=x+x^2+x^3+…$ 那么不难发现，因为序列无穷长，其满足 $xF(x)+1=F(x)$ ,可解得 $F(x)=\frac{1}{1-x}$ ,这个解出来的东西一般称... Read More

用于解决树上路径长问题的算法，复杂度是比较优秀的 $O(nlogn)$ 直接按照题目来讲。点分治1 我们要维护树上路径长度为 $k$ 的路径是否存在（当然视题目而定，点分治的操作比较灵活）。这类问题我们选用点分治。 具体怎么操作呢？ 一般就是，每次用vis标记删除根节点，然后对于所有没被删除的（除了它自己）计算到当前根节点的距离，然后对于不同子树中的点进行组合，看是否出现我们所要的答案即可。 但是显然这样并不是优秀的。我们发现还有很多地方可以优化。 根节点 很显然我们刚才的做法会被链这类的东西卡掉，于是考虑如何选择更优的节点。 然后我们发现如果每次选择树的重心，这样就可以保证复杂度。而重心我们直接套路的求就可以了。 void findRoot(int u,int f)... Read More

可以说是带修改的点分治。（当然也可以不带修改，是那种需要多次询问的） 灵活性很强，我们可以维护一些树上点对问题。 话不多说了，直接进入正题。 具体操作 我们考虑对于保存点分治的路径,然后把这些点依次连接起来，点分树就建好啦。（很显然这个只是把树重构，然后保证树高为 $log\ n$） 可以发现这样的搞法可以把一些邪教的暴力变得没那么邪教。 但是单走暴力显然是不优的，我们同样是维护当前点关于其子树的信息，一般考虑使用动态开点的数据结构（比如 vector树状数组 动态开点线段树） 修改和查询都可以考虑不断的从修改或查询点跳父亲，按照情况修改即可。 题目细讲 上模板题 震波 翻译一下题意，就是说给你一棵树，每个点有价值，支持修改和查询操作。每次修改可以修改一个点的价值。... Read More

优秀资料 素数 这个很好写。我们可以很好的理解埃氏筛，然后加一些优化即可得到线性筛。 inline void get_pri(int n){ for(int i=2;i<=n;++i) not_pri[i]=0; not_pri[1]=1; for(int i=2;i<=n;++i){ if(!not_pri[i]){ pri[++pri[0] ]=i; } for(int j=1;j<=pri[0] and pri[j]*i<=n;++j){ not_pri[i*pri[j] ]=1; if(i%pri[j]==0) break;//优化，防止重复筛同一个数 } } } 因为每个数都可以被拆分成若干个质因数，所... Read More

做了相当一部分的退火题练手，现在才算刚刚入了门。 于是做一个经验总结。 随机函数 有没有觉得 $rand()$ 莫名的不好用？我们在此为您推荐 \[mt19937!\] 在支持 $c++14$ 的环境下，可以生成更大的随机数，而且更快，岂不美哉？ 实用展示 mt19937 rd_ori(time(0)+114514); template<class T> inline T rd(T L,T R){ return std::uniform_int_distribution<T>(L,R)(rd_ori); } 这样调用 $rd(l,r)$ 就能生成范围内的随机数了，这比 $mod$ 来 $mod$ 还是方便了很多。 然后对于暴刷数列排列的，我们还... Read More

由于算法基于随机，不适宜作为题目正解，但在参数调得好的时候可以得到较高分数甚至AC，用于实在迫于无奈时的算法或暴力算法范围外的骗分算法 典型的邪教算法（我就喜欢邪教的） 基本思想是随机转移，从而确定最优解，大多数用于计算几何（但其实你如果够牛也可以在其他情况下用来骗分） 基本的实现步骤是： 1.取一个经验总结下的可能性较大的最优解（贪心或不正经结论） 2.按照当前选择的解进行转移，并设定较为科学的转移幅度 3.求出当前随机解的贡献，然后按照最优解必选、一定概率接受劣解的原则选取解 4.设置好初始温度，降温系数，结束温度等餐数（需要多次调试）同时为了保证解的最优性，可以进行多次退火。 对于第一点，可以通过编写暴力代码发现一些不正经结论，但是这个对正解的影响不大 个人认为最有... Read More

相当于把树上的链抽出来变成区间进行操作。 重链剖分（本文重点）： 本文依照P3384 【模板】轻重链剖分/树链剖分的实现进行讲解。 就是剖分出重链覆盖全树。 重链：除开头的端点为轻儿子外，其他节点全为重儿子的链。 重儿子：一个节点的儿子中子树大小最大的儿子。 要进行树链剖分，先要进行预处理。需要处理出以下信息： $top[u]$ u节点所在重链的开头端点的编号。 $dep[u]$ u节点的深度。 $fa[u]$ u节点的父亲节点的编号。 $dfn[u]$ 时间戳，u节点被遍历到的顺序。 $rank[x]$ 时间戳为x的节点的编号。 $size[u]$ 以u为根的子树大小。 $son[u]$ u节点的重儿子的编号。 总共七个(七国之乱 预处... Read More

简单论一下区间修改，单点查询的树状数组。 我们是考虑维护一个对于原数组的差分数组，然后取答案时用原数组加上查分数组得到。 资料 二维树状数组 参考资料:资料 单点修改 void modify(int i,int j,int k) { a[i][j]+=k; for(int x=i;x<=n;x+=(x&-x)) { for(int y=i;y<=m;y+=(y&-y)) { c[x][y]+=k; } } } 区间查询 int query(int i,int j) { int res=0; for(int x=i;x;x-=(x&-x)) { for(int y=j;y;y-=(y&-y)) {... Read More

在用树剖解决问题时发现，每次跳链的时候，就有跳到两点LCA的可能。 所以还是有之前树剖的思想，其实和倍增的LCA很像。 优点:常数小，实现很好理解也很好写。预处理复杂度$O(n)$,查询$O(log\ n)$,附带常数小。 感觉比倍增好写，而且还快。 实现如下:(预处理点这里) inline void Swap(int &x,int &y) { int tmp=x;x=y;y=tmp; } int LCA(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) Swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y]) Swa... Read More

在某些情况下可以和树剖替换。（当然某些情况替代不了，我愿称之为小树剖） 前置知识 倍增求LCA 了解差分思想 (既然要替代树剖怎么可能会用树剖求LCA呢/xyx) 引入 首先我们都知道差分是可以用来通过单点修改维护区间信息的（如单修区查的树状数组），因为我们在前面加上，再在后面减掉，中间这一段是得到了一个区间加的收益的。 那么我们考虑把这个区间转到树上。 分析 我们考虑对于一条路径区间加，然后思考如何差分。 我们记路径两个端点为 $x$, $y$。不难发现树上路劲总是由路径 $(x,LCA(x,y) )$ 和路径 $(y,LCA(x,y) )$ 组成，显然这个 $LCA(x,y)$ 是突破口。 可以效仿普通的差分在 $x$,$y$ 处加上需要增加的值，发现... Read More

简单讲一下极角排序。 我们对于极角排序，就是以x轴为始边，然后到当前点所在的终边，以原点为顶点所形成的角来排序。第二关键字按照到原点的距离。 tan2极角排序 我们把坐标放入 $tan2(y,x) $ 就可以得到极角了。返回的范围是 $[-\pi,\pi]$ 其中c是我们想要以其为中心进行极角排序的点，下同。 inline bool cmp(point x,point y){ db ax=tan2(x.y-c.y,x.x-c.x),ay=tan2(y.y-c.y,y.x-c.x); if(sgn(ax-ay)==0) return x.x<y.x; return ax<ay; } 叉积极角排序 由于我们知道叉积可以判断两向量的顺逆时针的位置关系，所以可... Read More

顾名思义，维护权值的线段树。在一定情况下可以代替平衡树使用。 原理是用线段树维护桶，节点维护子树中数的个数。所以空间开销与数据的值域相关。 那要是值域过大怎么办:离散化和动态开点，离散化可以将数据值域缩小到数据数量,将空间复杂度变为 $O(n)$，缺点是需要离线。而需要在线则需支持动态开点，即用多少开多少。 动态开点线段树 权值线段树:支持平衡树操作（翻转除外），并附带离散化 P3369普通平衡树 #include<bits/stdc++.h> using namespace std; #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) #define LL long lo... Read More

模板题链接:P2516 HAOI2010最长公共子序列 我们借题解第一篇的巨佬的图 我们$O(n^2)$的枚举$i$,$j$(分别对应两个串的下标) 我们记两串分别为$a,b$，记$dp[i][j]$为截止到$i,j$时的最长公共子序列,如果$a[i]==b[j]$匹配成功，我们可直接用$dp[i-1][j-1]+1$来扩展$dp[i][j]$,相当于在网格图中连一条斜边。若没有斜边,我们就通过$dp[i-1][j]$和$dp[i][j-1]$取$max$来扩展。 对于方案的统计，和上面是同理的，只需注意在$dp[i-1][j-1]=dp[i][j]$时，$dp[i][j-1]$和$dp[i-1][j-1]$由$dp[i-1][j-1]$转移来，再分别转移到$dp[i][j]$... Read More

需要注意树上做最短路是$O(n)$,因为只需要一次dfs SPFA #include<bits/stdc++.h> using namespace std; int n,m,ss; bool vis[500010]; int q[1000010],dis[500010]; vector<int>head,to,nxt,val; void add(int u,int v,int w) { nxt.push_back(head[u]); head[u]=to.size(); to.push_back(v); val.push_back(w); } void SPFA(int s) { int l=0,r=0; for(int i=1;i<=n;... Read More

#include<bits/stdc++.h> using namespace std; #define re register #define MAXN 5010 struct side { int u,v,w; }s[200010]; int fa[MAXN],n,m,ans,cnt,cnt1; inline int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } bool cmp(side a,side b) {return a.w<b.w;} int main() { scanf("%d%d",&n,&m); for(re int i=1;i<=n;++i) fa[i]=i... Read More

因为之前学东西学得太菜所以重学了。 不说多了直接正题。 思想解析 本质上就是普通的BST，只是多了一个重建不平衡子树的重构操作。 很显然每个平衡树都有一个维护平衡的操作，那么替罪羊树的平衡操作就是重构。 最开始的时候教练说替罪羊十分暴力，一不平衡整棵树拍扁重构。但是其实并不是整棵树重构，而且操作并不算特别暴力，我个人觉得挺妙的，而且速度比平衡树双子（treap，splay）快。 好那么快速开始。 操作讲解 重构(rbu) 核心操作！开始。 我们对于一个不平衡的子树进行重构，很显然如果我们随随便便就重构是极其低能的，我们要对不平衡进行定义。于是有 $canrbu$ 函数。我们设定一个平衡因子 $alpha$ ,对于一颗子树，如果它的大小乘上 $alpha$ 小于等于左... Read More

前置知识 对于$N^={\lfloor n/i \rfloor\mid i\in[1,n]}$. (1) 满足 $\lfloor n/i \rfloor,x\in N^$ 的最大的 $i$ 为 $\lfloor n/x \rfloor$. (1)证明: 显然有 $x\le n/i < x+1$ $\Leftrightarrow ix \le n < i(x+1)$ $\Leftrightarrow n/(x+1) < i \le n/x$ 又由于 $i\in Z$ ,所以 $\lfloor n/(x+1) \rfloor +1 \le i \le \lfloor n/x \rfloor$ Q.E.D. 稍微变一下就是 $\lfloor n/\lfl... Read More

\[A{^m_n}=\frac{n!}{(n-m)!}\] \[C{^m_n}=\frac{n!}{m!(n-m)!}\] 实现直接调用逆元套公式即可 $C{^m_n}$ 也写作 $\tbinom{n}{m}$ ,读作 “n 选 m”. Read More

用于解决前置性问题（如选A前需要先选择完B和C） 队列换成优先队列并反向建边可保证答案字典序最大或最小 vector<int>t; priority_queue<int,vector<int> >q; bool topo() { t.clear(); for(int i=1;i<=n;++i) { if(!d[i]) q.push(i); } while(!q.empty()) { int u=q.top();q.pop();t.push_back(u); for(int i=head[u];~i;i=nxt[i]) { if(!(--d[to[i]])) q.push(to[i]); } } i... Read More

用于处理矩形覆盖问题,因为是线段树实现所以拥有 $O(nlogn)$ 的复杂度。 主要思想是虚拟出一条平行与 x 或 y 轴的无限长的线,我们称之为扫描线。一路扫过去，如果发现触碰到矩形的边(被当前扫描线完全覆盖)就停下进行相关操作。 1 “对于点的坐标太大，不就变成暴力一样的的东西啦?” 对于这种情况我们两种解决方法，一种是离散化，一种是动态开点。个人认为离散化做起来比较方便。 因为我们只有在扫描到线的时候才需要处理信息，所以相邻两线之间的信息是不会发生改变的。我们可以直接进行离散化。 2 对于线段树，我们大部分情况维护一个 cnt 为当前区间被几个矩形覆盖，以及一个 len 表示当前区间被覆盖的区间长度。 所以我们扫到一条线，就可以对这个区间的 cnt 进行修改，再... Read More

直接给公式，你会发现它直接覆盖了费马小定理。 $a^b=a^{b\% \varphi(p)},gcd(a,p)=1\ (mod\ p)$ $=a^b,gcd(a,p)\not=1,b < \varphi(p)\ (mod\ p)$ $=a^{b\%\varphi(p)+\varphi(p)},gcd(a,p)\not=1,b\ge \varphi(p)\ (mod\ p)$ Read More

P1082 #include<bits/stdc++.h> using namespace std; #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1;y=0; return a; } int d=exgcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-(a/b)*y; return d; } bool liEu(int a,int b,int c,int &x,int &y) { int d... Read More

快读 inline int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {s=s*10+(ch^48);ch=getchar();} return s*f; } 快写 inline void write(int x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } 但是由于递归的常数巨大 所以我们可以采用栈来输出 注:stat... Read More

一般用于连通块查询 加入size数组可以做到查询连通块大小 #include<bits/stdc++.h> using namespace std; int fa[100010],n,m; inline int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } inline void join(int x,int y) { if(find(x)!=find(y)) fa[find(y)]=find(x); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { fa[i]=i; } for(int i=0;i<... Read More

平面图 就是放在平面上展开，存在一种画法能够使得图的边与边之间没有交点，这玩意就叫平面图。 但是一般来说吧，这个东西要配和着对偶图来使用。 对偶图 就是对于原平面图的每一条边，将与其接壤的两个面在对偶图中连一条边。特殊地，当且仅当对于一条边两边的面是同一个面，那么会出现自环。 然后不难发现，对偶图的对偶图是原图。 给出辅助用图。 (改自 百度百科，那里的图有一点点问题) 一些性质 （要求有源汇点）平面图的最小割可以转化为对偶图的最短路。 然后要保证这么一条最短路要横跨源汇点所属的两个区域 题目 海拔 狼抓兔子 Read More

对于每一个集合维护点与根的权值。 如果对权值取模，可以得到种类并查集，相当于同时维护数与数之间的多种关系，如包含与不包含。 典型例题:P2024 [NOI2001] 食物链 两种实现方式：(以 P2024食物链 为例) 1.维护点到根的关系值，通过权值判断两点是否在同一集合。 实现如下: #include<bits/stdc++.h> using namespace std; #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) #define LL long long #define N 50010 // 0同类 1吃 2被吃 inline int read() { i... Read More

随便提几笔吧，时间不太充裕就不写太多了。 就是在区间的基础上再加上一个时间。 来个例题 [数颜色 维护队列](https://www.luogu.com.cn/problem/P1903) 直接就是考虑按照 $l$ 所在块, $r$ 所在块, $t$ 的优先级排序，然后可以证明在块长取 $n^{\frac{2}{3}}$ 时最优，可用最劣情况证明其复杂度。 然后就是稍微注意点细节就好，比如离线化问题的时候记得修改原数组之类的。 那么结合例题看下代码就大概能理解了吧。 code： #include<bits/stdc++.h> using namespace std; #define LL long lo... Read More

#include<bits/stdc++.h> using namespace std; #define N 5010 int n,m; vector<int>head,to,nxt,val; void join(int u,int v,int w) { nxt.push_back(head[u]); head[u]=to.size(); to.push_back(v); val.push_back(w); } int dis[N],cnt[N]; bool vis[N]; int q[N*N]; bool spfa() { int l=0,r=0; for(int i=1;i<=n;++i) { dis[i]=0x3f3f3f3f; ... Read More

发现以前学的时候摸鱼，都没有搞明白原理，现在来捡了。 左偏树是一种可并堆，满足以下性质: 堆的性质：根的值比儿子大 左偏性质：左子树的距离不小于右子树的距离 距离是什么意思？就是指当前节点到最近的外节点的距离。 外节点是什么？就是不完整的节点，也就是儿子个数不满的节点。 堆的性质决定了左偏树的作用，而左偏性质则保证了复杂度。 先考虑如何处理距离。因为一个节点的儿子如果不满，为保证左偏性质，那么不管怎么样它的右儿子一定是空的，也就是0，那么我们把0号节点的距离值赋值为-1，这样外节点的距离就是0，考虑用右儿子距离+1更新节点，这个过程我们在递归回溯实现即可（融入到合并的递归中）。 合并操作 左偏树的核心操作，不难，我们看着代码讲。 inline void Sw... Read More

对拍模板，很好理解，就不多讲了。 #include<bits/stdc++.h> using namespace std; int main(){ while(1){ system("data.exe > data.in"); int t=clock(); system("hard.exe < data.in > hard.out"); system("easy.exe < data.in > easy.out"); printf("%dms\n",clock()-t); if(system("fc hard.out east.out")){ //如果系统是linux，把fc改成diff printf("W... Read More

先给出最为基本的公式 \[\lvert\bigcup_{i=1}^{n}A_i\rvert=\sum_{C\subseteq A}(-1)^{size(C)-1}\lvert\bigcap_{e\in C}e\rvert\] 这个可以看一些小学的具体一点的问题就可以比较好的理解然后推广。严谨证明我们用二项式定理展开，就不多说了。 min-max容斥 两个核心式子 \[min\{max\{a,b\},c\}=max\{min\{a,c\},min\{b,c\}\}\] \[max\{a,b\}=a+b-min\{a,b\}\] 所以有: \[ans=max_{i=1}^{n}a_i=\sum_{T\subseteq A}(-1)^{\vert T\vert+1}minT\... Read More

筛选素数 枚举每个数，并枚举它的倍数，给它的倍数打上非质数标记 用bitset存储标记会加速一倍，空间开销小一倍 { pri[1]=1; for(int i=2;i<=n;i++) { if(!pri[i]) { for(int j=2;i*j<=n;j++) { pri[i*j]=1; } } } } Read More

把小的合并到大的 int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } inline void Swap(int &x,int &y) { int tmp=x;x=y;y=tmp; return; } void join(int x,int y) { int xx=find(x),yy=find(y); if(xx==yy) return; if(size[xx]>size[yy]) Swap(xx,yy); fa[xx]=yy; size[yy]+=size[xx]; return; } Read More

可持久化就是支持维护不同时间下的版本的数据结构啦。 那么可持久化线段树能干什么很显然了。 可持久化线段树又叫主席树，因为来历大家都知道就不多说了。 那么就直接讲核心操作了，就是克隆节点。 克隆节点 就是在修改的时候（或者维护多棵有公共节点的线段树时）使用。把有变化的节点新建，由于每次如果进行单点修改是修改一条长为 $log\ n$ 的链所以空间复杂度是 $O((n+m)log\ n)$ 的（m是操作数）。 直接把修改前的节点克隆过来即可。回溯时 $pushup$ 即可。 单点修改示例： int modify(int i,int p,int val){ t[++tot]=t[i]; i=tot; if(p==t[i].l&&t[i].r==p){... Read More

#include<bits/stdc++.h> using namespace std; long long power(long long a,long long b,long long c) { a=a%c; long long res=1; while(b>0) { if(b&1) res=(res*a)%c; a=(a*a)%c; b=b>>1; } return res%c; } long long a,b,c; int main() { scanf("%lld%lld%lld",&a,&b,&c); printf("%lld^%lld mod %lld=%lld",a,b,c,powe... Read More

也是直接给公式了 \[\big(^n_m\big) mod\ p=\big(^{n\%p}_{m\%p}\big)\big(^{\lfloor n/p\rfloor}_{\lfloor m/p\rfloor}\big)\] Read More

多用于 权值线段树 用多少点开多少点，空间复杂度降至 $O(n)$ P3369 #include<bits/stdc++.h> using namespace std; #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) #define LL long long #define N 100010 #define INF 10000000 struct node_val_tree { int l,r,mid; int ls,rs; int d; }; struct val_tree { int tot; node_val_tree t[N*4]; void build(... Read More

概念 中缀表达式 就是我们平时用的式子。 前缀表达式 也叫波兰式，除了处理顺序与后缀表达式相反（从右往左），其他完全一致。 后缀表达式 也叫逆波兰式，从左往右处理，如果扫到数字，就把数字入栈；如果是字符，那么从栈顶取出两个数字进行运算，在将计算结果入栈。最后栈中的元素为结果。 表达式转换 前、后缀转中缀 按照概念操作即可。 中缀转前、后缀 资料推荐 Read More

#include<bits/stdc++.h> using namespace std; inline int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();} while('0'<=ch&&ch<='9') {s=s*10+ch-'0';ch=getchar();} return s*f; } int T,n,m; vector<int>head,to,nxt,val; void join(int u,int v,int w) { nxt.push_back(head[... Read More

维护凸壳 这个我喜欢读(tu1 ke2)。我们先从简单的入手。 这个分为上凸壳和下凸壳。顾名思义就是一个维护多条函数的最大值，一个维护最小值。 这个我们有一个例题 水平可见直线 其实是因为考场上没学但是写出来了而作为纪念找到的！(虽然那道题还是因为没调完爆零了/kk) 我们考虑按照每条直线的斜率排序，然后就可以得到非常不错的结果。因为斜率最大的和斜率最小的代表了两边界，可以很顺利的一路搭过来。 其中我们用单调栈来维护这些线段。一般我们考虑栈中的后两个直线以及当前的直线。很显然，因为当前的直线是目前所有直线中斜率最小的，所以它一定在某一处可以成为最大值，具体的位置是相对靠近左的。所以我们考虑新加进来的直线对之前栈中其他直线的影响。 还是得要一张图，这张图讲得还是挺详细的，就... Read More

预处理复杂度$O(n\ log\ n)$,查询复杂度$O(log\ n)$。 主要思想是倍增，通过预处理出夫亲的倍增数组实现快速求LCA 1 的父节点取 0 是为了方便树上差分，1 的深度设置得比 0 大是为了防止在求LCA时跳到0. 挺好理解的。 #include<bits/stdc++.h> using namespace std; #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout); int n,m,s; vector<int>head,nxt,to; void add(int u,int v) { nxt.push_back(head[u]); hea... Read More

有的时候我们为了方便对于低位进行操作，我们要把二进制数翻转过来，这样可以避免使用大量的取模操作。 直接入正题 思想解释+具体代码 我们要求 $[0,2^{len})$ 的区间中的每一个翻转。 首先要知道的是什么叫一个 $a$ 进制数的翻转。 我们以 $2$ 进制为例，$(x_{n}…x_{2}x_{1}x_{0})_{2}$ , 它的翻转就是 \[rev(x_{n}...x_{2}x_{1}x_{0})_{2}=(x_{0}...x_{n-2}x_{n-1}x_{n})\] 我们考虑线性求解这个东西。 发现对于一个数 $t$，其翻转 \[rev(x_{t}...x_{2}x_{1}x_{0})_{2}=(x_{0}<<t)\mid (rev(0x_{t}... Read More

用于优化多重背包。 对于每一种物品的可选个数，把它按照二进制拆分出来，如： \[24->1+2+4+8+9\] 然后把这些数分别乘到大小和价值数组里面(每个数开一个)然后跑01背包即可。 因为这样的数可以拼凑出所以需要的情况。 代码实现如下： for(int i=1;i<=n;++i){ int C=read(),V=read(),T=read(); for(int j=1;j<=T;j<<=1){ T-=j; v[++tot]=V*j; c[tot]=C*j; } if(T){ v[++tot]=V*T; c[tot]=C*T; } } for(int i=1;i<=tot;++i)... Read More

废话不多说，直接入正题。 误差 const db eps=1e-9; inline int sgn(T x){ return x<-eps?-1:x<eps?0:1; } 我们浮点数计算计算几何的时候是存在误差的，我们用上面这个函数来修正。 对于 $x < -eps$ ,我们认为它属于负数，返回 $-1$. 对于 $-eps \le x < eps$ ,我们认为它属于是零，返回 $0$ 剩下的属于正数，返回 $1$. 这样我们先把比较运算写出来，然后移项成减法形式，再在外面套一层浮点数修正函数即可。 这个养成好习惯即可。 点(point) 我们已经非常熟悉的东西，由横纵坐标来组成。当然也有更高维的点，但是在这里我们暂且不提，只考虑二... Read More

发现以前都没有真的理解二分边界应该取多少。所以手写 $lower_bound$ 出了一些锅，于是用了3种不同方式拍了几组数据改了下错，才真正理解了。 先上对拍程序(windows) $mian.cpp$ #include<bits/stdc++.h> #include<windows.h> using namespace std; #define LL long long #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) inline int read(){ int s=0,f=1;char ch=getchar(); while(ch<'0'||'9'&... Read More

可参考资料: 资料1 资料2 实现如下: LL CRT(){ LL num=1,ans=0; for(int i=1;i<=n;++i) num*=a[i]; for(int i=1;i<=n;++i){ LL mum=num/a[i],x,y; exgcd(mum,a[i],x,y); ans=(ans+1ll*r[i]*mum*x%num)%num; } return (ans%num+num)%num; } Read More

算法标签：排序，随机化，分治。 我这个人很喜欢比较玄学但是优秀的算法和数据结构。 众所周知，我们考试的时候经常遇到毒瘤出题人卡算法。但是我们也知道：“如果我自己都不知道我在干什么，你就别想卡我啦。” 所以说 $mt19937$ 天下第一！(不是CCF准用 c++14了嘛) 浅谈mt19937 简单提一下 $mt19937$ ,给一个使用示例吧: mt19937 RdOri(time(0)); #define rd(L,R) (int)((1.0*RdOri()/UINT_MAX)*(R-L+1))+L 这样就可以支持使用 $rd(l,r)$ 生成区间 $[l,r]$ 内的随机数了。 当然把宏定义里的类型 $int$ 改成其他类型也是可以的。 需要注意的是 $mt1993... Read More

#include<bits/stdc++.h> using namespace std; int n,m; int edge[500010][26],tot; int ex[500010]; void insert(char *s,int ls) { int p=0; for(int i=1;i<=ls;++i) { int c=s[i]-'a'; if(!edge[p][c]) edge[p][c]=++tot; p=edge[p][c]; } ++ex[p]; } bool find(char *s,int ls) { int p=0; for(int i=1;i<=ls;++i) { int c=s[i]-'a'; if... Read More

我们可以令$f[i][j]$表示区间$[i,i+2^{j}-1]$的最大值（最小值同理） 所以有$f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$ (根据上面的定义可以得出) 注：可以预处理出log2数组，进一步卡常。 #include<bits/stdc++.h> using namespace std; #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) #define LL long long #define N 100010 int f[N][30]; int n,m; int main() { scanf("%d%d",&... Read More

我当时知道ST表可以 $O(1)$ 求 LCA 的时候是极为震惊的，可以在需要反复使用 LCA 的时候卡常使用。 ST表！用于解决 RMQ问题 ST表 我可能写得不好,看专业的 怎么实现？ 考虑把求 LCA 转换为 RMQ问题。我们对于树求一遍欧拉序，就是那个回溯也会记录的那个。我们处理出每个数第一次在欧拉序中出现的位置，欧拉序上每个位置的深度，以及欧拉序上每个位置出现的点的编号。这些信息都可以在一次 $dfs$ 中求出。然后不难发现在回溯过程中加入的点是之前遍历的点的祖先，由此也不难推出结论。 在两个点在欧拉序上第一次出现的位置的区间中间的深度最小的点就是这两个点的 LCA 那么直接变成 RMQ问题，上 ST表。 Code: void dfs(int u,int f,... Read More

我们在原字符串中间添加 # 使得 manacher 可以同时处理奇偶回文 我们对于每一个 i ，若其未超出最大匹配到的范围，则使其按照区间内对称点对称，并按照其对称点的回文长度以及当前 i 到区间右端点取最小值更新当前 i 的回文长度。否则归为 1 。之后朴素算法更新答案，由于中间的那一个字符(包括 #)的对称点是其自身，所以更新后长度要减一。最后如果得到更远的回文范围我们就对范围进行更新。 #include<bits/stdc++.h> using namespace std; char a[11000010],s[22000210]; int len; void change() { s[0]=s[1]='#'; for(int i=0;i<len;++... Read More

完全顶替map #define Size 114514 struct Hash_map { int head[Size+10],nxt[N],tot; long long to[N];int val[N]; int hash(int x) { if(x<0) return (-x)%Size; return x%Size; } int& operator[](int x) { int u=hash(x); for(int i=head[u];~i;i=nxt[i]) { if(to[i]==x) return val[i]; } nxt[++tot]=head[u]; head[u]=tot;to[tot]=x; ... Read More

思想：把字符串变成数值比较。 我们选取这个 hash 公式: \[hash(s)=\sum_{i=1}^{len} s_i\times p^{len-i}(mod\ M)\] hash方法 自然溢出hash 我们使用 unsigned long long hash[N]; （$hash[k]$）来存储一个字符串下标 $[1,k]$ 的 hash 值 hash 公式就是: \[hash(s_{1,len})=hash(s_{1,len-1})\times p + s_{len}\] 我们知道 unsigned long long 在数值过大的时候会自动对 $2^{64}$ 取模 单hash 采用一个一大一小两个素数 hash 公式: \[hash(s_{1,le... Read More

#include<bits/stdc++.h> using namespace std; int n,m,tot; struct treap { int ch[3],pri,size,v; }t[100010]; void update(int x) { t[x].size=1+t[t[x].ch[0]].size+t[t[x].ch[1]].size; } int new_node(int x) { t[++tot].v=x; t[tot].size=1; t[tot].pri=rand(); return tot; } int merge(int x,int y) { if(!x||!y) return x+y; if(t[x].pri<t[y]... Read More

Tarjan系列！我愿称Tarjan为爆搜之王！ 1.Tarjan求LCA 利用并查集在一遍DFS中可以完成所所有询问。是一种离线算法。 遍历到一个点时，我们先将并查集初始化，再遍历完一个子树之后，将该子树的根的父亲指向当前点。 最后在回溯的时候给询问的答案更新一下，枚举一下 $v\in [1,n]$ 的点，看是否有询问，如果有询问更新一下 $LCA[u][v]=LCA[v][u]=find(v);$ 但是前提是 $v$ 已经被访问。 我们优化一下枚举的点，放入vector优化一下，就是 $O(n+m)$ 的复杂度了。 测试用题： T1 T2 T1 Code: 但是经过事实证明，有速度排行： 树剖 < st表 < 倍增 < Tarjan 什么东西天... Read More

Splay，即伸展树，较为受众的平衡树，依靠双旋的速度称霸（虽然替罪羊更快，但是splay在之后有光明的未来(可以发展为LCT),总之是比treap快） 平衡树调试两大题:P3369+P6136 注: 本文采用非递归 信息维护 我们对于splay树上的一个节点维护以下信息: $sz$ 子树大小 $fa$ 父节点编号 $ch[0/1]$ 左右儿子编号(0为左儿子，1为右儿子) $val$ 当前点权 $cnt$ 当前点权的出现次数 以及对与整棵树维护以下信息: $tot$ 节点总数 $rt$ 根节点编号 基本处理操作 $update$ 更新当前节点的$sz$ $stype$ 返回当前节点属于的儿子类型 $clear$ 销毁... Read More

对于一个多个子游戏的博弈，我们借助其SG函数研究这个先后手的胜负。 给一个定义，其中 $x$ 可以到达 $x_i$ \[SG(x)=mex\{SG(x_1),SG(x_2),...,SG(x_n)\}\] 然后对于mex,我们定义其为集合中没有的第一个非负整数。 然后我们就可以得到一个关于SG函数的性质。一个游戏的总和，为其子游戏的SG函数的异或和，若异或和为0，则先手必败，否则必胜。 然后对于求解SG函数，我们通过打表观察来得出结论。这个打表我们按照定义来即可。 Read More

不是费用流都需要用 SPFA 吗。 众所周知，SPFA 去世了，然后网络流显然有负边。于是我们可以像 Johnson 全源最短路一样，给边加上势能，具体实现看我之前的 博客 啦。 然后对于每一次跑 Dijkstra ，然后得到最短路，把势能要再加上这个最短路，可以证明这样操作一次图上不会再有负边。 也正因如此我们不能用 $dinic$ ，我们不保证在走了多条增广路后仍然边权非负，所以我们可以记录最短路的路径，然后每次增广一条，这样就能保证正确。这个似乎是 KM算法吗？反正都是增广一条，没有学过KM，所以不敢下定论。 code: #include<bits/stdc++.h> using namespace std; #define ll long long #def... Read More

来，背 稍微提一下原根的求法，我们对于模数(p-1)质因数分解，然后暴力枚举原根，我们发现原根满足 $^{n}_{i=1}g^{\frac{p-1}{p_i}}\not\equiv 1(mod\ p)$ 就没了。 然后就是模数需要满足是$X\times 2_n+1$ 的形式，否则上任意模数NTT #include<bits/stdc++.h> using namespace std; #define LL long long #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) #define endless() fclose(stdin),fclose(stdout) #de... Read More

手动模拟出奇迹 #include<bits/stdc++.h> using namespace std; inline int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();} while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();} return s*f; } const int N=1e6+3; char a[N],b[N]; int lena,lenb; int fail[N]; int main(){ scanf("%s%s... Read More

学这个是为了支持在带负权值的图上跑 Dijkstra. 为了这个我们要考虑把负的权值搞正。 那么先把我们先人已经得到的结论摆出来。我们考虑先用 SPFA 对着一个满足三角形不等式的图跑一次最短路，具体就是在原图的基础上建立超级源点。 然后我们把得到的这个东西称为 势能 $h$ ，我们对于原图的每条边 $(u,v)$的边权加上 $h_u-h_v$,然后就可以跑 Dijkstra 了，求出的答案是 $dis_{i,j}-h_i+h_j$.然后我们证明这样搞是对的。 首先需要证明这个搞法不会使求出来的值变化。 对于一条 $i$ 到 $j$ 的最短路径,有经过的点集 $S$ ,那么我们求出的最短路是： \[dis_{i,j}=(w(S_1,S_2)+h_1-h_2)+(w(S_2,... Read More

#include<bits/stdc++.h> using namespace std; #define N 2010 #define M 200010 #define INF 0x3f3f3f3f inline int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||'9'<ch) {if(ch=='-')f=-1;ch=getchar();} while('0'<=ch&&ch<='9') {s=s*10+ch-'0';ch=getchar();} return s*f; } int n,m,S,T; vector<int>head,to,nxt... Read More

建议全文背诵 3->2优化 #include<bits/stdc++.h> using namespace std; #define LL long long #define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout) #define endless() fclose(stdin),fclose(stdout) #define ReadOnly(a) freopen(#a,"r",stdin) inline int read(){ int s=0,f=1;char ch=getchar(); while(ch<'0'||'9'<ch) {if(ch=='-') f=... Read More

考模拟赛考到了线段树合并，于是学了树上启发式合并(?) 它相较于线段树合并的优点在于: 空间开销小 无线段树的常数 写法简单易理解 好那么开始进入正题。 首先说一下它的用途，可以用来解决一些子树问题。 具体的做法是先 dfs 预处理，然后像树剖那样剖出重儿子，可以剖出 dfs 序为之后加上一点常数优化（不需要优先遍历重儿子）。 然后我先给出核心函数的伪代码: void dfs(int u,int f,bool k){ for(int i=head[u];~i;i=nxt[i]){ if(to[i]==son[u]||to[i]==f) continue; dfs(to[i],u,0); } if(son[u]) dfs(son[u],u,1... Read More

最大流 #include<bits/stdc++.h> using namespace std; #define N 210 #define M 5010 #define INF 0x3f3f3f3f int n,m,S,T; vector<int>head,to,nxt,val; void join(int u,int v,int w) { nxt.push_back(head[u]); head[u]=to.size(); to.push_back(v); val.push_back(w); } int dep[N],cur[N]; queue<int>q; bool bfs(int s,int t) { memset(dep,0,si... Read More

冬令营突然发现的一个比较厉害的东西。 Dancing Links 用于解决覆盖性问题的利器。 两个不同分支，一个精准覆盖问题，一个可重复覆盖问题。 先讲相对基础的精准覆盖问题。 精确覆盖问题 就是说全集由多个集合恰好覆盖，各个集合间无交。 这个问题我们先考虑一个具体一些的问题。 我们用下面的那个 模板题 为例。是不是看到就想到爆搜。 确实是爆搜，我们考虑怎么优化这个搜索。我们发现如果我们把不可能的情况删掉，就可以减少冗余的操作，就可以做到优化。 具体就是删除含有了已经被加入了的集合。这样可以非常优秀地剪枝。然后回溯的时候再把删除掉的重新恢复即可。这几个过程我们都可以一个十字链表维护。 具体十字链表怎么维护？或者说十字链表是个什么东西？实际上就是一个链表，其节点保存... Read More

思想就是分治！ 然后就是每次二分区间，然后在分治统计左右区间之后，考虑统计跨越左右区间的数对。 给个模板题 陌上花开。 我们对于这个三维偏序问题，可以考虑CDQ分治。 先对于原序列按照a,b,c排序，这样保证a的单调增。 然后分治，对于每个小区间按照b,a,c排序，这样在右边区间的a大于左边区间的前提下，我们满足b单调增。我们枚举j区间选取的元素，然后取移动指针i保证i位置上的b小于j位置上的b，把i位置上的c加入树状数组。每个j在树状数组上统计一遍答案。这就是全过程。 但是本题有一个问题，它有相同的元素，分治的时候会统计少。 但是我们可以合并相同的元素，就可以了。 会CDQ分治了吗？上代码就懂了。 code: #include<bits/stdc++.h>... Read More

本质上大概是搜索优化。我们将bfs使用的队列改为优先队列，并使用结构体存储节点，重载 ‘<’ 小于号。 然后我们提高搜索效率的方法就是通过一个估价函数，评估当前情况与答案情况的差异，然后选取差异最小(或根据题目，并基于个人经验选取能够更快找到答案的情况) 由于优先队列存在复杂度，有时候估价函数写得不好反而会爆炸。所以谨慎选择即可。 例题: P2324 SCOI2005骑士精神 这里我们采用了 $A*$，估价函数的标准就是棋盘上每一位的差异和 #include<bits/stdc++.h> using namespace std; int ux,uy,wx[10]={1,1,-1,-1,2,2,-2,-2},wy[10]={2,-2,2,-2,1,-1,1,-... Read More

注：$A*$ 求解K短路效率极其低下，时间复杂度$O(nklog\ n)$,空间视题目而定，因为本质是爆搜，可求解数据范围较小的题目。 我们使用$A*$求解k短路: 首先需要预处理出估价函数。对于原图建立反向图，然后跑终点的单源最短路。用终点到这个点的距离作为$A*$的估价函数，可以完全保证搜索准确性。 然后我们跑$A*$。每次从优先队列里取出当前步数与估价函数之和最小的点并扩展其所有边。对于每个状态我们需要开一个标记数组（或者路径数组也可以），防止重复经过同一个点。 此时我们每次从优先队列取出的都是当前最短路径，当一个点第k次被取出时，这条路径就是k短路。 提供一道毒瘤例题P4467 SCOI2007k短路 这题似乎是公认的卡A(只卡了一个点，所以被用作$A$求k短路的模... Read More

#include<bits/stdc++.h> using namespace std; #define MAXN 1000010 #define LAXM 160 int n; char a[MAXN],s[LAXM][80]; int tr[MAXN][26],fail[MAXN],tot; int idx[MAXN],val[MAXN],cnt[LAXM]; void insert(char *s,int ls,int id) { int p=0; for(int i=1;i<=ls;++i) { int c=s[i]-'a'; if(!tr[p][c]) tr[p][c]=++tot; p=tr[p][c]; } idx[p]=id; ... Read More

同trie，只是维护的字符只有0和1 可以通过每次如果可以选择不同字符则选择不同字符的贪心思想维护最大异或和。多用于解决异或问题。 为什么上面那样操作可以维护最大异或和？因为我们按照从高位往底的顺序，如果当前答案这一位异或得1，其他答案的更高位都不超过当前答案的更高位，且其他答案这一位异或得0，那么当前答案必定是最大的。 举个例子:$3=(011)_2<4=(100)_2$ 代码实现: void ins(int num){ int p=0; for(int i=30;i>=0;--i){ int c=((num>>i)&1); if(!ch[p][c]) ch[p][c]=++tot; p=ch[p][c]; } } int ... Read More