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