博客

题目

给定一个长度为 n 的数列A1​,A2​,⋯,An​ 和一个非负整数 x, 给定 m 次查 询, 每次询问能否从某个区间[l,r] 中选择两个数使得他们的异或等于 x 。

输入格式

输入的第一行包含三个整数n,m,x 。

第二行包含 n 个整数A1​,A2​,⋯,An​ 。

接下来 m 行，每行包含两个整数 li​,ri​ 表示询问区间 [li​,ri​] 。

输出格式

对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。

思路

a^b=x, a^x=b.异或在python中是^符号，返回异或结果（十进制）。最开始我肯定是暴力取解题，很明显只能通过一部分用例（对了2个） 。但是好奇怪 有两个用例是答案错误，并不是超时，搞不明白！我又不是面向结果编程，怎么老是有这种问题。

去看了一下题解，就是会多增加一个数组，去记录离当前数最大的一个符合条件的数。（感觉也不是这样 就我也表示不清楚）。

代码

import os
import sys

# 请在此输入您的代码
n, m, x = map(int, input().split())
data = [0] + list(map(int, input().split()))
search = []
for i in range(m):
  search.append(list(map(int, input().split())))

mp = {} #感觉就是记录每个值及其下标 用来对另一个数进行查找下标
g = [0]*(n+1) # 标记离当前下标最大（也就是离最近的下标） 可以与该下标对应的数异或=x 或者可以与前面某个数异或为x

for i in range(1, n+1):
  b = data[i] ^ x #b可以与data[i]异或得到x
  if mp.get(b): # 如果b在前面 则得到b的下标
    g[i] = max(g[i-1], mp[b]) # 选取最大的下标进行记录
  else:
    g[i] = max(g[i-1], 0)
  mp[data[i]] = i

out = ''
for i in search:
  l,r = i[0], i[1]
  if l <= g[r]:
    out += 'yes' + ' '
  else:
    out += 'no' + ' '
print(out.replace(' ', '\n'))

 

我的垃圾代码

import os
import sys

# 请在此输入您的代码
n, m, x = map(int, input().split())
data = list(map(int, input().split()))
search = []
for i in range(m):
  search.append(list(map(int, input().split())))

out = ''
for i in search: # 如果存在两个数异或是x 则x与某个数异或得到的就是另一个数 因此用x取跟每一个数进行异或 判断结果是否在区间中
  flag = True
  for j in data[i[0]-1:i[1]]:
    temp = j^x
    if temp in data[i[0]-1:i[1]]:
      flag = False
      out +='yes' + ' '
      break
  if flag == True:
    out += 'no' + ' '
print(out.replace(' ', '\n'))