- 博客(168)
- 收藏
- 关注
RSS订阅原创 virtual studio + cplex 初体验 求解01背包问题
这里写自定义目录标题环境解决问题环境Virtual Studio 2017 + cplex 12.8.0.0解决问题初次体验，解决一下最简单的MIP问题这个数量级用dp也是很快的，哈哈 用着玩玩#include <ilcplex/ilocplex.h>ILOSTLBEGINint main(int argc, char** argv){ int val[1001], vol[1001],N,V; cin >> N >> V; for (int i
2022-04-02 22:08:58
371
原创 子序列dp问题
问题：给出一个长度为n(1≤n≤106)n \quad(1 \leq n \leq 10^{6})n(1≤n≤106)的字符串，你需要求出该字符串有多少个不同的子序列。子序列的问题乍一看和字串的问题很相似，可能要用到后缀数组等高级数据结构。仔细想想其实没有必要的，一个O(n)O(n)O(n)的dpdpdp就可以解决。对于给出的字符串A[1],A[2],...A[n]A[1],A[2],...A[n]A[1],A[2],...A[n]，我们用dp[i]dp[i]dp[i]表示以字符A[i]A[i]A[.
2021-08-28 15:07:06
200
原创 模拟退火入门
一只退役老狗了，目前现在夏令营零offer，也没什么事情干，就来学学一些学术界常见的算法，为读研做准备吧，毕竟竞赛和学术的算法还是有很大区别。ps：打比赛的时候实在不会也能水一水模拟退火（俗称炼丹） 当然 走上这一步了就不要在意罚时了，懂得都懂。模拟退火是最常见的随机搜索算法，首先我们看百度百科对它的定义：模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后
2021-06-30 16:47:07
256
原创 关于windows10不能更换默认浏览器的问题
今天想换默认浏览器，发现打开windows10设置默认浏览器的时候，选完就会闪退。找了半天都没发现原因，最终发现是管家的问题。如果你有相同的问题的话，可以查看自己的电脑管家。例如我的：锁定了以后根本无法更改，解锁或者是直接用管家设置就行了...
2021-06-28 20:21:53
473
原创 1398E Two Types of Spells 权值线段树
假设目前有x个火魔法 y个星魔法 显然 y个星魔法让y个权值最大的魔法翻倍就行但是 有一个情况就是 y个星魔法就是前y大的魔法 这时候 肯定有一个y魔法不能翻倍 根据贪心 我们要去掉最小的y魔法 假如最大的x魔法用权值线段树维护上述操作即可 #include<bits/stdc++.h>using namespace std;const int N = 2e5+100;typedef long long ll;struct node{ int op,d...
2020-08-15 20:27:06
130
原创 类欧几里得板子
一下为三个基本的可用类欧几里得求解的式子其中（结论来自Great_Influence大佬的博客）采用递归的形式实现就可以了 如果是更一般的形式如 使用万能欧几里得会更方便（待补）...
2020-08-12 17:27:09
102
原创 整除分块的模板
整除分块 用来求 可以在的复杂度内完成大佬的证明 简单明了：整除分块证明#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ ll ans=0,n; scanf("%lld",&n); for(ll L = 1,R; L <= n; L=R+1){ R = n/(n/L); ans+=(R-L+1)*(n/L); } prin...
2020-08-02 18:29:42
129
原创 牛客多校4 A Ancient Distance 线段树+dfs序
思路源于某巨佬：巨佬博客对于 1<=k<=n 答案最大是n-1 最小是0 于是我们从大到小枚举答案（这样的话小的值会覆盖大的值） 然后看这个答案对应的最小k是多少 最后在做一遍前缀最小值就行了找ans对应最小k的过程肯定是贪心的 我们找到深度最大的点 向上走ans步（找ans级祖先） 然后把它的子树都标记就可以了当最大的深度<=nowans时 退出循环当ans 确定的时候 最多进行 n/(ans+1) 次操作 每次操作复杂度是 logn级别的所以 总...
2020-08-02 17:45:59
110
原创 牛客多校 Interval 主席树套路
题意就不说了这样的题乍一看感觉区间& 会有n^2级别个不同的数 其实仔细分析是没有那么多的我们考虑维护一个map 这个map记录了当前位置以前的数&起来后可以得到的值以及他们的位置 （是连续的 可以理解为后缀&） 那么我们加入当前位置的数 并且与map中的值进行&操作（这一步我们最多得到logn个值）然后就是一个主席树的套路了 对于在前面出现过的值 我们把它的位置-1 并且在当前位置+1 然后更新这个值的位置为当前位置 这个题可以算是区...
2020-08-01 10:34:47
154
原创 CF 678F Lena and Queries 线段树维护凸包+三分
题意：维护一个点集 向点集中进行插入删除和查询的操作 其中查询操作是 求 q*x+y的最大值设 z=q*x+y 得到y=-q*x+z 显然我们需要使得截距z最大 我们需要维护一个凸包 然后在通过三分在凸包上找到最大值不过显然我们不能每次询问都去求一个凸包 那样复杂度是无法接受的我们可以维护每个点出现的时间 然后把它挂在线段树上面 最后在遍历一遍线段树就行了 （类似于线段树分治的思想）#include<bits/stdc++.h>using na...
2020-07-31 20:41:05
216
原创 HDU Tokitsukaze and Colorful Tree 离线+树状数组
因为是求异或值 显然我们需要将val进行二进制拆分 每一位单独去看 由求和式子我们知道 计算点对(u,v)的贡献时 v不能在u的子树中 v不能在 u到根结点的路径上由于修改都是单点修改 我们可以用树状数组进行差分操作具体的算法步骤就是：对于每一个颜色 我们枚举20位按照操作 顺序 我们将初始值视为一次加操作 将一次修改操作视为一次减操作和一次加操作计算将要修改的点的每一位的贡献 （用总的减去在子树中的 再减去在根结点到当前点的路径上的 即为满足条件的）然...
2020-07-31 18:31:20
144
原创 HDU 6798 Triangle Collision 镜像原理+坐标轴旋转
这道题比较考思维吧 首先 在三角形内部的反射 去求反射角比较麻烦 时间上也不允许 我们要利用反射的原理 把这个平面衍生成一个由正三角形 镶嵌构成的平面 那第k次碰撞就是 由这个球的坐标 及其速度 构成的射线 与平面内等边三角形的第k次相交 其他博客图很多 可以去看看然后 我们二分一个时间 看这个时间 与整个平面有几个交点首先看 和x轴平行的线 容易得出 交点个数为 floor的意思是 取小于等于当前小数的最大整数另外两种 我们可以将坐标点 分别绕 等边三角形的中...
2020-07-29 19:49:39
242
原创 牛客多校 B Graph 分治+trie求完全图的生成树
这题是51nod上一个题目稍微变形了一下：完全图最小生成树原题是 对于一个完全图 每条边（u,v）的边权都是 a[u]^a[v] 求一个最小生成树但是如果暴力去做的话 肯定会爆时间 n=1e5 边数就是n的平方级别的 我们需要去优化建立生成树的过程 有一个明显的想法是 从最高位开始 我们把当前位为0的分成一块 为1的分成一块 那么肯定是所有为1的在一个联通块内 所有为0的在一个联通块内 因为这样的话 为1的联通块的边权会尽量小 为0的联通块也是那...
2020-07-27 08:58:33
169
原创 HDU 2020多校 6756 Finding a MEX 简单树分块
我主要是按题解思路写的我们发现修改和询问两个操作都和点的度直接相关，直接修改或者询问的话复杂度无法保证（菊花图 度接近n） 那我们得想办法进行一个分类讨论我们设置大点和小点。设置一个临界值为sqn 其值为根号n如果一个点的度大于等于根号n 那么我们把它分为大点否则我们把它分为小点首先我们用树状数组维护mex（对每个点开一个树状数组） 并且 将所有的点和与它相连的大点构成另外一个大点图 （在这个图中 对于点u来说 和它相连的都是大点）对于修改操作 如果当前点是小点 我们...
2020-07-25 10:52:34
136
原创 P3792 由乃与大母神原型和偶像崇拜 双hash+线段树
想要知道区间内的数是不是连续的一段 显然我们需要一个hash函数来确定 其实应该很好想 我们先找出这个区间内的最大值和最小值 如果是连续的一段的话 那么肯定是从最小值到最大值这样连续的一段 那么我们首先维护区间最大最小值 其次维护区间和 这算是一个hash 但这还远远不够 因为区间和相同的时候 还有很多情况 那我们再维护一个区间平方和 如果区间平方和和区间和都和对应得最小值和最大值算出来得相等得话 那么就是连续得一段 区间和公式 很简单区间平方和公式 要用立...
2020-07-19 11:39:05
97
原创 P6136 【模板】普通平衡树（数据加强版） FHQ 平衡树模板
大概确定了一下 以后就写fhq吧 splay也就lct里面用用 主要是fhq好写啊 而且也能可持久化 能旋转 啥都能干写个板子 de了我半天#include<bits/stdc++.h>using namespace std;const int N = 1e6+1e5+10;#define R register int#define I inline void#define lc(x) c[x][0]#define rc(x) c[x][1]int r...
2020-07-17 20:58:05
148
原创 牛客多校训1 B Infinite Tree 虚树+数论+树状数组
第一场真的怀疑人生 做题做不动 补题补不动 还有叉姐的一句话题解 （看不懂啊呜呜呜） 然后我左翻右翻 终于找到了这题的题解 博主讲的非常详细 ：Infinite Tree知道有虚树这个东西 但是还没看过 虚树的建树过程大概就是 先把所有需要的点拿出来（也有博客说这是叫啥 议事点） 显然这题我们需要的点 就是 1!,2!,3!,,,,,,,n! 这n个点 然后把他们按dfs序排序 所幸 这题按照1~n的顺序就是 dfs序排序的 我们找出每个点前面那个点的lca 最后...
2020-07-17 17:36:46
181
原创 CF1156D 0-1-Tree 换根dp or 并查集
这题好像做法挺多的 还有个并查集的方法也非常好理解 可以看博客：CF1156D 0-1-Tree我的做法是换根dp 由题目可知 路径是有向的 也就是说 如果 u->v满足条件 且v->u满足条件 那么我们都要算进去 那我们先算以1为出发点 可以得到的答案数 然后再进行换根 把这些答案都加起来就是最终答案了 考虑以u为出发点 dp[u][0] 表示与子节点连边为0的方案数 dp[u][1]同理那么状态转移就是 我们用这个式子算出以1为出发点的...
2020-07-17 16:43:31
153
原创 P5385 [Cnoi2019]须臾幻境 LCT+主席树 维护区间联通块个数
题意很简单：给n个条边 m条边 每一次给一个询问 l，r 问区间l~r的边构成的图的联通块个数因为是不断加边 所以我们的lct肯定是维护边的 然后我们思考边和联通块的关系 一开始整个图是n个孤立的点 联通块的数目为n 当我们加入第一条边的时候 联通块数目-1 规律大概是 联通块数=n-边数 但是在构成环的时候就不成立了 例如 图中有 u，v 这样的一条链 u~v的点都是属于一个联通块 那么我如果加入一条边 使得u连上v 那么对联通块的减少是没有贡...
2020-07-16 09:47:13
380
原创 牛客多校2 Happy Triangle FHQ-treap 维护前驱差
题目还是不错的 需要仔细分析一下题意：给一个可重复集合，最初为空。每次操作为 op，x如果op==1，向集合中插入x如果op==2，删除集合中的x（保证x一定在集合中）如果op==3，询问集合中是否存在两个数a，b使得a，b，x可以构成三角形我们分析一下a，b，x的关系如果 a<b<=x 根据三角形的构成条件 必须满足 a+b>x如果 a<=x<=b 则必须满足 a+x>b 那么肯定是 a是x前驱 b是x的后继的时候最好如...
2020-07-16 08:06:34
136
原创 牛客多校2 Fake Maxpooling
单调栈的模板题吧 没啥好讲的 被卡了一点空间 去掉了一个数组就过了参考洛谷理想的正方形#include <bits/stdc++.h>using namespace std;const int N = 5002;int n,m,k,FRONT,BACK;int Q[N];int X[N][N];int a[N][N];typedef long long ll;int main(){ scanf("%d%d%d",&n,&m,&k); ...
2020-07-15 18:23:00
105
原创 P2839 [国家集训队]middle 主席树+求中位数技巧
首先做这个题 我们要用到一个常用的技巧 二分求中位数具体步骤就是 先二分一个值 在数组中把大于等于这个值的数都设为1 把小于这个值的数都设为-1如果数组和>=0 那么 l=mid+1否则的话 r=mid-1那么我们如何快速的进行这个操作呢 假如一个询问是 a,b,c,d a<b<c<d 并且对于 区间a~d我们都进行了上述的赋值操作那么 b+1~c-1之间的值是肯定要算进去的 然后我们需要在 a~b区间内找个最大后缀和...
2020-07-15 17:25:36
166
原创 P4301 [CQOI2013] 新Nim游戏 线性基+贪心
由nim游戏可知先手想要获胜得在后手第一次取完后各石子数异或不为0 也就是说在先手第一次取完后得到的线性基 是异或不出0的（否则后手将剩余的取完 就可以异或出0 然后先手就进入必败态）根据线性基的性质 我们可以把a数组从大到小排序 然后按顺序插入线性基 如果一个数无法插入线性基 那么就说明可以异或出0了 我们要把这个数取掉 为什么是从大到小呢我们看 10 9 3 这三个数 他们异或为0 如果我们从大到小插入的话 最后先手取得的最小石子数就是3 这有点猜...
2020-07-13 08:41:59
94
原创 P2173 [ZJOI2012]网络 维护多个LCT
一开始对题意的理解有些问题 2条件显然限制了从(u,v)的颜色为c的路径只能有一条 因为颜色数很少 只有10 于是我们想到一个很暴力的方法 就是 维护c颗LCT 分别对应c种颜色 然后进行对应的操作就行了#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;#define lc c[x][0]#define rc c[x][1]#define R register int #defi...
2020-07-12 20:01:51
104
原创 P4175 [CTSC2008]网络管理 整体二分+树链剖分
将整体二分移到了树上 那么在二分的时候 比较mid的过程 肯定是要用树链剖分+线段树（听说差分+树状数组也能做）来维护大于mid的个数的 然后就是一个整体二分的套路了 修改的时候就是将赋值操作拆分成两个操作 一个把原来的值-1 另一个把新加入的值+1另外对于没有解的情况我预处理了一下 求了一个lca(x,y) 然后算 x和y之间有几个点 如果小于k就没有 答案 都是比较直接的做法 但是能写出来离散化了一下值域 保守估计复杂度 nlogn^3#includ...
2020-07-12 19:49:55
88
原创 P1527 [国家集训队]矩阵乘法 整体二分求二维第k小
#include<bits/stdc++.h>using namespace std;const int N = 503;int c[N][N],n,w;const int M = 4e5+100;int ans[M]; inline int in(){ int x=0;char c=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<1)+(x&l.
2020-07-12 19:40:13
114
原创 区间第k小及其变形（整体二分法） 模板
作为不想写树套树和主席树的懒人 整体二分是个较好的方法 不过它的致命缺陷是必须离线#include<bits/stdc++.h>using namespace std;const int inf = 1e9;const int N = 4e5+10;struct node{ int l,r,k,id,op;}q[N],rq[N],lq[N];int n,m,c[N],ans[N];void add(int x,int val){ while(x<=n){ ...
2020-07-11 10:25:28
197
原创 P4230 连环病原体 LCT+双指针
双指针确实是个好东西 不能说是一种明确的算法 但是是很重要的思想 比如有名的尺取法 也是一种双指针的思想 双指针一般是利用单调性 来大幅度减少枚举的复杂度 这里就不深入了对于 加强区间 我们枚举左端点L 然后看右端点R 一个显然易见的性质是 如果 [L,R] 是加强区间 那么 [L,R] ,[L,R+1],[L,R+2],,,,,[L,m] 都是加强区间 因此对于每一个左端点L 我们枚举R 如果L，R 是加强区间 那么就有 m-R+1个加强区间 （统计数目会用到前...
2020-07-11 08:56:07
177
原创 HDU 6305 笛卡尔树+求期望
首先这个题要分析不少东西：B数组是取0~1内的实数 任意两个元素相等的概率为0 所以我们可以认为 B数组的每个元素都不相等 可以看作全排列 对于合法序列B 其元素的期望值为1/2 (0~1上的均匀分布) 所以序列的期望值为 n/2 A和B满足题目条件 当且仅当 A和B的笛卡尔树同构 而全排列总共有种 其中满足同构的有 所以同构的概率为 综上所述 最终的答案为#include<bits/stdc++.h>using namespace std...
2020-07-10 21:03:53
321
原创 笛卡尔树模板
温馨提示： 这是大根堆的笛卡尔树struct DCR{ int ls[N],rs[N],st[N],num,rt; void init(){ for(int i = 1; i <= num; i++) ls[i]=rs[i]=0; } void build(){ int z=0; for(int i = 1; i <= num; i++){ while(z&&a[i]>a[st[z]]) ls[i]=st[z--]; if(z).
2020-07-10 20:27:48
141
原创 Ascending Rating HDU - 6319 单调队列
这题把题目一读完就有滑动窗口那味了 当时就想这绝*是单调队列 但是想了好久 不知道怎么维护cnt 后来队友给了个反正来的思路 我发现确实可以先把n个数求出来 然后从后往前 维护一个单调递减的单调队列 当我们遍历的个数>=m时 单调队列的元素个数就是 cnt 队首就是mx 有点卡时间 最好加个快读#include<bits/stdc++.h>using namespace std;const int N = 1e7+10;typedef long lo...
2020-07-10 09:55:59
121
原创 SP10707 COT2 - Count on a tree II 莫队+欧拉序
因为本题支持 离线 所以可以用莫队的算法 常见的套路就是把树变成一个序列 而要解决这个题 我们需要使用欧拉序 （感觉更像是括号序列）从何俞均大佬手中偷来了一个图这棵树的欧拉序是： 1 2 4 5 5 4 2 3 6 6 7 7 3 1 （一个点第一次出现 视为进入的位置st 第二次出现视为离开的位置ed）设 u,v是我们要查询的路径 假设 u的遍历顺序（在欧拉序中进入的位置）小于v如果 u=lca(u,v) 那么 我们选择的遍历序列是 st[u],st[...
2020-07-10 09:07:37
152
原创 P1600 天天爱跑步 线段树合并+lca
天天爱跑步有点毒瘤的题目 我们观察一下性质 在路径 u,v 上 如果这个路径 对某个点j 有贡献j肯定得在路径 u,v上 也就是说 如果当前遍历的点在 lca(u,v)上方的话 那么 u,v路径是肯定没有贡献的 因此到达lca时我们要把贡献去掉在说怎么算贡献 设u为起始点 v为终止点如果u对于j有贡献 有 如果v对于j有贡献 则设u,v路径的时间为 t 有又 化简可得然后需要注意的几点：1.当我们遍历的点为lca(u...
2020-07-09 09:00:04
156
原创 HDU 6315 G Naive Operations 线段树
这题看题面就知道是线段树了，但是我们发现这个式子并不是很好维护，那么我们可以换一个思路，对于每个add操作，我们把B序列的对应区间-1，当B序列中某个位置上为0的时候，这个位置的答案就+1 并且把这个值又变回到Bi 这个很好理解 所以我们要维护区间的最小值来看-1后以后会不会有位置变成0 对于会变成0的位置我们需要单点更新 有些人可能觉得 如果有多个位置同时为1的话 复杂度会很高 其实...
2020-07-09 08:45:47
103
原创 P1712 [NOI2016]区间 尺取法 +线段树
我们需要枚举区间 看是否有一个点被覆盖m次 暴力的枚举肯定是不行的 那么可以采用尺取法首先根据长度对n个区间进行升序排序 假设当前枚举的为 标号L~R的区间 我们用线段树维护最大值 看是否有一个位置被覆盖了m次 如果有 更新答案 接着我们压缩L~R区间 （因为我们要最小值 当L越大 差值越小）也就是在 有一个位置被覆盖次数>=m时让L最大 更新完这个答案后 在向后扩展R就行了尺取法的一般步骤是：1.初始时 L=R=02.R向右扩展知道满足条件 3.在第二...
2020-07-08 13:33:08
95
原创 CodeForces - 587E 和 无力回天NOI2017 线性基套路+线段树
这两个题十分相似 就放在一起讲了 它们的操作1都相同1 l r x 将区间l到r的数都异或x 这个操作似乎可以线段树区间修改 不过 2操作明显涉及到线性基 如果进行区间修改的话 线性基如何处理在这要用到线性基的一个套路当我们说两个线性基相同的时候 当且仅当它们可以异或出来的数相同 我们先对数组做一个异或差分 那么1操作就变成了l和r+1两处的单点修改 那2操作如何实现 我们观察一下 到这 r-l 个数 是不是可以将到...
2020-07-08 08:59:21
332
原创 HDU - 6609 权值线段树
HDU - 6609给一个序列 a 对于每个i 询问最少删除几个数ai(i<ai) 能使得i位置的前缀和小于等于m表述可能不清楚 大家可以自己看题我们将题意转换一下 最少需要删几个数 那这几个数肯定是越大越好 并且 这几个数的和(其中sumi是i位置的前缀和) 那我们先把ai离散化了 然后遍历一次ai数组 每次向权值线段树中插入ai（当然是插入在ai离散化后排名的位置） 分别记录cnt和sum cnt是每个数出现的次数 sum是求和 然后我们在线段树中搜索 如...
2020-07-07 15:19:29
125
原创 HDU - 6610 Nim博弈+带修莫队
可以看出来两人的游戏是nim博弈 所以如果区间内的数异或和不为0 那么Alice 必胜简单分析一下我们肯定要做一个前缀异或 然后再莫队就行 因为Bob会对序列进行修改 所以我们需要用带修莫队 然后就变成一个板子题目了带修莫队 在块大小为 n^(2/3) 理论上复杂度最优#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N ...
2020-07-04 11:23:38
275
原创 博弈论题目集 （持续更新）
巴什博弈HDU 1846这个应该比较好推：如果 n % (m+1)==0 后手胜利 否则 先手胜利#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int main(){ int t; scanf("%d",&t); while(t--){ int n,m; scanf("%d%d",&n,&m); if(n...
2020-06-29 20:24:22
2955
原创 舞蹈链 模板
精确覆盖#include<bits/stdc++.h>using namespace std;const int N = 260000;inline int in(){ int x=0;char c=0; while(c<'0'||c>'9') c=getchar(); while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x; .
2020-06-28 21:55:48
254
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人