xianggl
xianggl
全部文章
分类
学习笔记(3)
游记(1)
翻译(1)
题解(10)
归档
标签
去牛客网
登录
/
注册
xianggl的博客
全部文章
(共15篇)
[题解]CF827D Best Edge Weight
题目描述给定一个点数为,边数为,权值不超过的带权连通图,没有自环与重边。现在要求对于每一条边求出,这条边的边权最大为多少时,它还能出现在所有可能的最小生成树上,如果对于任意边权都出现,则输出。 () 建出最小生成树讨论这条边在不在最小生成树上 若不在 那么在这条链上应该有边比它小,所以等于链上最大...
2021-08-26
0
258
[题解]BJOI2014大融合
题目描述小强要在个孤立的星球上建立起一套通信系统。这套通信系统就是连接个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的询问。 离线在查询的时候,如果我们...
2021-08-25
0
315
[题解]HNOI2016序列
题目描述给定长度为的序列:,记为。类似地,是指序列:。若,则称是的子序列。现在有个询问,每个询问给定两个数和,,求的不同子序列的最小值之和。例如,给定序列,询问给定的两个数为和,那么有个子序列,这个子序列的最小值之和为。 一个技巧:取最小数先取区间的最小值,设下标为首先对于左端点,右端点的区间,最小...
2021-08-20
1
422
[题解]HNOI2016 day1最小公倍数
问题描述给定一张个顶点条边的无向图(顶点编号为),每条边上带有权值。所有权值都可以分解成的形式。 现在有 个询问,每次询问给定四个参数和,请你求出是否存在一条顶点到之间的路径,使得路径依次经过的边上的权值的最小公倍数为。 注意:路径可以不是简单路径。 注意到不一定是简单路径,所以我们看联通性即可也...
2021-08-19
0
419
[学习笔记]Kruskal重构树
考虑算法 for(ri i=1;i<=m;i++) { int x=getfather(e[i].x),y=getfather(e[i].y); if(x!=y) { father[y]=x; ans+=e[i].x; } }我们这样做可...
2021-08-17
0
295
[学习笔记]树链剖分
树链剖分,就是把树上的边划分,然后用数据结构维护的算法 重链剖分:轻边与重边 百度百科的图一个节点子树中节点数最多的节点叫做它的重儿子,与它相连的边称为重边多条重边连起来成为重链我们把重链连续标号,用数据结构维护,即把树上问题转化成了序列上问题,每一个对应了一个节点记为的重儿子,为的深度,为所在重链...
2021-07-30
0
331
[学习笔记]线段树合并
线段树合并,顾名思义就是把两棵线段树合并在一起,将两棵树信息相加复杂度证明:自己想的证明设添加入各棵线段树的总点数为考虑一条链,长度为,那么合并这条链的复杂度为总复杂度=因为等于所以复杂度为 例题 天天爱跑步https://www.luogu.com.cn/problem/P1600小同学认为跑步...
2021-07-29
0
551
Codeforces Round #705 (Div. 2) D GCD of an Array
D GCD of an Array 题目描述 你有一个长度为的数组.你需要处理个操作,格式是:输入两个数和,将乘以.每次操作之后,你需要输出数组所有元素的GCD.因为答案可能很大,所以模再输出 输入 第一行由两个整数组成:和第二行由个整数组成 ——操作前的数组的元素接下来q行是操作,每行输入两个整数...
2021-03-09
0
423
逆序对
链接:https://ac.nowcoder.com/acm/problem/14731来源:牛客网题面求所有长度为的串中满足如下条件的二元组个数:设第i位和第j位分别位和(),则。 答案对取模。 考虑一对和在多少情况下可以出现,即是这对和的贡献 钦定两个位置,剩下随便选,再考虑钦定哪两个位置, 相...
2021-02-17
0
470
Xorto
链接:https://ac.nowcoder.com/acm/problem/14247来源:牛客网 题目描述给定一个长度为的整数数组,问有多少对互不重叠的非空区间,使得两个区间内的数的异或和为。 ,。 两个区间异或和为,则分别的异或和相等为了避免重复,我们对于,查询和构成的区间与前所有区间的方案数...
2021-02-07
0
439
首页
上一页
1
2
下一页
末页