- 博客(169)
- 收藏
- 关注
RSS订阅原创 CF600E(dsu on tree)
题意:给你一棵n个点的有根树，以1为根，每个点有一个颜色。对于一颗以v为根的子树，其出现次数最多的颜色，为dominating顶点v这个子树的颜色，可能有多个这样的颜色。求以n个顶点分别为根的子树中，dominating 的颜色和。思路：一个很好想的暴力思路就是，dfs n个点，统计该点为根的子树中出现的颜色次数。时间、空间都是O(N^2)的。我们可以每次统计完一个点后清空cnt数组...
2019-11-21 16:55:42
240
原创 树链剖分模板
//test 洛谷模板题#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> piir;const int maxn = 1e5+5;int n,m,r,mod;ll wt[maxn],w[maxn];struct node{ i...
2019-11-18 23:39:26
177
原创 2018牛客国庆集训派对Day6 I 清明梦超能力者黄YY(树链剖分)
传送门题意：中文思路：既然求倒数第k次染为什么颜色，那就倒着染色，染到第k次就标记下。所以我们可以用线段树来维护每个点被更新的次数，维护一条链上的节点被更新过的次数的最大次数。当一个区间的最大被更新次数超过k时，我们再暴力往下去找具体区间，对答案进行更新，对一个节点的答案更新完之后就将其的值设为负无穷大。由于每个点算答案的时候都只会被算到一次，所以整体的复杂度应该是 O(n*logn*l...
2019-11-18 23:36:59
135
原创 2018 ICPC shenyang online J KaChang(分块+dfs序+BIT)
题意：给你一颗根节点为1(深度为0)的树，初始每个节点的point为0。给定两种操作1 l x 将所有深度为l的节点point+x。 2 x 输出以x为根的子树的point和。思路：1操作很难搞啊！分块按每一层的节点个数分类讨论，设阈值为T。对于操作1，当第L层的节点个数SizeL<T时，枚举L层的所有节点，维护其对答案的贡献即可(BIT)。当L层的节点数Siz...
2019-11-16 15:40:12
188
原创 Codeforces 1257F MakeThemSimilar(Meet-in-the-middle+Trie(hash|map))
老套路了，可我DFS挂了。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e3+5;const int maxnode= 3300005;int n;int a[maxn];int mp[maxn][32];int bit[maxn],b[m...
2019-11-16 12:38:05
194
原创 Codeforces 1095F(Kruskal+Greed)
https://codeforces.com/contest/1095/problem/F题意给定n个点，每个点都有权值wt[i]，点u和点v建一条边的代价是wt[u]+wt[v]。有m条特殊边其权重直接为w，可选可不选。求联通n个点所需的最小代价。思路想复杂了，n^2建图显然是不可能的。不考虑特殊边的情况下，必然是权重最小的点与其他所有点建立n-1条边，然后再加入m条特殊边，跑一...
2019-11-15 23:48:21
168
原创 树链剖分模板
测试题目P3384 【模板】树链剖分#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> piir;const int maxn = 1e5+5;int n,m,r,mod;ll wt[maxn],w[maxn];//点权struct...
2019-11-15 12:34:13
137
原创 洛谷P2580 于是他错误的点名开始了(Trie树板子)
字典树空间一般开n*maxLen(n为字符串数量，maxLen为字符串最大长度，最大情况n个串都不相同)#include<bits/stdc++.h>using namespace std;const int maxnode = 5e5+5;//n*maxlenconst int maxn = 5e3+5;int trie[maxnode][26],val[maxnode...
2019-11-06 23:57:41
157
原创 2019CCPC-Harbin E(拓扑排序)
Note:T很大，初始化就容易超时。#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,ll> piir;const int maxn = 1e6+5;vector<int> s[maxn];vector<int> G[...
2019-11-03 18:28:29
287
原创 牛客假日团队赛19 D-Chocolate Milk(拓扑排序+树)
传送门思路：给每个入度为零的点一些流量，其流量等于该点的出度值。然后拓扑排序，如果某个点的流量等于全部流量，即为答案点(除起点)。因为题目给的是一颗树，所以不用考虑流量分流后在聚集到一点上。也就是说，除入度为零的点以外，出度大于1的点及其后面的点都不会是答案。#include<bits/stdc++.h>using namespace std;typedef pai...
2019-11-01 14:32:29
169
原创 2016第十二届湖南省赛 B-有向无环图(拓扑排序)
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 5;const int mod = 1e9+7;ll a[maxn],b[maxn];vector<int> G[maxn];queue<int> q;int in...
2019-10-31 15:07:02
159
原创 UVA - 10305 Ordering Tasks (拓扑排序)
水题#include<bits/stdc++.h>using namespace std;typedef pair<int,int> piir;typedef long long ll;const int maxn = 1e2+5;const int INF = 0x3f3f3f3f;int n,m;int in[maxn];vector<i...
2019-10-31 15:06:37
105
原创 UVALive - 4255(拓扑排序+构造)
传送门思路：连续和转化为前缀和之差。可以将问题转化为已知序列 a1,a2,...,an 的大小关系，求出任意一组满足条件的序列。拓扑排序即可。我是以sum大指向sum小的方向建边。假设入度为零的点即最大值点的值为0，那么后面的点比它小就小1。注意sum[0]=0，0也要跑。#include<bits/stdc++.h>using namespace std;typ...
2019-10-31 13:54:28
135
原创 UVA11624 Fire! (BFS)
思路：两遍BFS即可,先跑Fire，再跑J。貌似写过stp数组没有考虑初始INF！#include<bits/stdc++.h>using namespace std;typedef pair<int,int> piir;typedef long long ll;const int maxn = 1e3+5;const int INF = 0x3f3f...
2019-10-31 12:59:55
111
原创 区间贪心
51nod1091 线段的重叠#include<bits/stdc++.h>using namespace std;const int maxn = 5e4+5;struct node{ int l,r;}a[maxn];bool cmp(node a,node b){ if(a.l==b.l) return a.r>b.r; re...
2019-10-25 18:06:54
80
原创 Gym-101741C Cover the Paths(LCA贪心)
传送门题意：给你一颗n个结点的无向树，然后给你m条路径（a, b），让你求最小的点集，满足这些路径上至少有一点在这个点集上。输出点集的大小和点。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5+5;int n,m;vector<int>...
2019-10-25 16:24:27
261
1
原创 「BZOJ1483」[HNOI2009] 梦幻布丁 (启发式合并)
传送门这题没有数据范围可怎么写啊！#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll setoff = 1e9;const int maxn = 1e6+5;vector<int> v[maxn];int f[maxn],c[maxn],ans,n,m;//...
2019-10-22 22:54:20
138
原创 Codeforces 161D Distance in Tree(点分治)
题意：求distance(u,v)==k的点对数。思路：统计距离root距离之和为k的对数-距离root儿子节点中距离儿子节点距离之和为k-2的对数。因为每对算了两边除二即可。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e6+5;const int...
2019-10-10 22:34:07
183
1
原创 点分治
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 1e5+5;/* sz[x] 表示以x为根的子树的size使多少 son[x]表示x的儿子中size最大的是 rt 是我们要找的重心 all 当前子...
2019-10-10 22:27:15
90
原创 __int128
void scan(__int128 &x){ x = 0; int f = 1; char ch; if((ch = getchar()) == '-') f = -f; else x = x*10 + ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ...
2019-10-05 23:19:49
127
原创 2018 Hunan province E
动态开点#include <bits/stdc++.h>using namespace std;typedef pair<int,int> piir;typedef long long ll;const int maxn = 1e6+5;const int INF = 0x3f3f3f3f;int sum1[maxn],ls1[maxn],rs1[max...
2019-10-05 10:29:29
94
原创 2019牛客国庆day4 (2017湘潭 H) 树的直径
#include <bits/stdc++.h>using namespace std;typedef pair<int,int> piir;typedef long long ll;const int maxn = 1e5+5;const int INF = 0x3f3f3f3f;int n;bool vis[maxn];ll dist1[maxn],di...
2019-10-05 09:53:24
126
原创 2019 Shanghai Online Substring
传送门题意给定一个主串S，m个模式串T，问主串中有多少个字串与模式串T比配这里的匹配指首尾字符相同，中间部分可以乱序(可以理解为相同字母个数相同)。思路整体思路就是，将T个模式串按照长度排序，相同长度的模式串一起处理。对于每一种长度len，求一次主串S长度为len的子串哈希值。考虑到空间问题，我们只存储有贡献的子串，即出现过的。赛时维护的位置前缀和应该是会冲突的，所以这里用哈希和来维...
2019-09-20 18:49:17
126
原创 GDKOI2016Day1T1-魔卡少女
题目描述君君是中山大学的四年级学生。有一天在家不小心开启了放置在爸爸书房中的一本古书。于是，君君把放在书中最上面的一张牌拿出来观摩了一下，突然掀起一阵大风把书中的其她所有牌吹散到各地。这时一只看上去四不像的可爱生物“封印之兽”可鲁贝洛斯从书中钻了出来，它告诉君君书中的牌叫“库洛牌”，现在散落各地已实体化，要君君将它们全部再次封印起来，以免危害世界，于是君君开始过上了收服“库洛牌”的旅程。经...
2019-09-11 15:49:47
173
原创 51Nod 1391 01串(思维+前缀和)
传送门题意：思路：预处理出每个点向左和向右分别最远能扩展多远。处理完后O(n)扫一遍串即可。很常规的0->-1,1->1维护一个【0,i】的前缀和cur，当cur<0表示[0,i]区间0的个数大于1的个数，即当前长度为最长的，否则判断cur+1是否出现过，如果cur+1这个数值没有出现过，则向左扩展最大长度为0，如果曾经出现过，则两点间的串0比1多，因为有前缀和可知，...
2019-09-11 15:08:38
146
原创 Dinic模板
#include<bits/stdc++.h>#define mk make_pairusing namespace std; typedef long long ll;const double PI = acos(-1.0);const double eps = 1.0e-8;const int INF = 0x3f3f3f3f;const int maxn = 1...
2019-09-06 22:04:34
87
原创 牛客练习赛4 A-Laptop(二维偏序)
传送门题意：求思路：很老的题目，一维排序，二维BIT，离散搞一下。#include<bits/stdc++.h>using namespace std;const int maxn = 1e5+5;int n;struct unt{ int m,s;}bk[maxn];bool cmp(unt a,unt b){ return a.m < b.m;...
2019-09-02 21:21:18
237
原创 后缀数组(Suffix Array)
前言SA是一种解决多模板匹配问题的算法。大致就是将后缀处理出来然后按照字典序排个序。时间主要浪费在排序上。sa数组sa[i]表示rk为i的后缀的开始位置。rk数组rk[i]表示以i位置开始的后缀的rank为多少。基数排序先排个位，然后十位依次往下，稳定算法。模板const int N = 1e6 + 5; // 开二倍吧int sa[N], rk[N], Height...
2019-08-24 17:29:42
235
原创 POJ 2559Largest Rectangle in a Histogram(单调栈入门)
题意：见标题思路：维护一个单调递增栈，遍历[0,n-1] 遇到a[i]>a[s.top()]直接入栈，否则计算矩形面积。#include<cstdio>#include<stack>using namespace std;typedef long long ll;const int maxn = 1e5+5;stack<int> st...
2019-08-15 10:51:25
86
原创 曼哈顿距离和切比雪夫距离转换
设平面空间内存在两点，它们的坐标为(x1,y1) (x2,y2)曼哈顿距离dis=|x1−x2|+|y1−y2|，即两点横纵坐标差之和。切比雪夫距离dis=max(|x1−x2|,|y1−y2|)，即两点横纵坐标差的最大值。两者之间的关系两者的定义看上去好像毛线关系都没有，但实际上，这两种距离可以相互转化！我们考虑最简单的情况，在一个二维坐标系中，设原点为(0,0)如果用曼哈顿距离...
2019-08-12 16:48:07
585
原创 2019牛客暑期多校训练营（第八场）D-Distance(三维BIT | 时间分治)
题意：思路：将曼哈顿距离去绝对值的8种情况分别用BIT维护。暴力讨论比较最小值。 BIT维护把每个点拆掉绝对值后的8种贡献。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 3e5+5;const double eps = 1e-10;const in...
2019-08-12 15:56:13
276
原创 SPOJ3267 DQUERY (主席树 求区间内不同数的个数 )
题意：给定一个含有n个数的序列，有q个询问，每次询问区间[l,r]中不同数的个数。思路：从左向右一个一个将该数字处在的位置添加到主席树中如果该数字前面未出现过，则在此版本的线段树中的该条链加1，如果该数字已经出现过了，则在此版本线段树的上次出现位置减1，再在此版本线段树的该位置加1，这样就能保证区间不重复计算。#include<bits/stdc++.h>...
2019-08-08 17:49:18
231
原创 POJ2777 Count Color
题意：一段区间从1-n的初始颜色为1，每次进行两种操作1，C a b c 把[a,b]这个区间染成颜色c。2，P a b查询[a,b]区间内有多少种颜色。思路：首先题目保证染色的颜色数少于30种这是关键。我们需要将30种颜色的有无与否都存在线段树的结点上，这样一来每个结点都要存储30个bool值，空间太浪费，而且在计算合并操作的时候有一步30个元素的遍历，大大降低效率。因为题目...
2019-08-07 21:16:59
146
原创 主席树入门
第k小#include<cstdio>#include<vector>#include<algorithm>#include<iostream>using namespace std;const int maxn = 1e5+5;int cnt,root[maxn],a[maxn];//root[i] 第i课线段树根节点的位置 ...
2019-08-07 17:14:45
196
原创 欧拉函数入门
What is Euler function对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。例如φ(8)=4，因为1,3,5,7均和8互质。性质：若n是素数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质 。 欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n) phi(p)=p-...
2019-07-16 17:22:20
176
原创 PC的机器设备 dijkstra最短路径
I. PC的机器设备描述HenuACM团队的PC同学设计出一种节能的机器设备。它的内部结构是由 N 个齿轮组成。整个机器设备有 一个驱动齿轮，当启动它时，它立即按 10,000 圈/小时转速顺时针转动，然后它又带动与它相切 的齿轮反方向，即逆时针转动。齿轮之间互相作用，每个齿轮都可能驱动着多个齿轮，最终带动 一个工作齿轮完成相应的任务。 在这套设备中，记录了每个齿轮的圆心坐标和齿轮半径。已...
2019-06-06 19:33:01
263
4
原创 LightOJ - 1341 Aladdin and the Flying Carpet 唯一分解定理
题意：a*b=S,给S 和一条边的最小长度，求多少种组合有一个矩形的毯子，已知它一定不是正方形，并且已知最短边和毯子的面积，求这个毯子可能有多少种形状。分析：首先，如果最短的边大于等于面积的平方根，两个大于面积平方根的边不可能组成面积等于给定面积的矩形。所以这种情况是0. 然后最短边的范围就变成了1-1e6，问题也变成了在最短边（min_side）到面积(area)这些数中有多少对不...
2019-06-06 18:59:14
244
原创 PTA 古风排版 （25 分）
古风排版（25 分）中国的古人写文字，是从右向左竖向排版的。本题就请你编写程序，把一段文字按古风排版。输入格式：输入在第一行给出一个正整数N（<100），是每一列的字符数。第二行给出一个长度不超过1000的非空字符串，以回车结束。输出格式：按古风格式排版给定的字符串，每列N个字符（除了最后一列可能不足N个）。输入样例：4This is a test case...
2019-06-06 18:48:25
315
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人