NC214363. 区间异或
描述
输入描述
第一行两个整数 n , m (1 ≤ n ≤ 3000 and 0 ≤ m ≤ 2e5)
第二行 n 个整数 a[i] . (0≤ a[i] ≤ 1e9)
接下来 m 行， 每行一个整数 x , 代表一次询问。 (0 ≤ x ≤ 1e9)
输出描述
每次询问输出满足条件的最短区间，如果找不到输出 -1
示例1
输入:
5 3 16 5 2 8 32 4 48 33
输出:
1 5 2
C++(clang++11) 解法, 执行用时: 64ms, 内存消耗: 1008K, 提交时间: 2020-12-07 01:27:17
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,x,n,m,S[3005]={0},A[3005]={0};
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&x),S[i]=S[i-1]^x;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)A[j-i+1]=max(A[j-i+1],S[j]^S[i-1]);
for(i=2;i<=n;i++)A[i]=max(A[i-1],A[i]);
while(m--)
{
scanf("%d",&x);
i=lower_bound(A+1,A+1+n,x)-A;
if(i>n)i=-1;
printf("%d\n",i);
}
return 0;
}