hnust_yangyanjun

题解

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

/ 注册

全部文章 / 题解（共3篇）

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