- 博客(199)
- 收藏
- 关注
RSS订阅
原创 C#学习
参考书籍：《C#入门经典(第七版)》 (美)Christian Nagel Bill Evjen 等著观前提示：内容并不专业，写文自娱自乐。请擦亮你的狗眼观看因为我自己都不知道哪里是写错的。Part 1 你看不懂概念的样子像个文盲.NET微软的操作平台，功能...大概是进行操作.NET frameworkfram...
2020-01-03 13:38:29
163
1
原创 板子合集，持续更新中...
树上倍增求LCAconst int N = 1e5+5;int lca[N][20];int dep[N];void dfs(int now,int f,int depth){///初始时dfs(根节点,0,1); lca[now][0] = f; dep[now] = depth; for (int i=head[now];i!=0;i=edge[i].las...
2019-07-17 10:06:51
419
转载 DP学习一些好的东西（转载）
分类总结：https://blog.csdn.net/qq_1932568757/article/details/82725132背包问题：背包九讲 https://wenku.baidu.com/view/29208152192e45361066f57d.html背包专辑题目 https://blog.csdn.net/woshi250hua/article/details/76...
2019-05-29 19:44:18
125
原创 冒泡排序和直接插入排序
冒泡排序题目链接：http://47.96.116.66/problem.php?cid=2082&pid=9题目大意：对n个数排序排序思想：每次操作吧最大的数移到最后，然后之后不管那个数，处理前n-1个。重复此操作代码：/*我的想法是从小到大排，总共进行n次，首先处理0~n-1将最大数逐渐换到最后一位，然后处理0~n-2，将第二大的数放到倒数第二位....依此类推对于每一层，比方说第一层，我们是怎么把最大的数放到最后一位的呢？我们从左开始遍历，每次处理相邻的两个数，如
2020-07-31 20:11:12
370
原创 Codeforces Round #648 (Div. 2) ABCDEFG
Codeforces Round #648 (Div. 2)Problem A题意：n*m的方格，0表示未填过，1表示填过，初始状态下可能有已经填过的格子。两人轮流填(Ashish 先手)，且只能填 未填过 并且 对应行列都未出现填过 的格子，到谁填不了那个人就输了。 思路：每填下一个1，就有清白的一行和清白的一列双双惨遭毒手。所以统计一下有几行干净的几列干净的，取两者较小的就是最多能凑的对数。 总结：可能容易把能填的格子的要求看错吧，刚开始脑中自动脑补成周围一圈不能有填过的，然后看成
2020-06-20 21:11:28
203
原创 Codeforces Round #496 (Div. 3) C D E1 E2 F
Codeforces Round #496 (Div. 3)Problem A题意： 思路： Problem B题意： 思路： Problem C题意： 给出n个数，询问最少删除几个数使得剩下的每一个数总能找到对应的另一个数使得两个数的和是2x2^x2x(x为非负整数)思路： 枚举每个数形成 202^020~小于2*1e9的最大的2x2^x2x所需的另一个数，只要存在...
2020-01-31 16:05:55
221
原创 Codeforces Round #613 (Div. 2) ABCDE
Codeforces Round #613 (Div. 2)Problem A题意： 给出一个串，L代表-1，R代表+1，现在你只让其中一些数字有效，询文最多有多少种不同结果思路： LR一起用等于不用，所以只用L或者只用R，最后结果就是L+R+1#include<bits/stdc++.h> using namespace std; #define ll ...
2020-01-15 14:37:23
235
原创 Educational Codeforces Round 72 (Rated for Div. 2) ABCD
Educational Codeforces Round 72 (Rated for Div. 2)本场链接Problem A题意：a点物理，b点智力，c个技能点，技能点加完的情况下，物理大于智力的情况有多少种思路：我们只需要a和b的相对差值a-b，然后先把c全部加到a上去，每次移到b，a-b+c -2-2-2,所以不管其他什么的话有(a-b+c+1)/2种，然后不能超过c+1种，因为技...
2020-01-13 19:49:47
80
原创 Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4) A B C D E F
>>>这场比赛的链接Problem A题意：t组数据，每组给出一个n，询问1~n中各个位上都相同的数的个数，比如1~10有1 2 3 4 5 6 7 8 9这九个数满足，答案是9。思路：1~9,10~99,100~999，...各自都有9位，所以获取一下最高位的位数，最高位特殊处理一下+（最高位的位数-1）*9就是答案了。#include<bits/std...
2020-01-05 19:01:10
270
原创 Codeforces Round #499 (Div. 2) A B C D E F
>>>本场链接Problem A题意：给出一个串有n个字符，选择出k个字符，要求总和最小，且a[i]-a[i-1]>=2，存在就输出总和，不存在就输出-1。思路：首先排序，然后一定是选取当前能取的最小的因为舍弃当前位置去取后面的首先当前不利，对于取下一位更小的也不利。#include<bits/stdc++.h> using nam...
2019-12-29 20:59:13
166
原创 P3803 【模板】多项式乘法 ——FFT/NTT模板
>>>FFT>>>NTT要点：①A（x） = A1（x）+ wnk*A2（x） A（x+n/2） = A1（x）-wnk*A2（x）②单位圆的两个复数相乘得到的是角度相加后单位圆上对应的复数（模长相乘，极角相加）③重新转回系数表示，FFT用的是共轭复数，最后还要除以问题的规模NTT用的是规模的逆元④NTT每个规模n下对应的一单...
2019-12-07 18:05:54
467
原创 Python 瞎写
Python不知道学的啥1.一个list可以存放种类数据Extend（）另一个表所有元素一个个倒进去Append（）末尾加一个元素Print（list[a:b:c]）遍历[起点（闭）:终点（开）: i+= 几]2.dictionary {}List[]Tuple（）3.list查找元素的方法① 元素 in 列表名 #这个...
2019-11-24 23:03:03
1893
原创 Codeforces Round #584 C D
本场链接（contest/1219）Problem C解题思路题目大意就是，从串中抓一些数扔到串的末尾，使得这个串中的数排列出来是非递减比如 1672893，我们把67 89抓出来，剩下1 2 3，把67 89按顺序放到123后面，那么就是123456789但是 1892673，这样是不行的，因为抓出的8967必须按顺序放到末尾，而8967是不符合非递减的，而如果67不抓出...
2019-11-12 12:11:41
108
原创 HDU 3436 Queue-jumpers (无旋treap)
题目传送门（HDU3436）解题思路题目的意思是位于一个[1,n]的序列有三种操作，操作一把一个数放到队首，操作二询问某个数现在的位置，操作三询问现在排名为k的数是谁Part I 口胡（第一部分可以跳过）一开始的愚蠢思路是这样的：用一棵平衡树T1维护进行过top操作的数的序列，另一棵平衡树T2维护top操作过的数的值排序①每次top，如果这个数在T1中，找出他的排名，然...
2019-11-09 20:26:33
180
原创 HDU 1890 Robotic Sort（无旋treap）
题目传送门（HDU1890）解题思路题目大意是[1,n]整个区间询问最小的数的位置x，然后[1,x]整段区间翻转，之后最小的数被放到1位置，之后对于[2,n]区间重复同样的操作，每次都让你输出当前区间内最小的数的位置。单纯的寻找区间最小值，线段树之类的直接实现以下就可以了。单纯的区间翻转，随便搞个支持区间操作的平衡树打个标记就可以了。现在两个操作合并在一起的话，该怎...
2019-11-09 19:35:29
213
原创 POJ 2828 Buy Tickets（无旋treap）
题目传送门解题思路题目大意是把一个数插到当前数列的某一位后面，问最后这个数列是啥样的据说还可以用树状数组/线段树做，咱也不想看，咱也不想学。无旋treap的做法非常的直接，基本上会无旋treap这题也能直接写了，所以直接看代码吧。代码#include<cstdio>#include<algorithm>using namespace std;...
2019-11-09 19:10:28
118
原创 P3391 【模板】文艺平衡树 （无旋treap）
题目传送门解题思路用可以提取区间的平衡树，对区间整体打标记，先不下放，等到操作涉及这个节点时再下放：交换左右儿子并给左右儿子打标记我用的是无旋treap刚开始需要建树，建树模仿笛卡尔树，由于所有元素出栈之后自身的儿子不会再有变化，因此出栈的时候再push_up即可，由于栈维护右链，栈顶就是root要看Splay版本的也可以去这里看>>>Splay版本文艺平衡树...
2019-11-09 19:01:11
98
原创 POJ 3481 Double Queue（无旋treap/Splay）
题目传送门解题思路三种操作，插入一个数，取最大值并删除，取最小值并删除。应该有挺多方法可以做的。提供无旋treap和Splay这两种平衡树的数组的做法。代码无旋treap版本#include<cstdio>#include<algorithm>using namespace std;#define ll long long#defi...
2019-11-09 18:52:56
282
原创 Splay/伸展树（P3369 P3391 P2042）
什么是splay？一种平衡二叉树。什么是平衡二叉树？需要先了解什么是：二叉搜索树——简称BST，每个节点最多有两个子节点，左子比当前节点小，右子比当前节点大。因此对于插入和查找第k小的值，都可以从根递归着进行下去，在到达递归终点之前，不是选择这个节点左儿子就是右儿子，因此，操作的复杂度 = 树的深度。然而，这棵树的形状会因为你插入数字的顺序和大小不同，导致层数过大。比如你插...
2019-10-28 20:40:39
537
原创 线性基学习
>>>大佬写的贼好建议参考线性基的基本概念：①引入一下给出一个数组a[],我们从a中得到一个数组b[],a数组中的任何数都可以由b中一个或者几个数的异或和得到，b就是我们所说的线性基。②b数组本身具有什么性质？（1）b数组的数量最多 = 数组a数据最大值的二进制位数比如说a最大是int最大，那么最大是2^31-1，需要31位来表示，所以此时线性基最多3...
2019-10-12 20:50:43
162
原创 树链剖分（P3384）
树链剖分的作用树链剖分用于解决树上区间询问，主要有两种：给出两点，询问和修改之间的路径，又或者给出一个点，询问和修改整颗子树的信息。树链剖分需要配合其他数据结构如线段树等一起使用说白了，树链剖分只是根据询问提供正确的区间针对路径给出区间 的 复杂度为O（logN）针对子树给出区间 的 复杂度为O（1）如何实现？树链剖分，顾名思义，就是把树分成链。分为重链和...
2019-10-12 19:41:13
120
原创 后缀平衡树模板（例题SPOJ - DISUBSTR）
删除操作还没有验证，原本例题是HYSBZ5084，不过网站好像炸了，一直没法提交，目前不知道删除代码正确性，不过插入和维护height都已经验证过意思就是你可能会被这篇文章演平衡树用treap写的什么是后缀平衡树？利用平衡树动态维护后缀数组。可以支持的操作为加入一个字符到串末尾或者删除末尾一个字符。先搞清两个问题：只能在末尾操作吗？中间插入删除会影响多个后缀，末尾插...
2019-09-30 20:47:08
145
原创 Codeforces Round #587 (Div. 3) ABCD
题目传送门（contest1216）Problem A变成每两个一a一b#include<bits/stdc++.h>using namespace std;#define ll long long#define for1(i,a,b) for (int i=a;i<=b;i++)#define for0(i,a,b) for (int i=a;i<...
2019-09-27 20:56:04
93
原创 可持久化无旋treap（良心讲解 P3835）
前置技能：无旋treap什么是可持久化平衡树？每经过一次操作，当前状态的整棵树就成为一棵全新版本的树，给每个版本编个号，我们可以根据版本号查找这格版本的树中的一些信息，也可以在这个版本上进行修改生成全新版本。我们需要保留每个版本的所有信息。可持久化无旋treap的大体思想由于treap的树的期望深度为O（logn）级别，所以每次操作（插入/删除等）只涉及O（logn）个节点的修...
2019-09-23 21:26:18
294
原创 可持久化线段树/主席树 （P3919 + P3834）
建议先了解一下动态开点线段树，可以参考一下我写的这篇什么是可持久化线段树：若询问次数为q，维护区间为m则所需空间为O（q*logm）通过root[]数组，记录不同版本的根节点编号，我们可以方便的在某个版本上修改和查询问题1：什么是不同的版本？我在某个版本的线段树上做了某次修改，修改后的线段树，就是不同与之前的一个船新版本。问题2：为什么只要O（q*logm）？对于在...
2019-09-16 21:22:38
92
原创 动态开点线段树（P1908/洛谷1908）
什么是动态开点线段树：假设操作次数为q，维护区间大小为m普通的线段树会先把所有可能需要的节点开辟出来需要的空间为O（4*m）这样可以：1.方便的通过节点下标所引导对应的左右儿子节点2.所有需要的节点都已经有了，不必在额外创建新节点动态开点线段树则是只开辟需要的节点，因此每个节点左右儿子都要记录需要的空间为O（q*logm）这样可以：1.很明显可以节省空...
2019-09-16 19:40:13
1211
原创 BZOJ 1500 [NOI2005]维修数列 （无旋treap良心题解）
题目传送门上面链接沉了幸亏洛谷还有这道题无旋treap解题的原理：1.无旋treap可以在维护平衡的同时保持中序遍历不变（treap也可以，应该都可以），因此我们用下标代表插入二叉树的值，那么我们可以按照中序遍历获得原来的数组。2.无旋treap的分裂操作可以分裂出包含前k个节点的树和剩下元素的树，就相当于可以把数组切开。你可以切取想要的区间进行操作，操作完再merge回去即可...
2019-09-10 20:14:22
198
1
原创 无旋treap/fhq-treap 模板 （附良心讲解 + 例题：洛谷P3369 普通平衡树）
博文更新：20190917 更新了一下merge和split函数的递归理解定义：无旋treap，就是不通过旋转的维护堆性质的treap，根本的原理还是 tree + heap。与普通treap的不同之处：大概就是可以可持久化。然后区间操作的话，不知道有旋的行不行，用无旋的反正是比较好搞，区间操作举个例子就是让你把一段区间的数反过来等等。现在听着可能区间操作什么的可能莫名...
2019-09-09 22:57:45
649
原创 HDU 1506 Largest Rectangle in a Histogram（笛卡尔树）
题目传送门解题思路：来来来，笛卡尔树了解一下代码1：（非要用结构体版）#include<bits/stdc++.h>using namespace std;#define ll long long#define for1(i,a,b) for (int i=a;i<=b;i++)#define for0(i,a,b) for (int i=a;i&l...
2019-09-07 21:28:51
156
原创 笛卡尔树模板
如果学过treap(一种平衡二叉树)，笛卡尔树应该很好理解本文只介绍基础的建树，没有深入的东西。（你懂我意思吧）笛卡尔树也是二叉树+堆一、二叉树与堆的概念可以看看我这篇，顺便把treap学了也可以，简单哒二、笛卡尔树的结构笛卡尔树可以按顺序插入一个数组，我们将下标当值插入二叉树，然后数组的值作为“优先级”，维护堆的性质。盗一份网上的图你们参考一下，结构就是这个样子...
2019-09-07 21:27:47
280
原创 Codeforces Round #583 (Div. 1 + Div. 2, based on Olympiad of Metropolises) ABCDEF
本场链接（contest/1214）Problem A题意：给定两种兑换的货币的兑换率以及所有面额，问当前的卢比尽可能换成这两种货币后最少剩下多少？解题思路：首先先把换这么多种面额简化成两种，即这两种货币的最小面额，因为每种货币较大的面额都是：最小的面额 x 对应倍数。然后到了这里，只剩两种的情况下，暴力枚举其中一种货币的张数，另一种尽量取即可。#include<bit...
2019-09-06 21:32:35
183
原创 POJ 1442 Black Box（Treap模板题）
题目链接：http://poj.org/problem?id=1442题目大意：就讲一下第二行数列到底是什么玩意儿吧，第二行的意思是插入第几个数的时候进行一次询问，第一次询问排第一，第二次询问排第二的...解题思路：Treap模板题，所以我另写了一篇博客把这题需要的部分讲了一下：对，对，就是这里代码：#include<cstdio>#include<c...
2019-08-30 20:17:52
184
原创 Treap模板
Treap = 二叉搜索树 + 堆一、二叉搜索树简称BST，每个节点最多有两个子节点，左子比当前节点小，右子比当前节点大。因此对于插入和查找第k小的值，都可以从根递归着进行下去，在到达递归终点之前，不是选择这个节点左儿子就是右儿子，因此，操作的复杂度 = 树的深度。然而，树会根据插入的数的不同，产生不同的形状，并不是我们认为的logN，最好情况下才是O（logN），要达到O（lo...
2019-08-30 20:09:39
311
原创 SPOJ - SUBLEX Lexicographical Substring Search(后缀自动机)
题目传送门解题思路：多组输入会RE（坑爹玩意儿）后缀自动机上可以跑子串，因此每一位我们都按照a~z的取，这样可以使字典序尽量小。怎样才能找到第k小的呢？DFS预处理每个节点包括自己共可形成多少子串，记为cnt[]。注意记忆化，不然GG（复杂度大概从O（26^2N）->O(2N)）然后逼近即可，我们保证k小于等于当前子树大小，找到当前根的26个子节点中，第一个使得前po...
2019-08-25 19:49:10
88
原创 SPOJ - NSUBSTR Substrings（后缀自动机）
题目传送门解题思路：题意是求一个串各个长度的子串的可重叠最大重复出现次数。①首先我们肯定能想到构造后缀自动机的时候每加入一个新的字符新产生的子串长度一定是跟当前节点有关。用cnt[]记录每个节点的串出现的次数，在一个个添加字符的时候，每次在这个新产生的后缀节点+1，我们知道如果这个节点没有对应符合要求的父节点的话还会再产生一个新的节点，那个节点不用记，因为那个节点也属于当前节点的后缀，...
2019-08-24 19:10:28
158
原创 SPOJ-LCS2 Longest Common Substring II （后缀自动机）
题目链接：https://www.spoj.com/problems/LCS2/en/解题思路：对于两个串的LCS，我们只需对其中一个建sam，另一个在上面跑，记录最大值即可。对于多个串的话，我们需要记录每个串跑sam的时候在每个节点的相同子串取最大值，每次跑完更新一下每个节点当前所有串的最长相同子串取最小值。需要注意的是失配时跳fa数组的时候也需要更新fa节点的数据。代码：...
2019-08-23 12:20:08
119
原创 SPOJ LCS:LCS - Longest Common Substring(后缀自动机)
题目链接：https://www.spoj.com/problems/LCS/en/解题思路：数据量和时间限制摆明了准备卡掉O（N*logN）的求法，后缀自动机可以O（N）解决讲解后缀自动机的博客（易懂）：https://www.luogu.org/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie讲解后缀自动机的PPT（高深）：https://...
2019-08-21 14:12:23
113
原创 HDU 3247 Resource Archiver（AC自动机+BFS+状压DP）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3247参考博客：https://www.cnblogs.com/kuangbin/p/3164106.html 不能处理的数据：2 111 001100也不知道这种病毒串是否合法，我觉得应该不会出现这种病毒串，不然压缩原本字符串的过程中间还得添几个其他的字符也算不上是压缩了。各...
2019-08-18 13:22:44
149
原创 HDU 5418 Victor and World（Floyd + 状压DP解决TSP问题）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5418解题思路：有n座城市，m条边，询问从1节点开始走遍所有节点回来的最短路径。因为n比较小，因此可以用状压DP做例如，我们用一个数i表示一种状态，若i转化为二进制为10111，表示去过1,2,3,5，没去过其他城市先用Floyd求出任意两点最短路，记做mp[][],mp[i][j]...
2019-08-17 12:14:34
237
原创 图论的一些基础算法的模板
Floyd 算法：作用：求任意两点最短路时间：O（V^3）#define for0(i,a,b) for (int i=a;i<b;i++)memset(dp,INF,sizeof dp);for0(i,0,n) dp[i][i] = 0;int u,v,w;for0(i,0,m){ scanf("%d %d %d",&u,&v,&w);...
2019-08-15 16:47:05
99
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人