hnust_yangyanjun

分类

大数加法(1) 尺取法(1) 面经(4) 题解(119)

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

A and B and Lecture Rooms 来自专栏

题意：有一颗n个节点的树，有m个询问，每个询问给出x和y两个节点，让你求树上节点到这两个节点距离相等的数目。思路：①：如果x和y深度相同，则他们的最近公共祖先lca（x,y)的非这二个节点方向的节点以外的节点到x和y的距离相等.②：如果x和深度不同，则他们的路径为奇数时无解，为偶数时中点在深度大的...

倍增

2020-11-29

4 647

疫情控制来自专栏

题意：给你一个有n个城市的国家，n-1道路将城市连接（即为树），首都为节点1，有m支军队，每支军队可以在一个城市设立一个检查点，问使从首都到任意一个边境节点都会碰到检查点军队移动最少时间为多少，军队可以同时移动。思路：如果军队数少于与首都直接相连的节点数则输出-1，否则一定有解。我们可以发现时间越...

倍增

2020-11-28

3 885

[AHOI2008]MEET 紧急集合来自专栏

题意：有一颗n个节点的树，现在有m个询问，每个询问给与三个节点，求这三个节点在哪个节点集合时总距离最小？输出集合节点和总距离。思路：我们知道在树上求任意两个节点可以用lca求取，求三个节点怎么转换成求两个节点呢，我们画一颗树然后任找三个点可以发现两两之间的lca的值要么三个相等，此时该点为集合点，...

LCA

2020-11-26

3 801

Tree with Small Distances 来自专栏

题意：给你一颗有n个节点的无向树，你可以往树中加无向边，求你形成1节点到任意一个节点距离小于等于2的图加边的最小次数？思路：你可以认为是求一个变形的最小支配集，即求以1节点为根节点时第0，1，2层无需考虑的最小支配集，所以可以用动态规划和贪心算法解决。代码： #include<bits/s...

最小支配集树状dp

2020-11-19

3 840

Bookshelves 来自专栏

题意：给你一个长度为n的数组，请你按顺序分成k份，然后将每一份的和进行位与操作，求结果最大为多少？思路：从高位到低位枚举结果，即如果加入该位后结果满足条件则将该位加入结果，否则舍弃该位。判断结果是否满足条件使用dp：dp[i][j]表示将前i个数分成j组是否满足条件；dp[i][j]=(dp[i]...

位操作 dp

2020-11-17

3 703

Vitya and Strange Lesson

题意：给你一个长度为n的数组，然后有m次询问，每次询问有一个值x，让数组的每一个值异或x后，求数组中不存在的最小非负整数。思路：先将数组中的元素按01trie树建立，然后每一次查询查询相当于原数组和（当前的值和前面次数的值异或）异或。01trie树上找答案：如果与当前位异或为0的点不存在则输出当...

01trie

2020-11-05

2 547

奶牛异或

题意：给你一个长度为n的序列，让你选择你个连续的子序列做Xor操作求最大值为多少？并且该区间是什么？（如果有多个解，则取右边界最小（第一关键词），区间长度最短（第二关键词））。思路：对数组求前缀异或和，即求[1,2][1,3]....[1,n]等区间的异或和，然后你将二个区间异或后可以发现是一个连...

01trie

2020-11-05

2 534

The XOR Largest Pair

题意：给你n个整数，让你选择两个数进行Xor操作后值最大为多少？思路：建一颗01trie树，从高位到低位，然后从遍历数组，利用01trie树求每一个数与其中某一个一个数Xor的最大值，然后取总的最大值。取法：如果该数在该位上是1则尽可能在01trie树该位取0使其Xor为1。如果该数在该位上是0则...

01trie

2020-11-05

2 610

起床困难综合症

题意：让你选择一个0-m的值，求出在经历n次位操作后最大值为多少？思路：进行位操作时，每一个位的值是独立的，所以我们可以按下列情况进行计算：①：如果该位为0时结果该位为1时该位取0。②：如果该位为0时结果为0且该位为1时结果为1时该位取1。（不超出m的范围，否则取0）③：如果该位为0和1时结果都为...

2020-10-24

6 596

What Goes Up Must Come Down

题意：给你一个长度为n的序列，使序列呈先升序再降序的最少操作次数为多少？每次操作可以交换相邻的两个数。思路：对于每一个数来说，它最终要么左边的数全比它小，要么右边的数全比他小，每次移动相邻两个位置，所以你只需要判断它左边比它大的数的个数和右边比它大的个数的最小值（哪边小与那边大于它的交换），用树状...

树状数组

2020-10-04

2 755