- 博客(125)
- 收藏
- 关注
RSS订阅原创 leetcode 第 59 场双周赛 5837. 划分数字的方案数 题解
前置知识：后缀数组，RMQ区间最值，简单dp。首先我们会想到使用dp的思路来解决，dp[i][j] 表明当前第i个位置为结尾往前j个位置截取出来当作一个数的方案数，dp[i][j] 就是对于 i-j+1 位置为结尾上小于当前截取的值的方案数的和，因为每次要选取不同的j，这样就是n的平方的时间复杂度，还要每次比对数的大小是n的时间复杂度，最终的时间复杂度就是n的三次方。仔细思考一下，发现只能简化数字的对比，字符串排序就能得到大小，只要求出 rank[i-j+1] +1 和 rank[i-j-j+1]
2021-08-22 01:02:10
172
原创 投票算法简介
使用场景：在一个数组中找到超过一半的那个元素。原理：取第一个元素当标志，遍历数组，如果相同+1，不相同-1，如果为负数，舍弃原先的元素，将当前元素变成标志，继续前面的做法。结束之后，再次循环一遍判断标志是否是超过一半的元素。分析：假设数组里面有一个元素超过一半，假设当前标志不是这个超过一半的元素，那么最终一定会变成负数，切换标志，剩下的元素一定是超过一半的那个元素多，因为抵消了前面的标志，以此类推，最终获取的标志一定是超过一半的元素。代码：int majorityElement(vec
2021-07-09 22:07:45
388
原创 序列式容器
vector：就是一个可变的数组，底层是一个固定数量的数组，当元素的数量大于数组的容量的时候，会进行倍数扩充，将原来数组的数据拷贝到现在的数组里。vector iterator 就是一个普通的指针，对于vector的操作其实就是对于指针的操作，对于操作符进行了重载，可以使之和普通数组一样使用。list：链表，底层就是一个双向链表，list的iterator就是_list_node的指针，对于其操作就是在链表上进行操作，重载运算符。deque：和vector相似，比vector头部插入快，底层是一
2020-10-31 23:29:22
165
原创 STL源码剖析第三章迭代器和traits编程技法读后感
迭代器类似于指针的对象，内中管理着元素指针，对于*、->、++、--等操作符进行重载，管理着对象的创建和删除。对于迭代器的使用的时候需要相对应的型别，所以利用traits技法，来获取型别定义对象。traits就是特性萃取机，定义一个iterator_traits类，在类中使用typedef对于模板中的参数进行重命名，这样我们就能获取传递的参数的型别，对于特定的类型如原始指针，我们可以特化一个版本的模板。5中常用的型别：value_type、difference_type、pointer、r
2020-10-28 00:17:26
119
原创 STL源码剖析第二章空间配置器（allocator）读后感
STL 将空间配置器分成三部分1、构造construct()和 destory()：因为不知道会传递什么类型，使用template模板来实现，对于特别的类型，使用特化来实现。因为不同的型别有不同的处理方法，所以利用类型萃取和函数重载来实现。涉及traits，在第三章解释。2、空间的配置与释放设计要求： 向system heap申请内存，考虑多线程问题，考虑内存不足的问题，考虑过多的小型内存造成内存碎片的问题。根据这些情况，设计了两级内存配置器，如果内存大于128 b...
2020-10-27 23:34:23
120
原创 高并发内存池C++
三层结构： PageCache:内存的单位是页，一页的大小是4KB，从操作系统中最多申请128页，维护128个链表，每个链表的每个节点存放对应数量的页。节点结构体：//记录页的内容typedef size_t PageID;struct Span{void *_objlist = nullptr;//分配的地址的头指针 因为分配内存返回的是vo...
2020-10-16 00:17:14
224
原创 K - Kingdom of Ants Kattis - kingdomofants
题解：线段树扫描线求面积交，维护区间修改次数为0的和区间次数为奇数和偶数的，偶数的个数减去为0的个数就是面积交为偶数个矩阵。代码：#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=2e6+100;struct Line{ ll y,x1,x2,v; ...
2019-11-30 14:15:38
260
原创 E - Rainbow Roads Kattis - rainbowroads
题解：点分治枚举任意两点为端点的路，判断路是否是正确的，计算重心为根的树，暴力跑子树，看子树是否有从根到子树上的点的路有错误，标记这个点，标记这颗子树，如果有多颗子树被标记，那么这整颗树都标记上，如果只有一颗子树被标记，那么除这颗子树之外的子树全部标记，然后在判断与根相连的边有没有相同的，如果相同，这两条边相连两颗子树的点都要被标记，最后没有被标记的点就是正确答案。代码：#include...
2019-11-29 10:31:15
188
原创 F - Mr. Panda and Fantastic Beasts Gym - 101194F
题解：对于每个字符串后面加一个特殊符号把所有的串连接在一起，然后在后缀数组中找到后缀的位置出现在第一个串，对于这个串找到前后最近的不是第一个串的字符串，取height数组前后区间最小值的最大值，如果后缀小于第一个串中以i为起点的后缀长度，取最小值，如果最小值相同，取rak最小的。代码：#include <bits/stdc++.h>using namespace std;...
2019-11-21 08:52:36
244
原创 Gym 102428L Leverage MDT
题解：如果满足给定条件的正方形，只要正方形的每一行中都为相同的就行了，不用管是否是good土地,因为可以使用MDT对于每一行进行转换。预处理，对于每一行的每一个位置，如果这一行当前位置和前一个位置是不同的那么这个位置就为1，对于每一个正方形，我们把行减小一列进行二维前缀和，如果二维前缀和的值为0，那么这个正方形就满足条件，但是因为枚举每个正方形会超时，那么我们可以对于每一个为正方形的右下点，二分枚...
2019-11-19 10:26:47
359
原创 Gym 102428G Gluing Pictures
题解：其实就是在找最少需要多少原串中的子串构成询问串，SAM进行匹配就行了。代码：#include <bits/stdc++.h>using namespace std;const int maxn=2e5+5;int len[maxn * 2], //最长子串的长度(该节点字串数量=len[x]-len[link[x]])link[maxn * 2], //后缀...
2019-11-19 10:18:58
554
原创 K - Addition Robot CodeForces - 1252K
题解：对于线段树上的一段，Ax=x*a1+y*b1 , Bx=x*a2+y*b2, x，y为初始给的A，B值，Ax，Bx，为操作完这一段的结果值，如果线段树上两段合并前一段的Ax为后一段的x，前一段的Bx为后一段的y，带入结果就算出两段合并的值。对于反转操作，其实就是Ax变为 Bx，然后a和b交换。代码：#include <bits/stdc++.h>using names...
2019-10-29 16:51:42
167
原创 M - Mediocre String Problem Gym - 101981M
题意： 给你个s串和t串 找三元组（i，j，k） 在 s中选取 i -j ，在t中选取 1-k，使他们拼凑出来的是回文串。题解：首先对于s串倒转，exkmp求s串和t串extend，对s串进行manacher，求每个统计每个回文串的右端点，最后统计答案。代码:#include <bits/stdc++.h>using namespace std;typedef lo...
2019-09-21 21:26:04
226
原创 G. Indie Album
题解： 字典树原本的串，ac自动机询问的串，预处理答案，树链剖分+树状数组处理fail树，dfs寻找所有串，统计答案。代码：#include <bits/stdc++.h>using namespace std;const int maxn=4e5+1005; vector<pair<int,int> >g[maxn];int tree[ma...
2019-09-10 16:18:37
203
原创 J. Random Access Iterator
题解：想如果到达某个点往下走能走到一次的错误概率，只要有一次对就是对的，所以求出全部错的概率，所以这个点往下走的正确概率为1-全部错误概率。结果就是根节点往下走正确的概率。代码：#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int ma...
2019-09-07 20:40:15
237
原创 A - Artwork Gym - 101550A
题意：给你n*m个格子每次添加一条黑线，问这些黑线将白格子分成几个部分。题解：首先将全部黑线涂上，将每个格子标记在那个块上，对于询问从后往前删除，并将删除之后的白格子赋值为新的块，然后并查集合并，结果就是这次询问的块数。代码：#include <bits/stdc++.h>using namespace std;const int maxn=1e3+5;int n,...
2019-09-03 17:03:31
186
原创 The beautiful values of the palace
题目链接：https://nanti.jisuanke.com/t/41298题目大意:给一个n*n的矩阵，矩阵的值成螺旋状，找到m个格子，每个格子的值为原先数字的位数和，其他的全为0，询问p次给定矩阵的权值。题解：首先快速求出这个点的原先的值，寻找这个点在那个环上，在四个边上那个边上，就能求出来了，线段树前缀和，扫描线的做法，一次查询分成两次。代码：#include <b...
2019-09-02 16:40:45
120
原创 K-th occurrence
题意： 给定区间 [l,r] 和 k，求和区间 [l,r] 相同的串的第k个位置在哪？题解：利用后缀数组求出height数组，因为排名相近的两个串是最想像的串，所以st表求区间最小值，找到字符相同的串的区间，然后利用主席树存sa值求第k大。代码：#include <bits/stdc++.h>using namespace std;typedef long long ...
2019-08-24 18:46:50
477
原创 Rikka with Travels
题意：求出两条不相交的路的不同长度对。题解：换根dp维护最长、次长、次次长链，维护子树的直径和子树的次长直径，线段树区间更新，单点查询。代码：#include <bits/stdc++.h>#define ls x<<1#define rs x<<1|1using namespace std;const int maxn=1e5+5;...
2019-08-20 21:00:14
162
原创 C - Coprimes Gym - 101492C
题意：给你一个长度为n的序列，给你m次询问区间 [l,r] ,回答区间内是否有一对互质的数。题解： 首先素数筛，开素数筛个bitset，bitset的每一位对应序列的每一位。从后往前循环，维护两个bitset，a清空，b每次循环都把后一位从0变为1，然后求当前数的素数因子，然后a把素数因子的bitset或起来，然后与b异或，使用_Find_first(),加1就是当前位的后面最近互质的数的位置...
2019-08-19 20:49:05
153
原创 J - Deciphering Oracles Gym - 101492J
题意：1~n之间的数字重新排序，排序规则是：如果x<y （x的位数求和小于y的位数求和，或者x的位数求和等于y的位数求和且x<y）。题解：数位dp求n的位数和小于sum的个数，对于第一个答案，我们首先求出k的位数和ans，然后求出k在ans的是第几位，然后求出n在ans-1是的个数，最后两个相加就求出来了。 第二个答案，首先for循环求出第k位在那个位数和内，在这个位数和的第几个，...
2019-08-19 20:40:34
172
原创 菜菜种菜
题目链接：https://www.cometoj.com/contest/58/problem/D?problem_id=2758题解：对于每一个点维护离它最近的左右点，然后对于每次询问，标记而且按照r排序。树状数组维护每一点为左端点开始的区间。用优先队列维护每一个右端点，如果树状数组插入到当前r的时候删除右端点为当前r的区间。代码：#include <bits/stdc...
2019-08-10 19:35:30
231
原创 P3810 【模板】三维偏序（陌上花开）
题目链接：https://www.luogu.org/problemnew/show/P3810题解：三维偏序，cdq分治来解，首先对于首先第一维有序，然后按照一维排序后的第二维二分，树状数组维护第三维。代码：#include <bits/stdc++.h>using namespace std;const int maxn=1e5+5;int pp[maxn*2]...
2019-05-23 21:05:26
234
原创 P1393 动态逆序对
题目链接：https://www.luogu.org/problemnew/show/P1393题解：把这个转化成三维，使用cdq分治来解决，第一维为删除的时间（不删除的为n+1），第二维是以位置，第三维就是数值。代码：#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll ...
2019-05-23 21:00:29
144
原创 E. Split The Tree HDU - 6504
题目大意：给你一个树，每个节点上都有一个权值，把这棵树分成两棵树，问每一棵树的不同数值的个数和最大。题解：首先dfs序，如果查询所有子树，会把两棵树分成三个区间，就不能查询第二课树的不同数值的个数，所以复制此序列放在第一次的后面，因为是离线的，可以使用树状数组维护区间不同数值的个数，对于当前r位置把此位置加上树状数组中，如果前面有相同的值，那么把前面的那个位置删除，然后查询此r位置的l就能找到...
2019-05-06 16:29:12
304
原创 永无乡 HYSBZ - 2733
题目链接：https://cn.vjudge.net/problem/HYSBZ-2733题解：先用并查集统计哪些岛是相连的，然后每个块动态开权值线段树，每两个岛相连就是把两个块的权值线段树合并起来，查询就是从并查集中寻找那个块，然后查询第k大。注意：（这个题的读入字符要用字符串读入，否则会出错）；代码：#include <bits/stdc++.h>using nam...
2019-04-29 20:00:39
153
翻译 主席树模板
#include <iostream>#include <algorithm>#include <stdio.h>using namespace std;int h[100005],pp[100005],root[100005];int n,m,cnt,ans;struct node{int l,r,sum;};node tree[5000005...
2019-04-14 17:26:42
80
原创 B - Count on a tree
题目链接：https://cn.vjudge.net/contest/290094#problem/B题目大意：给你一棵树，每个节点都有一个权值，接下来q次询问，给你两个节点，询问这两个节点之间的路上第k大的权值是多少。题解：假设两个节点为x,y，首先利用倍增lca求出这两个节点之间的lca，每个节点的主席树是以父亲节点为根建立的，两个节点之间的路的主席树为x+y-lca(x,y)-fa[...
2019-04-14 17:25:32
184
原创 倍增lca模板
注意fa数组和depth数组一定要先初始化。#include <iostream>#include <algorithm>#include <stdio.h>#include <string.h>#include <vector>using namespace std;int fa[10005][50],depth[10...
2019-04-14 17:19:01
243
翻译 H Parco_Love_GCD
题目大意：给你一个长度为n的序列，求所有区间gcd的和，结果取余1e9+7.题解:首先用st表处理好区间gcd，然后枚举左区间二分右区间，因为一个数字的因子最多有log（n）个，所以右区间最多右log(n)个。代码：#include <bits/stdc++.h>using namespace std;const int mod=1e9+7;const int ma...
2019-04-14 17:05:54
139
原创 递减序列
Problem Description现在给你n个不同的数，a1，a2，a3， ..... ，an。求长度为k的不同递减序列的个数，既包含连续也包含不连续的序列。例如：给你n=3，k=2，原始序列为 3 ，1，2 。长度为2的递减序列为3，1和3，2；一共有两组所以答案为2.Input第一行输入n,k(1<=n<=20000, 2=<k<=10)分别代...
2019-02-27 21:00:10
1136
原创 这真的是签到题
Problem Description给你n个整数，a1,a2,a3,......,an。每个整数范围1到1e6。选取任意的i（1<=i<=n）和j（1<=j<=n）如果gcd（ai,aj）>1，ai和aj为一组，如果ai和aj为一组，ai和ak为一组，那么ai,aj,ak为一组，求这n个整数中，最后有多少个组。Input输入一个T表示组数（T<=1...
2019-02-27 20:50:02
399
原创 A - Network POJ - 1144(割点)
链接：https://cn.vjudge.net/contest/258373#problem/A代码：#include <iostream>#include <algorithm>#include <stdio.h>#include <string.h>#include <vector>using namespace...
2018-12-27 20:54:59
114
原创 树状数组
树状数组原理：假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。来观察这个图：令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：C1 = A1C2 = A1 + A2C3 = A3C4 = A1 + A2 + A3 + A4...
2018-12-12 22:04:42
138
原创 线段树
刚刚学过一些有关线段树的知识，现在就简单的说一下线段树是什么。线段树就是一棵树，例如我们要求一段区间的和，那么刚开始的树的根就是存的全部区间的和，接下来左儿子为1-mid区间的和，而右儿子就是mid+1--n的区间和，左儿子和右儿子以此类推直到某个节点的区间为他自己那么我们就建好了一线段树。建树代码：struct node{ int l,r,num;//l,r。存的是区间范...
2018-12-07 21:53:34
102
原创 D - Just a Hook
题目链接：https://cn.vjudge.net/contest/269834#problem/D题目大意：刚开始给你n个点，每个点的价值是1，然后会区间更新价值，询问最后总的价值是多少。题解：lazy算法。代码：#include <iostream>#include <algorithm>#include <stdio.h>#inc...
2018-11-15 11:30:17
239
原创 A - 敌兵布阵
题目链接：https://cn.vjudge.net/contest/269834#problem/A代码：#include <iostream>#include <algorithm>#include <stdio.h>#include <stdlib.h>#include <string.h>using name...
2018-11-15 11:25:30
396
1
原创 B - I Hate It
题目链接：https://cn.vjudge.net/contest/269834#problem/B题目大意：单点更新，区间查询。题解：线段树。代码：#include <iostream>#include <algorithm>#include <stdio.h>#include <stdlib.h>#include &l...
2018-11-15 11:24:03
289
原创 C - A Simple Problem with Integers
题目链接：https://cn.vjudge.net/contest/269834#problem/C题目大意：区间更新和区间查询。题解：lazy算法，加线段树。代码：#include <iostream>#include <algorithm>#include <stdio.h>#include <stdlib.h>#in...
2018-11-15 11:21:38
92
翻译 N - Trailing Zeroes (III)
题目链接：https://cn.vjudge.net/contest/70017#problem/N题目大意：给你一个数n，让你求出后缀有n个零的最小的x！。题解：二分1到5*1e8+5之间的数，然后计算这个数一直除以5的和。代码;#include <iostream>#include <algorithm>#include <stdio.h&g...
2018-10-27 16:22:40
124
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人