Doraemon's Blog

扩展KMP 解决的问题： 求解母串以i位置开始的后缀子串与模式串的最大公共前缀 时复： O(母串长度+模式串长度) 引入两个概念，extend[]数组表示以母串i位置开始的后缀子串与模式串的最大公共前缀，next[]数组表示模式串以i位置开始的后缀子串与模式串的最大公共前缀，一个是模式串与母串，一个是模式串与模式串 与KMP类似，都采用了利用之前已经得到的信息来优化当前的时间 大致过程记一个po表示起始位置，求解extend数组需要先求出next数组，而求解next数组的过程和求extend过程一致，只不过是把模式串当作母串 (1) 第一步，我们先对原串S1和模式串S2进行逐一匹配，直到发生不配对的情况。我们可以看到，S1[0]=S2[0],S1[1]=S2[1],S1[2]=S2[2],S1[3] ≠S2[3],此时匹配失败，第一步结束，我们得到S1[0,2]=S2[0,2],即extend[0]=3; (2) Extend[0]的计算如第一步所示，那么extend[1]的计算是否也要从原串S1的1位置，模式串的0位置开始进行逐一匹配呢？扩展KMP优化的便是这个过程。从exten ...

树链剖分 求解问题：在树上进行区间修改区间查询问题，求lca问题，维护路径信息 主要思想：将树上的点分割成一条一条的链，每一条链的第一个点是链头(父亲)，利用dfs序按照链优先的思想加上序号，这样每一条链上面的序号都是连续的，就把树上的点映射到了一条数轴上 时复：找到父亲，重子节点，子树大小（dfs1）O(N)，进行一次dfs序(dfs2 O(N))，每一条路径都能被分割成最多log2n条链，因此链头数量不超过log2n，每次求lca时复logn 重链剖分 dfn数组: 每一个点映射到链上的标号 rnk数组: 每一个标号对应点的编号 (rnk[dfn[x]]=x) dep数组: 每一个节点的深度 fa数组: 节点父亲 siz数组: 子树大小 son数组: 重孩子 top数组: 节点在链上链头的编号 以上7个数组是树链剖分的几个必要数组，根据题目不同会使用上面的某几个数组 定义： 重子节点是子树节点最多的那棵树的根节点，如果有多个随意取出一个即可 剩下的非重子节点的点都是轻子节点 从当前节点到重子节点的边是重边 从当前节点到轻子节点的边是轻边 若干条首尾相连的重边称为重链，所有落单 ...

题目 题意从(1,1)出发走到(n,m)，途中有墙有门有钥匙，问最短几步走到右下角。 思路利用状态压缩，用二进制位表示第几种钥匙是否持有，利用BFS爆搜，再开一个数组储存状态来记忆化剪枝 实现方法有很多种，可以利用邻接表建边，可以直接利用Next数组表示下一个位置，邻接表利用空间换取了时间，表示墙和门时如果不用邻接表，则需要用map

题目 题意如图所示，旋转最少的电线使得左面的电源和发光器相连、 思路考虑把所有电线已经相连的点设为边权为0，没有连接的，比如电线是主对角线，副对角线上的两个点就应该设为边权为1，最后跑一个从左上角到右下角的最短路径，将每一个点映射到一维数组中。 dijstla当然可以做，但是双端队列更高，因为这个图中只有边权为0和1的点，可以把优先队列的log(n)省掉，当遇到边权为0的点时就把点直接添加到队头，遇到边权为1的点放到队尾，并且判断能否更新当前点离起点的距离。 CODE123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113#include <bits/stdc++.h>#de ...

题目 题意n个城市，从1到n点，有有向边，也有无向边，每个城市都有宝石价格，从一个点买一个宝石，再在后面走的点卖出，问最多赚多少钱？ 思路对每一个路径求一个前缀最小值和后缀最大值，对每一个点后缀减去前缀取最大值即是答案，细节就是，求后缀可以反建图，开一个rhead数组 CODE1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int MAXN=500000;const int INF=0x3f3f3f3f;struct node{ int to,next;}e[MAXN];queue<int> q;int head[MAXN],val[MAXN], ...

题目 题意给定t个点，r条道路，p条航线，和一个起点，道路可互相到达，航线只能单向到达，且航线的权值可能为负数，问从起点到各个点的最小距离是多少？若不可到达输出“NO PATH” 思路把所有道路相连的点组成联通块，给他们编上号，从起点所在的联通块往后跑一个拓扑排序，连通块内跑dijstla，松弛时发现松驰的点和当前点不在一个连通块内，则把更新的点所在的联通块入度-1，大致思路是这样，但是还是有许多细节问题 为什么一开始要加入入度为0的点？ 因为要保证拓扑序列的进行。假设s所在块编号为a，a连向块c，块b连向块c，且块a块b不相连。此时，如果你不加入入度为0的点，那么b块就不会访问到，c的入度也就不会减到0，也就不会访问到。 判断无解为什么不写出==inf？ 因为有坑1的存在。还是上面那个例子，再加2个条件： 块d->块b，块a与块d不相连。 d到b的路为负边权 此时显然应该块b、d里所有的点都是NOPATH，而且dis都为inf。但其实在用块d内的点更新块b时，会松弛成功，因为存在负边权。所以无解时不一定dis就为inf 对每一个连通块跑最短路时，不知道那个点作 ...

340. 通信线路分层图做法建k+1层图，相邻两层图之间权值为0，代表免费升级，在一层图里面跑就去找最大值，最后的答案就是第k+1层的dis[n]也就是dis[(k+1)*n]，注意的是这样的做法只有在边数大于k时成立，当全部边都可以免费升级时，会出现问题，还没有跑到最后一层图就到达终点了，这时就会往回跑，导致边权增加，就会出错，所以需要把层与层之间的终点连接起来，使它们可以免费互相到达 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include <bits/stdc++.h>#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)#define ios ios::sync_with_st ...

__int128C++支持的最大数据类型就是longlong，再大就会爆掉，所以出现了_int128类型，默认gcc是不支持编译的，但是在各大OJ上是可以运行的，\_int128不支持cin、cout，所以需要自己写读入打印函数，也就是传统的快读快写 1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; void read(__int128 &x){ int y=1;x=0; char c=getchar(); while(c<'0' || c>'9'){ if(c=='-') y=-1; c=getchar(); } while(c>='0' && c<='9'){ x= ...

Early Orders 题意n个数从中找出一个包含1-k的字典序最小子串，注意子串可以断开，但是相对顺序不能变 题解求得是字典序最小的子串，用一个单调栈维护，从栈底到栈顶依次表示子串的从前到后，为什么用栈呢？考虑子串的先后性，必须先把后面的更新了才能更新前面的，如何维护栈呢？对于栈顶元素，从左往右遍历的过程中如果这个数字比栈顶数字小，而且右面还有栈顶数字，那就可以出栈，还有就是当栈内有一个元素了，这时就不能再往里面塞这个元素，搞一个标记数组标记栈中是否有这个元素 CODE123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) using namespace std;const int MAXN=1e6;stack<int> st;bool vis[MAXN];int ans[MAXN],a[MAXN],pos[MAXN];int mai ...

B 比武招亲（上） 题目大意给定n,m，每次从1-n中挑选出m个数，可以重复挑选，挑选出的数的贡献值等于排序后最大值减去最小值，挑选的序列不同当且仅当两个序列排序后不同，求所有可能的序列的总贡献值？ 解法可以枚举贡献值，差值一共有n-1种，差值固定了，也就是在m-2个空位中随意放置[min,max]的数，这里有一个坑，也不是随便放的，因为要求排过序后序列不同，也就是放置要求是单调不减，于是可以把+1看成一个隔板，就是在m-2+1个隔板中放置d(差值)个隔板，可是隔板可以连续放置，所以放置一个隔板后空位就会增多！所以答案不是C(m-1,d)，雨巨的想法NB，考虑每一个隔板的左面带有一个空位，那么所有的隔板放完后空位就增加到了m-1+d个，在这些空位中放进去d个隔板，这个时候隔板就不能连续放了，因为每一个隔板左面都带有一个空位，所以每一个隔板左面都必须至少有一个空位，那最左面也不能放了，所以空位变成了m-1+d-1，答案就变成了从m-2+d个空位中放置d个隔板，隔板不能连续放，C(m-2+d,d)，到这里题目就做出来一大半了，组合数复杂度为O(n)，这里的n和m都是1e5，所以每次都算一遍 ...