linbinwu
linbinwu
全部文章
分类
题解(5)
归档
标签
去牛客网
登录
/
注册
linbinwu的博客
全部文章
(共5篇)
2020牛客多校第四场A题 Ancient Distance dfs序+线段树+k级祖先
A题 Ancient Distance 题意 个点以点为根的树,在树上确定个关键点,每个点的权值为点与点到根节点上碰到的第一个关键点的距离(若路径上没有关键点, 那么权值为),答案为所有点中最大权值的最小值。现在求的答案之和 题解 题意比较难理解,看看样例应该能懂考虑已经确定答案的情况下,最少需要多...
dfs序
线段树
k级祖先
2020-07-22
10
716
2020牛客多校第二场A题 All with Pairs Hash+KMP
All with Pairs 题意 记为最大的使得给个串,求 题解 统计所有串每一个后缀出现次数,这个可以用哈希来实现 map<ull, int> mp; void insert(string &s) { ull hash = 0, b = 1;//unsigned lo...
2020-07-16
3
751
2020牛客多校第二场E题 Exclusive OR FWT
Exclusive OR 题意 个数, 求从中取出个数的最大异或和,输出的答案 题解 FWT:这是一个卷积的形式,只不过平常的卷积运算符是我们用记录中是否出现那么代表的含义就是 选取两个数的异或值为的种数 同理,代表的含义为 在选取了个数能得到的异或和数中选取一个,在初始数字中选取一个, 使得...
2020-07-16
8
751
2020牛客多校第一场D题 Quadratic Form 拉格朗日乘子
Quadratic Form 题意 , 为的正定二次型,为的列向量求满足求,的最大的值 题解 带有不等式约束条件解极值问题, 使用拉格朗日乘子法设拉格朗日函数由KKT条件有 , 若 则 , 因此令由, 得 则 又 最终有 代码 #include<bits/stdc++...
2020-07-16
5
753
2020牛客多校第一场 B Infinite Tree 虚树
Infinite Tree 题意 一颗无限结点的树,任意大于的点与点相连,其中为的最小质因子记为树上之间的距离,求 题解 不考虑本题的树 我们先考虑这个题在已经知道树的结构下怎么解显然在的树中,假设现在,那么当前答案记,那么在图中,显然现在考虑当我们的点转移到的一个子节点时,答案会发生什么变化那么就...
2020-07-15
17
1554