A40891. 选数异或本题总分：15 分【问题描述】给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。【
填空题
困难
知识点
题目描述
选数异或
本题总分：15 分
【问题描述】
给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查
询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。
【输入格式】
输入的第一行包含三个整数 n, m, x 。
第二行包含 n 个整数 A1, A2, · · · , An 。
接下来 m 行，每行包含两个整数 li,ri 表示询问区间 [li,ri] 。
【输出格式】
对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出
no。
【样例输入】
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
【样例输出】
yes
no
yes
no
参考答案
#include <bits/stdc++.h>
using namespace std;
long long arr[100010]={0};
char arr_out[100010]={0};//m,1yes
int main()
{
int n,m,i,j,k;
long long x;
scanf("%d %d %lld",&n,&m,&x);
for(i=1;i<=n;i++)
scanf("%lld",&arr[i]);
for(k=0;k<m;k++)
{
int l,r;
scanf("%d %d",&l,&r);
for(i=l;i<r;i++)
{
int should_break_yes=0;
for(j=i;j<=r;j++)
{
if(i==j)
continue;
if((arr[i]^arr[j])==x)
{
should_break_yes=1;
arr_out[k]=1;
// printf("arri:%lld,arrj:%lld,arr[i]^arr[j]: %lld ,x:%lld\n",arr[i],arr[j],arr[i]^arr[j],x);
break;
}
}
if(should_break_yes)
break;
}
}
for(k=0;k<m-1;k++)
if(arr_out[k])
printf("yes\n");
else
printf("no\n");
if(arr_out[k])
printf("yes");
else
printf("no");
return 0;
}
上一题
下一题