异或运算的最大值

  • Z时代
  • 2024-01-10
  • 分类：问答

我想到了这个问题。

有一种加密算法广泛使用按位XOR操作。该加密算法使用一系列非负整数x 1，x 2，… x

n作为密钥。为了有效地实现此算法，Xorq需要找到给定整数a，p和q的（a xor x j）最大值，以使p <= j <= q。帮助Xorq实现此功能。

输入项

输入的第一行包含一个整数T（1 <= T <= 6）。随后是T测试用例。

每个测试用例的第一行都包含两个整数N和Q，它们之间用一个空格分隔（1 <= N <= 100,000； 1 <= Q <=

50,000）。下一行包含N个整数x 1，x 2，… x n，它们之间用单个空格分隔（0 <= x j

<215）。接下来的每条Q行描述一个查询，该查询由三个整数a i，p i和q i（0 <= ai <215，1 <= p i <= q i <=

N）组成。

输出量

对于每个查询，打印的最大值（我 XOR X Ĵ）使得P 我 <= j的<= Q 我在单行中。

样本输入

1
15 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10
1023 7 7
33 5 8
182 5 10
181 1 13
5 10 15
99 8 9
33 10 14

样本输出

13
1016
41
191
191
15
107
47

说明

First Query (10 6 10): x6 xor 10 = 12,
    x7 xor 10 = 13, x8 xor 10 = 2, x9 xor 10 = 3, x10 xor 10 = 0,
    therefore answer for this query is 13.
Second Query (1023 7 7): x7 xor 1023 = 1016,
    therefore answer for this query is 1016.
Third Query (33 5 8): x5 xor 33 = 36, x6 xor 33 = 39,
    x7 xor 33 = 38, x8 xor 33 = 41, therefore answer for this query is

41.

Fourth Query (182 5 10): x5 xor 182 = 179,

x6 xor 182 = 176, x7 xor 182 = 177, x8 xor 182 = 190,

x9 xor 182 = 191, x10 xor 182 = 188,

therefore answer for this query is 191.

我首先通过使给定范围内的数字长度（以二进制表示）相等，然后将’a’与特定的xj值进行比较来进行尝试，但这是时间的浪费。Java中的最大时间限制为5秒。

回答：

我没有详细介绍您的代码，但您似乎在r = p-1的范围内有循环；r <q-1; r ++，而不必执行此操作会很好。

给定ai，我们希望找到给定范围内的xi值，其最高位尽可能多于ai的倒数。一切都在0到2 ^ 15之间，因此不必担心太多事情。对于n =

1到15，您可以根据xi的n个最高位将xi分成几部分，因此将其分为2、4、8、16 ..

32768部分。对于每一部分，请按照找到可能位置的位置的顺序排列一个列表，因此对于最高位，您将有两个列表，其中一个给出位模式为0的位置.........

.....并给出位模式为1的位置.............对于每个三元组，您可以在特定部分上使用二进制印章来查找其中是否有任何位置您要查找的前n位具有位模式的范围。如果有，那就很好。

设置成本是在xi上进行15次线性传递，这可能比您读入它所需的时间要少。对于每一行，您可以进行15次二元运算，以查看xi的哪个值与前n位匹配，并修改如果您无法匹配特定的位，则寻找的高位模式。

我认为，如果通过将问题代码作为单独的子例程来将I /

O与问题代码分开，则您的程序会更清晰。这样也可以更轻松地将问题代码的一个版本与另一个版本进行比较，以查看哪个版本更快，以及它们是否都得到相同的答案。

以上是 异或运算的最大值 的全部内容， 来源链接： utcz.com/qa/428040.html

回到顶部