题目链接:https://csacademy.com/contest/archive/task/xor-submatrix
题意:给你一个列向量和行向量,矩阵乘法定义为矩阵异或,异或完后为一个矩阵,求这个矩阵中一个子矩阵这个子矩阵内所有元素的异或和最大。
思路:假设两个向量异或我们可以得到如下矩阵:







#pragma comment(linker, "/STACK:102400000,102400000") #include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #define MOD 1000000007 #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define Key_Value ch[ch[root][1]][0] #define DBN1(a) cerr<<#a<<"="<<(a)<<"\n" #define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n" #define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n" #define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n" #define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n" #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n" #define clr(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; const int maxnode=30000000+5; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);} template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;} template<typename T> inline T read(T&x){ x=0;int _f=0;char ch=getchar(); while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x=_f?-x:x; } int n,m,cnt,ans; int a[1005],b[1005]; int ch[maxnode][2]; void Insert(int x){ int pos=0; for (int i=29;i>=0;i--){ int c=((x>>i)&1); if (!ch[pos][c]){ cnt++; ch[pos][c]=cnt; } pos=ch[pos][c]; } } void Find(int x){ int pos=0,val=0; for (int i=29;i>=0;i--){ int c=((x>>i)&1); if (ch[pos][c^1]){ pos=ch[pos][c^1]; val+=(1<<i); } else pos=ch[pos][c]; } ans=max(ans,val); } int main(){ read(n),read(m); cnt=0; for (int i=1;i<=n;i++) read(a[i]),a[i]^=a[i-1]; for (int i=1;i<=m;i++) read(b[i]),b[i]^=b[i-1]; for (int i=1;i<=n;i++){ for (int j=i+1;j<=n;j+=2) ans=max(ans,a[i-1]^a[j]); for (int j=i;j<=n;j+=2) Insert(a[i-1]^a[j]); } for (int i=1;i<=m;i++){ for (int j=i+1;j<=m;j+=2) ans=max(ans,b[i-1]^b[j]); for (int j=i;j<=m;j+=2) Find(b[i-1]^b[j]); } printf("%d\n",ans); return 0; }