- 博客(70)
- 收藏
- 关注
RSS订阅原创 扫描线求矩形是否相交
#include<bits/stdc++.h>using namespace std;const int maxn=300005;struct node{ int l,r,h,val; bool operator <(const node &x)const { return h<x.h; }}b[maxn]...
2019-10-17 19:34:25
274
原创 2019沈阳网络赛B 并查集+dfs
补题的时候，忘记将怪兽节点的size值变为0。#include<bits/stdc++.h>using namespace std;int fa[200005],siz[200005];int getfa(int x){ int fx=fa[x]; if(fx!=x) { fa[x]=getfa(fx); } ret...
2019-09-18 19:03:47
196
原创 2019 牛客暑假多校训练营 第四场 I 广义后缀自动机+回文自动机
广义后缀自动机，求多个串的本质不同子串个数。回文自动机求回文串个数#include<bits/stdc++.h>using namespace std;const int maxn = 4e5+100;char s[maxn];int len;int T;int n,m;struct SAM{ int last,cnt,nxt[maxn*2][26]...
2019-08-12 20:36:32
292
原创 牛客网小白月赛 16 H 线段树求gcd
线段树维护差分数组，求gcd#include<bits/stdc++.h>using namespace std;const int maxn=1e5+100;int sum[maxn*4];int gcd[maxn*4],maxx[maxn*4];int a[maxn];void pushup(int i){ sum[i]=sum[i*2]+sum[i*2...
2019-08-08 10:24:35
161
原创 2019hdu暑假多校训练营第四场 H 主席树+二分
主席树+二分二分与p的距离，确定与[p-mid,p+mid]这个区间中有多少个点，如果大于等于k个，说明这个区间合理，可以缩小寻找范围，否则增大寻找范围。#include<bits/stdc++.h>using namespace std;const int maxn=1e5+10;int root[maxn*40];int sum[maxn*40];int ls[...
2019-08-06 14:25:35
154
原创 洛谷p2444 p4052 AC自动机
ac自动机fail指针，即为当失配后，跳转至与当前后缀相同的一个前缀上。因此如果一个点的fail指向的点是一个单词的终止，那么说明当前匹配到的这个位置，一定包括这个单词。因此建立fail指针时，我们可以更新ed的值，由此来判断，当到达这个点的时候是否会经过单词的结尾。P2444 在ac自动机上找一个无限循环的串，且这个串不可经过单词结尾，通过nxt数组进行dfs，维护两个数组，一个判断...
2019-07-31 14:17:25
150
原创 hdu多校2 I I Love Palindrome String 回文自动机+hash
回文自动机学习链接：https://blog.csdn.net/lwfcgz/article/details/48739051 https://www.cnblogs.com/Xu-daxia/p/10544128.html#autoid-0-3-0对于此题，回文自动机记录本质不同回文串出现次数，hash判断这个回文...
2019-07-31 13:48:52
123
原创 洛谷p2322 ac自动机+最短路+dfs
ac自动机建立fail指针，求出每个点能覆盖的全部串种类，bfs求出最短母串长度（最短路），dfs求出路径输出。#include <iostream>#include <stdio.h>#include <stdlib.h>#include <queue>#include <cstring>#include <alg...
2019-07-28 20:17:38
137
原创 洛谷p4180 ac自动机
匹配字符串时，对于重复的单词我们只考虑一次，我们开一个数组记录，重复单词的第一个id将重复单词的出现次数全部变为第一次出现的个数相加。且在匹配时，对于每个now只扫描一次，不重复扫描。#include <iostream>#include <stdio.h>#include <stdlib.h>#include <queue>#incl...
2019-07-28 15:47:20
144
原创 洛谷p3121 ac自动机
ac自动机匹配时，建立两个栈，其中一个栈存储答案，另一个栈存储失配指针。如果在某点找到我们要删除的单词（全部），那么我们要将匹配指针前移至此单词前面那个字母，即将我们的指针前移长度单位。#include <iostream>#include <stdio.h>#include <stdlib.h>#include <queue>#i...
2019-07-28 14:38:10
180
原创 主席树学习总结
主席树即每次建立改变点的链接，建立n颗权值线段树，根据其类似于前缀和的性质，求解区间第k大问题。POJ - 2104数组区间上求第k大：#include<iostream>#include<string>#include<algorithm>#include<cstdlib>#include<cstdio>#incl...
2019-07-28 09:38:37
123
原创 hdu 5068&&2019牛客网暑假多校训练赛E 线段树+矩阵乘法
hdu 2068#include<bits/stdc++.h>using namespace std;//用线段树维护一个2*2的矩阵，a[i][j]表示从这一层第i个门到下一层第j个门是否联通，//第i层到第j层之间的矩阵相乘之后的结果矩阵，各元素和为从第i层到第j层的种类数const int mod=1000000007;struct mat{ long ...
2019-07-24 19:43:38
186
1
原创 2019牛客暑假多校训练营第一场 A 单调栈
两个数组中，第i个左边第一个比a[i]小的值的下标相等的时候，就说明这两个数组等价。当判断向右移动一位时，我们可以发现，我们需要重新是否等价的区间新增了[1,i],[2,i]···[i-1,i];当右边第一个比a[i]小的下标为j时，区间左值小于等于j的显然最小值都是相等的（因为最小值不是a[j]就是在a[j]的左边，这一部分在i-1时已经判断相等），当区间左值大于j时，我们可以发现，最小值都...
2019-07-19 09:37:00
154
转载 hdu6333 莫队+组合数
#include<bits/stdc++.h>using namespace std;//组合数性质：//(n,m)=(n-1,m-1)+(n-1,m);//由题意可知求s(n,m)=sega(i=0-m)(n,i);//s(n,m)=s(n,m-1)+(n,m);//s(n,m)=2*s(n-1,m)-(n-1,m);const int maxn=2e5;struc...
2019-07-17 16:09:55
157
转载 基础莫队分块优化模板
#include<bits/stdc++.h>using namespace std;//分块时按左端点所在块排序，块内按照右端点排序const int maxn=100000;struct query{ int l,r,id,pos; bool operator <(const query &x) const{ if(pos=...
2019-07-17 09:57:15
215
原创 CF EDU 68 E树状数组判断直线之间构成矩形的个数
#include<bits/stdc++.h>using namespace std;const int maxn=200000;long long tr[maxn+100];struct node{ int x,l,r;};node q[200000],p[200000];int n;void add(int x,long long t){ whi...
2019-07-15 18:00:07
162
原创 线段树区间01区间值异或与相邻1个数
#include<bits/stdc++.h>using namespace std;int tr[800000],l1[800000],r1[800000];int l2[900000],r2[900000],tr2[800000];int lazy[900000],a[200000];void pushup(int i,int l,int r){ int m...
2019-07-14 21:30:52
384
原创 树链剖分边权 poj 3237
#include <cstdio>#include<string.h>#include<algorithm>#include<iostream>using namespace std;const int M=2e5+100;int f[M];int d[M];int siz[M];int rk[M];//保存树链剖分后，节点编号对...
2019-06-19 18:32:52
208
原创 权值线段树模板
#include <bits/stdc++.h>using namespace std;const int maxn=1e6+10;const long long mod=1e9+7;long long sum[maxn*4],val[maxn*4];int ls[maxn*4],rs[maxn*4];int cnt;void update(int &root...
2019-06-16 16:31:39
163
转载 C. Electrification
思路借鉴：https://blog.csdn.net/qq_43506138/article/details/90990594感谢大佬对于一个长度为n的序列k=n-1，那么对于第k+1即第n个最小就是取点为区间中最大值与最小值的和出2（（max+min）/2），当k小于n-1时，我们可以发现，我们想要找到区间中第k+1大的数，可以每次取一个长度为k+1的序列，那么，第k+1大的数一定出现在这...
2019-06-07 16:56:56
308
原创 hdu 4578 Transformation
从题面可以推断，如果一个区间中的值很可能为等于同一个值，即有操作涉及，对某个区间设为t之类，就很可能存在一个区间，区间值全部相等，就可以用线段树做标记，标记区间值，如果，区间中有值不相等则对其赋值为-1，注意如果区间值相等修改，或者查询时需要下推标记。#include<bits/stdc++.h>using namespace std;int mod=10007;int ...
2019-06-07 14:56:57
137
原创 线段树 最大连续区间 hdu1540
#include<bits/stdc++.h>using namespace std;int li[100000*4],ri[100000*4],mi[100000*4];void pushup(int i,int l,int r){ int mid=l+r>>1; if(li[i*2]==(mid-l+1)) { li[i...
2019-06-05 20:28:05
135
原创 Codeforces Round #563 (Div. 2) Ehab and the Expected XOR Problem
数组部分异或和与前缀疑惑和之间的关系（a为原数组，b为a的前缀异或和数组）：al^al+1^al+2^^^ar=bl-1^br因此题目中不允许al^al+1^^^ar等于x且不可等于0，因此就可转换为bi^bj=0且bi^bj=x不可出现。再转换一下，就可以得到bi或者bi^x只能出现一次。同时bi也不能等于x。#include<bits/stdc++.h>...
2019-06-05 19:23:32
137
原创 线段树区间染色 map，vector离散化 poj2528
#include<map>#include<vector>#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;//线段树区间染色，对于杂色区间tree赋-1.没有颜色赋值为0，其他颜色...
2019-05-31 12:58:27
181
原创 2019 东北赛
链接：https://vjudge.net/contest/304079B#include <bits/stdc++.h>using namespace std;long long gcd(long long a,long long b){ return b?gcd(b,a%b):a;}vector<long long>v[1000005...
2019-05-30 11:09:10
419
原创 树上dp
hdu 4123树的直径+ 单调队列 + 尺取50000个点的树，每个点有一个人，每个人会跑到离自己初始点距离最远的点上，这个距离为distance[i]。给你500个查询，对于每个查询Q，找一段连续编号的人，比如[left,right]，满足 max( distance[i] i∈[left,right] ) – min( distance[i] i∈[left,right] ) ...
2019-01-17 18:50:46
218
转载 找一个字符串有多少不同子串（trie树）
感谢铭哥提供的思路：https://blog.csdn.net/DT2131/article/details/54936247找一个字符串有多少不同子串，利用trie树性质，即为trie树上有多少个不同的节点。代码：#include <iostream>#include <stdio.h>#include <stdlib.h>#include...
2019-01-16 17:41:42
2022
原创 树上倍增
对于在树上查找某点的祖先，如果简单的查找时间复杂度是o(n)，那么，我们可以通过倍增算法优化这个时间复杂度，将每次跳一个点变成，每次跳2的i次方个点，也就是倍增优化这个过程，将时间复杂度变为o(logn)。如何进行倍增？首先我们需要进行一遍dfs初始化，处理出每个点的深度。根据深度，初始化fa[now][i]，fa数组存的是now节点的2得i次方倍祖先。这样处理完成后，我们来看树上倍增...
2019-01-16 16:30:01
1728
1
原创 洛谷 工艺 最小/大表示法
最小表示法的是求字符串s的字典序最小的循环同构，最大表示法是求字典序最大的循环同构。循环同构是对于一个字符串，可从字符串串首选择字符，移动到串尾，或者从串尾，平移到串首。以最小表示法为例：对于一个字符串，设两个指针i,j，第一个指向s[0],第二个指向s[1]，并且保证i，j绝对不相同。设一个k，对于s[(i+k)%len]与s[(j+k)%len]有以下三种情况：1、s[(i+k...
2019-01-16 10:48:55
212
原创 树链剖分模板
树链剖分：通过两次dfs，分别对每个节点为根节点的树的节点个数，重点，父亲节点，深度与重链头结点，在线段树上对应的id，每个id对应的原本序列rk，进行初始化。这样就完成了树链剖分。剩下的就是在在剖分过得树上进行求和，更新操作。洛谷p3384#include <iostream>#include <stdio.h>#include <stdlib...
2019-01-11 18:51:05
179
原创 codeforces 558E
计数排序：计数排序就是对于一个已知序列找出序列最大值，最小值后。开辟一个大小为max-min+1的辅助数组，在辅助数组上对已知序列进行计数。即fuzhu[a[i]-min]++。然后再在愿数列上按照一定顺序（降序/升序）进行赋值。for(int i=0,j=0;i<max-min+1;i++)//升序{ if(fuzhu[i]!=0) { a[j+...
2019-01-11 10:59:15
198
转载 codeforce 556E
#include <bits/stdc++.h>using namespace std;map<pair<int,bool>,int>mp;//此题向上吃只与大于等于自己的操作相关.向左吃，只与小于等于x的操作相关//因此用map记录向右向上的操作，每次操作进行二分查找即可int main(){ int n,q; scanf("%d...
2019-01-10 19:45:11
208
原创 区间众数问题，线段树
区间众数，利用线段树，维护区间众数转换的平度序列。线段树记录区间最大值，即为连续区间众数连续个数。平度序列例如：1 1 1 1 2 3 3 3 1 2 3 4 1 1 2 3代码：#include <iostream>#include <algorithm>#include <cmath>#include <cstring&...
2019-01-08 20:27:45
2249
原创 nefu 复读机、分块加二分
有两个操作，1操作，对于x,y区间内的值全部加1。2操作，求出第一次复读y次跟最后一个复读y次的复读机次数。a存复读机原数组，b存分块数组，对于分块数组每个进行排序操作，使区间有序，每次查询对于第一个区间查找到最后一个区间，进行二分查找。 更新时则对两个区间都进行更新。也可对a更新后再对B赋值。#include <iostream>#include <stdio....
2019-01-08 20:07:45
222
转载 牛客网练习赛36 E Rabbit的机器人 思维+二分
转载自牛客网题解：链接：https://ac.nowcoder.com/acm/contest/328/E来源：牛客网 题目描述xxx给Rabbit买了一个机器人，机器人只能在一个直轨道上行走，直轨道由无限多个方格组成，且每个方格按顺序编号，‘0’号方格右侧编号为正，‘0’号方格左侧编号为负。Rabbit可以给机器人一系列‘LR’指令，‘L’和‘R’分别代表让机器人向左走一个方格和...
2019-01-08 19:20:51
244
原创 牛客网练习赛36 Ribbit的数列 分块
题目描述 Rabbit得到了一个长度为N的数列(数列编号从0到N−1)。数列中每个数vali满足1<=vali<=C。初始时数列中每个数均为1，现在Rabbit要对这个数列进行Q次操作，每次操作给出四个数：X Y A B，首先查询数列中值为X的个数P，然后计算出L，R：L=(A+(P+B)2)mod NR=(A+(P∗B)2)mod N并将范围[min(L,R),max(L...
2019-01-08 19:11:02
256
转载 牛客网练习赛36 Rabbit的蛋糕（叉积模板）
转载自牛客网练习赛36题解： #include <cstdio>#include <bits/stdc++.h>#include <map>#include <cstring>#include <algorithm>using namespace std;int n,m;struct node{ doub...
2019-01-08 19:04:16
199
原创 无旋treap树
约定：int ch[maxd][3];//0左儿子，1右儿子int val[maxd];//权值int rnd[maxd];//随机权值int sze[maxd];//以每个点为根树的大小int T,rt,x,y,z;分裂：inline void update(int x){ sze[x]=1+sze[ch[x][0]]+sze[ch[x][1]];}//x为...
2019-01-08 19:01:50
243
原创 nefu 1330 树上求和dfs序+线段树
dfs序即先序遍历树，对于第一个节点进行总结点个数加一并且赋值操作。思路：对于给出的点，进行vecter建树。建树完成后dfs序求出各节点，dfs序，ls[i]表示当前节点的dfs序为多少，rs[i]表示以当前节点为根的子树的最右边节点值。代码：#include <iostream>#include <stdio.h>#include <strin...
2019-01-08 18:55:53
316
转载 nefu1267挑战字符串
因为要求最大美丽值和的子串，不能相互重叠，那么我们记录每个子串的长度dep[i]，在对母串进行字符串匹配时，进行状态转移，ans[i]=max(ans[i],ans[i-dep[i]]+val[i])，这样就能求得最大的答案了。#include <iostream>#include <stdio.h>#include <stdlib.h>#inc...
2019-01-04 19:06:34
162
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人