xianggl
xianggl
全部文章
题解
学习笔记(3)
游记(1)
翻译(1)
归档
标签
去牛客网
登录
/
注册
xianggl的博客
全部文章
/ 题解
(共10篇)
[题解]CF827D Best Edge Weight
题目描述给定一个点数为,边数为,权值不超过的带权连通图,没有自环与重边。现在要求对于每一条边求出,这条边的边权最大为多少时,它还能出现在所有可能的最小生成树上,如果对于任意边权都出现,则输出。 () 建出最小生成树讨论这条边在不在最小生成树上 若不在 那么在这条链上应该有边比它小,所以等于链上最大...
2021-08-26
0
261
[题解]BJOI2014大融合
题目描述小强要在个孤立的星球上建立起一套通信系统。这套通信系统就是连接个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的询问。 离线在查询的时候,如果我们...
2021-08-25
0
316
[题解]HNOI2016序列
题目描述给定长度为的序列:,记为。类似地,是指序列:。若,则称是的子序列。现在有个询问,每个询问给定两个数和,,求的不同子序列的最小值之和。例如,给定序列,询问给定的两个数为和,那么有个子序列,这个子序列的最小值之和为。 一个技巧:取最小数先取区间的最小值,设下标为首先对于左端点,右端点的区间,最小...
2021-08-20
1
423
[题解]HNOI2016 day1最小公倍数
问题描述给定一张个顶点条边的无向图(顶点编号为),每条边上带有权值。所有权值都可以分解成的形式。 现在有 个询问,每次询问给定四个参数和,请你求出是否存在一条顶点到之间的路径,使得路径依次经过的边上的权值的最小公倍数为。 注意:路径可以不是简单路径。 注意到不一定是简单路径,所以我们看联通性即可也...
2021-08-19
0
422
逆序对
链接:https://ac.nowcoder.com/acm/problem/14731来源:牛客网题面求所有长度为的串中满足如下条件的二元组个数:设第i位和第j位分别位和(),则。 答案对取模。 考虑一对和在多少情况下可以出现,即是这对和的贡献 钦定两个位置,剩下随便选,再考虑钦定哪两个位置, 相...
2021-02-17
0
473
Xorto
链接:https://ac.nowcoder.com/acm/problem/14247来源:牛客网 题目描述给定一个长度为的整数数组,问有多少对互不重叠的非空区间,使得两个区间内的数的异或和为。 ,。 两个区间异或和为,则分别的异或和相等为了避免重复,我们对于,查询和构成的区间与前所有区间的方案数...
2021-02-07
0
443
Treepath
链接:https://ac.nowcoder.com/acm/problem/14248来源:牛客网 题目描述给定一棵个点的树,问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。到与到被视为同一条路径。路径的起点与终点不能相同。 是偶数,所以只要为偶数即可于是预处理所有,即到根的距离最后...
2021-02-07
0
403
NC19427 换个角度思考
把问题看作,即需要分别求出两项的值,令前一项为sumr,后一项为suml;用指针,确保记录时所有的数均在[1,r]或[1,l-1]范围内,即可对值域查询;于是将问题离线,第一步用左端点升序排序;当指针j==q[i].l时,记录suml[q[i].id]=getsum(x),否则在值域中添加a[j];...
2020-05-04
1
555
HAOI2015 树上操作
做的时候经验不够,没有想到一种类似于差分的思想观察操作:操作一:单点修改,对子树影响:所有子树节点到根路径加a操作二:子树所有节点增加a,可以看作先将所有节点到根的总权值加上a * dep[u],再减去a * (dep[x]-1),数据结构维护一下即可操作三:直接查询 Code: #include&...
2020-05-02
0
523
[黑科技]用线段树写平衡树板题
Code: #include<bits/stdc++.h> using namespace std; struct segmenttree { int l,r,cnt; }sgt[8*100000+5]; struct option { int op,x; }opt[10...
2020-05-02
0
641