[2018.03.29 T1] 异或

暂无链接

异或

【题目描述】

蒜头是一位优秀的 OI 选手。

自古以来，迷人的星空总是吸引着许多天文学的爱好者。顺着星星的指引，明天的蒜头将会遇到一道 有趣的题，和蒜头曾经出过的一道题一样有趣。

给一个长度为 n n 的序列aa， q q 次询问在a[l...r]a[l...r]中选择若干个数(可以不选)和 d d 异或所能得到的最大值。

【输入】

输入的第一行是一个数nn，表示序列的长度。

接下来一行 n n 个数，第ii个数表示序列的第 i i 个元素。

接下来一行是一个数qq，表示询问数。

接下来 q q 行，每行三个数l,r,dl,r,d表示一组询问。

【输出】

共输出 q q 行，第ii行表示第 i i 个询问的答案。

【输入样例】

17
564336209 776981317 868432406 79690390 105769824 521627888 858214260 66699280 76283981 338813935 566669033 929900644 508668884 239924833 9927169 356446378 777851615
20
8 8 326049892
1 8 950790720
10 12 76241722
7 7 324181335
5 9 89862960
3 6 313463619
4 9 897057197
1 6 840260745
1 3 1068836159
3 7 33253290
4 6 628314026
7 12 1010898432
4 9 49135963
10 17 359110673
4 9 403969940
2 9 369688276
3 7 709921095
2 6 618680372
5 7 238186905
10 10 886901243

【输出样例】

326049892
1072550086
870740830
544592419
927225721
1048265125
934931072
1063393342
1068836159
914859818
1054596556
1069078032
934584212
1070493062
938347227
1072003701
934670401
1061732946
1024802541
886901243

【提示】

子任务编号123456789子任务分值71181017178517n=172003×1043×1043×1053×1042×105106106q=202003×1043×1053×105106106106106ai<23021623023023023023024230子任务编号子任务分值n=q=ai<171720230211200200216383×1043×1042304103×1043×1052305173×1053×1052306173×104106230782×1051062308510610624917106106230
每个子任务七个测试点，依次分布。

题解

出题人题解：
时间复杂度瓶颈在于我们要表示出 O(loga) O ( l o g a ) 个线性基。
考虑我们之前维护端点的过程，那么后 i i 个端点实际上就是一个
大小为ii的线性无关组。
容易发现，我们将位置在前面的数异或位置在后面的数，并不会
对我们的答案产生影响。所以实际上我们仍然可以维护线性基，
并且只需维护 1 1 个。
实现上来说，只要同时存在两个最高位相同的数时，用前面的异
或后面的即可。
时间复杂度O((n+q)log2a)O((n+q)log2a)。

代码

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+5;
struct sd{int ri,d,id;};
vector<sd>que[M];
int ans[M],a[M],n,q,pos[40],base[40];
void in()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
scanf("%d",&q);
}
void ac()
{
int le,ri,d;
for(int i=1;i<=q;++i)
{
scanf("%d%d%d",&le,&ri,&d);
que[le].push_back((sd){ri,d,i});
}
memset(pos,63,sizeof(pos));
int v,p,re;
for(int i=n;i>=1;--i)
{
v=a[i],p=i;
for(int j=30;j>=0;--j)
{
if(v>>j&1)
{
v^=base[j];
if(pos[j]>p)
base[j]^=v,swap(pos[j],p);
}
if(!v)break;
}
for(int j=que[i].size()-1;j>=0;--j)
{
d=que[i][j].d;ri=que[i][j].ri;
for(int k=30;k>=0;--k)if(pos[k]<=ri&&~d>>k&1)d^=base[k];
ans[que[i][j].id]=d;
}
}
for(int i=1;i<=q;++i)
printf("%dn",ans[i]);
}
int main()
{
in();ac();
return 0;
}

最后

以上就是笑点低猫咪为你收集整理的[2018.03.29 T1] 异或的全部内容，希望文章能够帮你解决[2018.03.29 T1] 异或所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。