xia0ji233's blog

本篇博客只有板子。 sa[i]：排名为i的后缀的下标 rak[i]：后缀suff[i]的排名 Height[i]：后缀按照字典排序之后，该后缀与上一个后缀的最长公共前缀，也就是排名为i的后缀字符串和排名为i-1的后缀字符串的最长公共前缀。 DA算法(O(nlogn))12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=100010;int wa[N],wb[N],wv[N],wss[N],rak[N],height[N],cal[N],n,sa[N];char s[N];int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}void ...

主席树应用之一：区间第k大，中间还有用到vector离散化 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<iostream>#include<cstdio>#include<algorithm>#include<vector>using namespace std;const int maxn=2e5+10;vector<int>v;typedef struct A{ int l,r,sum; //l为一个离散化变量的左边界，r为右边界，都是对于值域而言的，sum存储数值在[l,r]区间内的数的个数 }node;node tree[maxn*20];inline int getid(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin()+1; ...

洛谷的板子 题目1 标程123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126#include<iostream>#include<queue>#define maxn 1000001using namespace std;bool b[maxn];string word,s;int ans=0;typedef struct A{ A *fail; A *next[26]; int word; int num; void a(){ ...

一道小思维题 题目描述 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106#include<bits/stdc++.h>#define maxn 6000using namespace std;struct eee{ int to; int w; int next; }e[maxn*3000];int root[maxn],cnt=1,dep[maxn];int n,m,q,x,y;queue<int>que; int rd() { int x = 0, w = 1; char ch = 0; while (ch <  ...

最近需要下载钉钉的录屏回放，但是管理员禁止了下载，找到了众多的方法都不得行，后面自己开辟了一个方法（我也不敢确定是不是没有人用这个方法，反正这个方法不是通过搜索得到的。。 先说说我通过搜索资源得到了些什么方法吧，其实大多数就指向一种方法——通过fd抓包找到m3u8的下载地址，然而我在用fd抓包的时候并没有找到m3u8的下载地址，也有说用旧版本的钉钉的，但是我发现根本扫不上去，于是我仔细观察fd得到的包，发现播放视频的时候大部分出现了 .TS文件格式的url请求。 可以看到每过一会就会请求一个对应的 ts 文件，我也去搜了一下 ts 文件的含义，差不多就是视频的切片。因此如果我能得到所有的ts的下载地址，那么我就相当于得到了这个视频。 但是在请求这个 ts 文件的时候必须加上一个 auth_key 参数，然后这个参数貌似也是个随机的散列值，目前信息有限没办法计算出这个散列值的排布规律，但是我能得到一个最朴素的做法：暴力得到所有的 ts 的url，然后一个一个下载，最后用 ffmpeg 去合并就好了。 然而这里我们并不需要看完所有的视频，我们可以快进，我理解的原理是这样的：假如把你 ...

一道思维好题，写篇题解纪念一下。 Problem Description有 $n$ 个敌人，你需要在第 $k_i$ 秒用至少 $h_i$ 的攻击力打败这个敌人。 攻击力的计算方式如下： 第一秒时，你有 $1$ 攻击力 对于后面的任意一秒，若前一秒你的攻击力为 $x$，则这一秒你的攻击力可以为 $x+1$ 或 $1$ 一秒内，如果你的攻击力为 $x$，则你就需要消耗 $x$ 的能量。 请问，在你打败所有敌人的情况下，最少需要消耗多少能量。 题目分析在一秒内，你可以继承之前的攻击力，但是继承攻击力的代价就是你要花费相当于继承之后攻击力的法力值来保存你的攻击力。只有当前攻击力大于当前出现的怪物的血量的时候，你才能杀死他。在任意一秒，你可以选择摆烂，但是摆烂的代价就是会丢失上一秒的攻击力，使你在下一秒的时候无法有之前那么高的攻击，摆烂可以选择从 $0$ 开始或者从 $1$ 开始。显然可以发现，当 $k_i\ge h_i$ 的时候，主角总是有办法杀死所有的怪物的。 在杀死所有的怪物的怪物下要保证消耗的法力值最少，那就需要我们合理分配增加攻击的时间了。我们不难得出以下结论： 如果在第 $ ...

比赛遇到了新鲜的图论题，特此记录。 什么是Kruskal重构树？ $\text{Kruskal}$ 重构树，和 $\text{Kruskal}$ 算法的思想差不多，就是在这个过程中建出一个有着非常优秀的性质的数据结构，这是一个非常少见和小众的算法，但是如果碰到了合适的题目，就会体现出其优越性。 如何实现？既然它叫 $\text{Kruskal}$ 重构树，那么它必然与 $\text{Kruskal}$ 有着密不可分的联系。首先我们回顾一下 $\text{Kruskal}$ 最小生成树是怎么实现的，先将所有边按照权值排序，然后再从小到大添加边，如果添加边的两个顶点都在生成树当中则跳过这条边，直到添加过n-1次算法结束。 我们在添加边的时候构造一棵这样的树：当边e被添加时，e的两顶点一定在不同的生成树内，因此将两个顶点所在的树用一个点连接起来，点的权值为这条边的权值，这个点的权值表示了什么呢？就是这两个子树上，其中一个子树所有的顶点到另一个子树的所有顶点中经过的边的最大值的最小值为这条边的边权。 首先先解释一下什么叫最大值的最小值，这句话可能有点抽象，那我具体举一个例子。我一个节点从 ...

时隔多日，又一模板收入其中：最小费用最大流。 概念引入 费用：对每条有向边新增的一个属性，费用表示每个经过这条边的一个单位流量将会添加这么多费用。 将抽象的问题具象化：在一张高速网中有 $n$ 个收费站，$m$ 条单向通行的道路，每走完一条道路就会到那边的收费站收费，收费价格会根据你走的哪条路收费，而不是固定的收费点就收固定的钱，这个也很合逻辑吧。然后一条道路最多同行 $w$ 辆车，也就是说这条路一旦走过超过 $w$ 辆车那这条路将不再放行，虽然不符合我们的认知但是他就这么规定了你也没办法嘛对吧。在 $n$ 个收费站有一个源收费站一个目的收费站，问最多有多少辆车能从源收费站到目的收费站，总费用最小的通行方案是多少。 解题步骤乍一听好像没啥思路，但是从一个司机的角度去考虑，这就会变得简单了，因为对于一个司机来说，我的目标是到达目的收费站且使我花费最少。那么起点终点确定了，每条路收费确定了，收费站之间的道路也确定了，那么我以收费为边权计算我到终点的单源最短路不就可以了么，走单源最短路一定会使得我的花费最少，因为边权是费用，最短在某种意义上就是费用最少啦。 但是我们是不可能为每一个司 ...

最近花点时间看了看网络流，也深度地学习了一下网络流的各个算法，虽然还有一个没学，但是不影响。 概念引入首先我们要先理解一下什么是网络，网络与有向图虽然长得一模一样，但是概念略微不一样，首先网络的边权不代表路径长度，代表流量或者花费。 源点：入读为0的点，只出不进 汇点：出度为0的点，只进不出 在网络中，对于非源点和汇点的所有点，需要满足流入流量之和等于流出流量之和，中间节点不存储任何流量，任何一条边的流量受限于自己的容量限制。 于是有的人就想要求出：这张网络运作起来的时候，总流量最大能有多少。由于容量限制比较复杂，似乎不容易规划一个最佳方案。 such as: 在这里，很容易得出 $s\to t$ 的最大流量就是2，上面一条路，下面一条路，边上的限制都是1，因此总流量为2。这里我们再给出两个概念： 增广 :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差) 增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?) 因此我们有了第一个算法：FF。 虽然一般来说基本通不过测试点，但是还是有必要学的 ...

最近复习一下线段树的板子。 线段树就随便写吧，就写给自己看看的，因为即便是我学过板子，也基本会交错很多次。首先一个就是一定在开头加上一句话： 1#define int long long 然后就是push_down的操作，一定是有标记的时候已经加完了，push_down的时候就是把标记分发下去然后给子节点加上值和lazy标记。 在add操作的时候一定要加上先push_down再加。 线段树解决问题的范围要求在线，并且含有区间加法和区间查询的操作，下面是洛谷的板子题并给出标程，也可以当板子用。 板子123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include<bits/stdc++.h>#define int long long#def ...