xia0ji233's blog

还是很开心的，第一次CF打出来D题，嘎嘎上132分，目前1584分，紫名指日可待。 A.Red Versus Blue题目描述： 题目分析知道双方赢球场次，要求构造一个输赢序列使得总比赛中最大连赢场数最小，即给定两种字符及个数，输出一个字符串使得由相同字符构成的子串最短。 首先题目给定了B的数目严格小于R，那么最优的情况一定是一输一赢，考虑在 b 个 B 中插入R，容易得到总共有 b+1 个可以插入的位置。若 r 可以整除 b+1，则可以得出答案为 r/(b+1)，若否，则得到 r/(b+1)+1。 我们先在b+1个位置中每个放上 r/(b+1) 个 R，剩下r%(b+1)个R则随便给，只要不要一个位置给两次就可以了。 标程12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;void solve(){ int n,r,b; cin>>n>& ...

今天来深度解析一下RSA加密 引言还是最朴素的例子，Alice和Bob要在不安全的路线上发送信息，整条线路完全被窃听者Eve所知，如何让Alice和Bob安全地通信呢？如果这个例子略难懂，那换一个来讲，我要给别人寄个快递，我怎样让别人不知道我寄的是什么，一般情况下，如果没什么特殊情况，快递是不会被随便拆开查看的，但是也很难说，如果我给我实际要送的东西上把锁，那么即使我送的快递被拆开，没有钥匙也不会有人知道我送的是啥，而钥匙只有收件人拥有。 这就是非对称加密的一个例子了，一个人只有锁，另一个人有钥匙，可以这么说，当把锁关上的那一刻，寄件人都没办法打开去检查他寄的是啥，如果这个锁足够强大的话。 RSA加密rsa主要是利用一系列的数学公式，让推导难以逆向分析，常见的有右移运算或者取模运算，RSA主要是使用取模运算。首先，我选择一个指数(e)，让明文(m)进行这么多次的幂运算，再模上一个数(N)，这也就得到了密文(c)，这个密文难以逆向得到明文，因为取模运算不可逆，这个e和N是公开的，所有人都可以加密，也就是锁，但是钥匙只有自己拥有。 这里也先给出加密和解密的公式： 在这里d由一个 ...

本篇博客只有板子。 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$ 个收费站有一个源收费站一个目的收费站，问最多有多少辆车能从源收费站到目的收费站，总费用最小的通行方案是多少。 解题步骤乍一听好像没啥思路，但是从一个司机的角度去考虑，这就会变得简单了，因为对于一个司机来说，我的目标是到达目的收费站且使我花费最少。那么起点终点确定了，每条路收费确定了，收费站之间的道路也确定了，那么我以收费为边权计算我到终点的单源最短路不就可以了么，走单源最短路一定会使得我的花费最少，因为边权是费用，最短在某种意义上就是费用最少啦。 但是我们是不可能为每一个司 ...