2021“MINIEYE杯”中国大学生算法设计超级联赛(1)补题
source link: https://segmentfault.com/a/1190000040402397
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目链接:https://acm.hdu.edu.cn/showpr...
Xor sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 3024 Accepted Submission(s): 795
Problem Description
Given a sequence of integers of length n, find the shortest consecutive subsequence witch XOR sum not less than k.
If there are multiple consecutive subsequences of the same length, print the consecutive subsequence with the smallest left end point.
If there are no consecutive subsequence witch XOR sum not less than k, just print "-1".
Input
The first line contains a single integer t (t<=100) representing the number of test cases in the input. Then t test cases follow.
The first line of each test case contains two integers n (1<=n<=100000) and k (0<=k<2^30), representing the length of sequence.
The second line of each test contains n integers ai (0<=ai<2^30), representing the integers in sequence.
The number of test witch n>1000 does not exceed 5.
Output
For each test case, print two integers in one line, representing the left end point and right end point of the consecutive subsequence.
If there are no consecutive subsequence witch XOR sum not less than k, print "-1" in one line.
Sample Input
2
3 2
1 2 2
9 7
3 1 3 2 4 0 3 5 1
Sample Output
2 2
5 7
题目大意:找到一个连续子序列,使子序列上的数的异或和大于等于k,找到子序列最短长度,如果找到多个长度相等的子序列,那就输出左端点最小的那个子序列的左端点和右端点。
分析:求出原序列的前缀序列,那么本题的题意就变成了找前缀序列两个最近的数,使他们的异或和大于等于k,并输出两个数的下标,同样,如果两组数距离相等,输出靠左的那组。题目就变为了01字典树求异或和问题。
建立一个mr[k]数组,存储k节点所有子树上所存储的数的最大下标,即后面来的数的下标要覆盖前面数的下标。
具体代码:
//注意初始化,我在做的时候总是因为初始化超时
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <queue>
using namespace std;
const int N = 3e6+10;
int mr[N];//后面数的下标要覆盖前面数的下标
int tree[N][2];//字典树
int a[100010];
int cnt;//字典树节点编号
int n,k;
int l,r;
void insert(int num,int idx)
{
int root = 0;
for(int i=29;i>=0;i--)
{
int p=(num>>i)&1;//取num第i位的数
mr[root]=idx;//更新字典树节点所存储的下标
if(!tree[root][p])
{
tree[root][p]=++cnt;
//cout<<"hfahud"<<root<<" "<<p<<" "<<cnt<<endl;
}
root=tree[root][p];
}
mr[root]=idx;
}
int req(int x)//询问操作,返回的是与x异或大于等于k,且与x相距最近的数的下标
{
int root=0;
int flag=0;
int res=-1;
for(int i=29;i>=0;i--)
{
int p1=(x>>i)&1;
int p2=(k>>i)&1;
if(!p2)//k在第i位上的数为0,那么如果两数在第i位上异或为1,那么两数异或和必定大于k
{
if(!p1)//如果p1也为0,那么只有存在右子树才能异或为1
{
if(tree[root][1]!=0)//右子树存在
{
res=max(res,mr[tree[root][1]]);
if(!tree[root][0])//如果左子树不存在
{
flag=1;
break;
}
root=tree[root][0];//继续向下找
}
else//这种情况只能继续向下找,直到某一位满足上述情况
{
if(!tree[root][0])
{
flag=1;
break;
}
root=tree[root][0];
}
}
else//如果p1为1,那么只有存在左子树才能异或为1
{
if(tree[root][0]!=0)//如果左子树存在
{
res=max(res,mr[tree[root][0]]);
if(!tree[root][1])
{
flag=1;
break;
}
root=tree[root][1];
}
else
{
if(!tree[root][1])
{
flag=1;
break;
}
root=tree[root][1];//到x所在的右子树继续向下寻找
}
}
}
else//如果p2在第i为上的数为1,如果两数在第i位上异或为0,必定会小于k
{
if(!p1)//如果p1为0
{
if(tree[root][1]!=0)//表示存在右子树
{
root=tree[root][1];//两数在第i位上的异或等于k在第i位上的数,无法判断两数异或是否大于等于k,继续向下找
}
else//如果不存在右子树,则两数异或一定小于k
{
flag=1;
break;
}
}
else//与上同理
{
if(tree[root][0]!=0)
{
root=tree[root][0];
}
else
{
flag=1;
break;
}
}
}
}
if(!flag)
{
res=max(res,mr[root]);
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&k);
l=-1,r=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]=(a[i]^a[i-1]);
}
for(int i=1;i<=n;i++)
{
insert(a[i],i);//建树
int left=req(a[i]);
if(left!=-1)
{
if(i-left<r-l)
{
l=left;
r=i;
}
}
}
if(l>=0)
{
printf("%d %d\n",l+1,r);
}
else
{
printf("-1\n");
}
for(int i=0;i<=cnt;i++)
{
mr[i]=tree[i][0]=tree[i][1]=0;
}
cnt=0;
}
return 0;
}
Recommend
-
68
台湾篮球联赛惊现超神绝杀,这球可以吹一辈子
-
8
阅读时间大约3分钟(874字) ...
-
4
话说每次都是周末一大早吗,前一晚嗨了,第二天就起迟了,本来以为罚时令我与金擦肩而过~ 但11月2号下午查重后的获奖名单,检索自己的名字,居然变成了金奖(意外,有点惊喜),看来有同学不小心被查重除名了... G题如果L在2e5...
-
6
教育部 2022 年将办首届中国青少年足球联赛,并筹备首届全国学生(青年)运动会,有哪些信息值得关注?记者今天从教育部获悉,今年教育部将举办首届中国青少年足球联赛,并筹备首届全国学生(青年)运动会...
-
4
MINIEYE完成D2轮融资 智能驾驶解决方案研发存在发展空间 •...
-
7
...
-
4
「MINIEYE」完成D3轮融资,D轮累计融资8亿元2022-06-07 09:17:12 来源:合创投资 作者: 近日,智能驾驶解决方案研发商MINIEYE(深圳佑驾创新科技有限公司)宣布完成D3轮融资,本轮融资由凯辉基金领投,蔚来...
-
11
2022-06-13 07:34 苏格兰足球超级联赛将在 Topps 平台首发 NFT 据 Nftevening 6 月 13 日消息,苏格兰职业足球联盟(SPFL)宣布将首次推出 NFT,藏品包括明星球员、俱乐部队徽和其他高光时刻。此次发布的 NFT 包含所有 12...
-
7
英格兰足球超级联赛(英格兰最高级别足球联赛)_百度百科 近期有不法分子冒充百度百科官方人员,以删除词条为由威胁并敲诈相关企业。在此严正声明:百度百科是免费编辑平台,绝不...
-
3
DOTA 2开出46人禁赛大罚单,EHOME等5支战队移出DPC中国联赛 2023-03-13 •
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK