蓝桥杯2022年第十三届省赛真题-选数异或

解题思路:

输入所需数据，分别用两组数组存储数列和检查值。

check方法的逻辑是：创建一个HashSet对象set，遍历数组a的指定范围[l, r]，对于每个元素a[i]，检查set中是否已经存在一个元素与a[i]异或后等于x。如果存在，则返回true；否则，将a[i]添加到set中。如果遍历完整个范围都没有找到满足条件的元素对，则返回false。

注意事项:

例：a^a=0,b^0=b;
在遍历到元素a[i]时，计算x与a[i]的异或结果，然后检查这个结果是否已经在HashSet中。如果存在，说明之前有一个元素a[j]（其中j < i）满足a[j] ^ a[i] = x，因此返回true。否则，将a[i]添加到HashSet中，继续遍历。

a[j]^a[i]=x——>x^a[i]=a[j]^a[i]^a[i]=a[j]

参考代码：
import java.util.HashSet;
import java.util.Scanner;
public class caiYao {
       public static void main(String[] args) {
              Scanner sc=new Scanner(System.in);
              int n=sc.nextInt();
              int m=sc.nextInt();
              int x=sc.nextInt();
              int[] a=new int[n];
              String[] b=new String[m];//用来存储检查后的值
              for (int i = 0; i <a.length ; i++) {
                       a[i]=sc.nextInt();
               }
               for (int i = 0; i < m; i++) {
                       int l=sc.nextInt()-1;//减一代表数组序号
                       int r=sc.nextInt()-1;
                       b[i]=(check(a,l,r,x)?"yes":"no");//将布尔值切换为所需值
               }
               sc.close();
               for (String i:b) {
                       System.out.println(i);
               }
       }
           public static boolean check(int[] a,int l,int r,int x){
                   HashSet<Integer> set=new HashSet<>();//使用HashSet来减少时间复杂度

                       for (int i = l; i <= r; i++) {
                           if (set.contains(a[i]^x)){       //set.contain(H) 检查set中是否含H
                                   return true;
                           }
                            set.add(a[i]);
                     }
                       return false;
               }

//下面是未优化的方法

/*

public static boolean check(int[] a, int l, int r, int x) {  

          for (int i = l; i <= r; i++) {      

              for (int j = i + 1; j <= r; j++) {           

                     if ((a[i] ^ a[j]) == x) {            

                        return true;     }     

               }     

           } return false;  

          }

*/

}