异或密码

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 898    Accepted Submission(s): 297 Problem Description 晨晨在纸上写了一个长度为N的非负整数序列{ ai }。对于这个序列的一个连续子序列{ al,al+1,…，ar }晨晨可以求出其中所有数异或的结果  alxoral+1xor...xorar 其 中xor表示位异或运算，对应C、C++、 Java等语言中的^运算。 小璐提出了M个询问，每个询问用一个整数  xi 描述。 对于每个询问，晨晨需要找到序列{ ai }的所有连续子序列，求出每个子序列异或的结果，找到所有的结果中与  xi 之差的绝对值最小的一个，并告诉小璐相应子序列的长度。 若有多个满足条件的连续子序列，则告诉小璐这些子序列中最长的长度。   Input 包含多组测试数据，第一行一个正整数T，表示数据组数。 每组数据共两行。 第一行包含N+1个非负整数。其中第一个数为N，表示序列的长度；接下来N 个数，依次描述序列{  ai }中的每个数。 第二行包含M+1个整数。其中第一个数为M，表示询问的个数；接下来M个数  xi ，每个数对应题目描述中的一个询问。 保证 1 <= N <= 100，1 <= M <= 100， ai  <= 1024，| xi | <= 1024，数据组数 <= 100。   Output 对于每组数据输出M + 1行。前M行对应晨晨M个询问的回答，第M + 1行为空行   Sample Input 2 2 1 1 2 0 2 3 1 2 4 3 10 5 1   Sample Output 2 1 3 2 1   这道题是我做二分搜索的专题的时候出现的一道题，一开始怎么都不懂它要干嘛，总之它就是一道二分题。 题意 ： 输入一串数组，然后把它的所有连续子串通过异或运算得到结果，然后输入一个数，找到异或结果中与这个数的差值的绝对值最小的那个数，也就是最接近的数。 所以我们对输入进来的数应该进行预处理。 对于输入进来的数，先把它的长度初始化为1，然后把它向前与前面的连续子串进行异或，并且把答案存于一个数组的下标，数组的值存子串长度 输入了要查找的值后，用left 和 right 向两边查找，找到了值后对比距离，距离相同则对比长度，若一边找不到则直接输出另一边的值 上 AC代码： #include<stdio.h> #include<string.h> int num[5000]; int main(){ int n,m,z,list[105],k,len,gg; while(scanf("%d",&n) != EOF){ while(n--){ scanf("%d",&m); memset(num,0,sizeof(num)); //用来存一个结果的连续字串里面的元素个数 for(int i = 0;i < m;i++){ scanf("%d",&list[i]); k = list[i]; if(num[k] == 0) num[k] = 1; // 对这个数进行初始化 len = 1; for(int j = i - 1;j >= 0;j--){ len++; // len 表示这个字串的长度 k ^= list[j]; // 把这个数之前的所有数的（第n个数，有（n - 1)！个字串 进行异或 if(len > num[k]){ //每次只更新更长的那个子串 num[k] = len; // 把异或的结果 K存为数组下标，数组内容为子串长度 } } } scanf("%d",&z); for(int i = 0;i < z;i++){ scanf("%d",&gg); int l,r,lFlag = 0,rFlag = 0; l = r = gg; // 二分搜索，初始值为 输入要找的那个值 从该值向两边进行搜索 while(num[l] == 0){ // l向左边延伸 l--; if(num[l] != 0) //若找到了值 结束搜索 if(l < 0){ // 若 l已经小于0了，即找不到结果，令lFlag = 1然后结束搜索 lFlag = 1; break; } } while(num[r] == 0){ //同上一样的操作 r++; if(num[r] != 0) if(r > 5000){ // 大于了5000，数据原因大概超过5000那么大的数也是找不到值了，令rFlag = 1 rFlag = 1; break; } } if(rFlag){ //如果右边找不到，那么输出左边的 printf("%d\n",num[l]); }else if(lFlag){ //如果左边找不到，那么输出右边的 printf("%d\n",num[r]); }else{ if(gg - l < r - gg){ // 如果两边都找到了 那么就输出 与该数值更接近的那个 printf("%d\n",num[l]); }else if(gg - l> r - gg){ printf("%d\n",num[r]); }else{ if(num[r] < num[l]) // 若是两个值与那个数的距离相等 输出长度更长的 printf("%d\n",num[l]); else printf("%d\n",num[r]); } } } printf("\n"); } } }