https://ac.nowcoder.com/acm/contest/342/C
C++版本一
题解:
大佬东西,tql,orz
#include<bits/stdc++.h>
#define N 21
#define M 10000000
#define Nxt (now>>(x-1)&1)
using namespace std;
int n,m,k,ans,cnt;
int a[N][N],v[N][N];
int rt[N][N],ch[M][2],sum[M];
void ins(int &p,int now,int x=31){
if(!p)p=++cnt; sum[p]++;
if(x) ins(ch[p][Nxt],now,x-1);
}
int ask(int p,int now,int x=30){
if(x<0) return 0; int k=now>>x&1,ok=sum[ch[p][!k]];
return ok>0 ? ask(ch[p][!k],now,x-1)+(1<<x) : ask(ch[p][k],now,x-1);
}
void dfs(int x,int y,int now){
if(x>n or y>m) return ;
if(v[x][y]) return ins(rt[x][y],now^a[x][y]),void();
dfs(x+1,y,now^a[x][y]); dfs(x,y+1,now^a[x][y]);
}
void dfs1(int x,int y,int now){
if(x<1 or y<1) return ;
if(v[x][y]) return ans=max(ans,ask(rt[x][y],now)),void();
dfs1(x-1,y,now^a[x][y]); dfs1(x,y-1,now^a[x][y]);
}
signed main(){
cin>>n>>k;m=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n and i<=m;i++)
v[i][m-i+1]=1;
dfs(1,1,k);dfs1(n,m,0);cout<<ans;
}
C++版本二
题解:C++版本一简化版本
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define N 21
#define M 10000000
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,k,q;
int ans,cnt;
int a[N][N];
int rt[N][N],ch[M][2],sum[M];
void ins(int &p,int now,int x=31){
if(!p)p=++cnt; sum[p]++;
if(x)
ins(ch[p][now>>(x-1)&1],now,x-1);
}
int ask(int p,int now,int x=30){
if(x<0)
return 0;
int k=now>>x&1,ok=sum[ch[p][!k]];
return ok>0 ? ask(ch[p][!k],now,x-1)+(1<<x) : ask(ch[p][k],now,x-1);
}
void dfs(int x,int y,int now){
if(x+y==n+1)
return ins(rt[x][y],now^a[x][y]),void();
dfs(x+1,y,now^a[x][y]);
dfs(x,y+1,now^a[x][y]);
}
void dfs1(int x,int y,int now){
if(x+y==n+1)
return ans=max(ans,ask(rt[x][y],now)),void();
dfs1(x-1,y,now^a[x][y]);
dfs1(x,y-1,now^a[x][y]);
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
cin>>n>>k;n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
dfs(1,1,k);
dfs1(n,n,0);
cout<<ans<<endl;
//cout << "Hello world!" << endl;
return 0;
}
C++版本三
C++版本四
C++版本五
/*
字典树+dfs双向
*/
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#define ll long long
#define pb push_back
#define test printf("here!!!")
using namespace std;
const int mx=20+10;
const int lim=3e6+10;
int a[mx][mx];
int dif[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n;
ll ans;
int tot=0;
int trie[21][lim][2];
void add(ll p,int x)
{
int rt=0;
for (int i=30;i>=0;--i)
{
int rp=(p>>i)&1;
if (!trie[x][rt][rp]) trie[x][rt][rp]=++tot;
rt=trie[x][rt][rp];
}
}
void see(ll p,int x)
{
int rt=0;
ll val=0;
for (int i=30;i>=0;--i)
{
int rp=(p>>i)&1;
if (trie[x][rt][rp^1])
{
val+=(1ll<<i);
rt=trie[x][rt][rp^1];
}
else rt=trie[x][rt][rp];
}
ans=max(ans,val);
}
void dfs(int x,int y,ll exp)
{
exp^=a[x][y];
if (x+y==n+1)
{
add(exp,x);
return;
}
dfs(x+1,y,exp);
dfs(x,y+1,exp);
}
void dfs2(int x,int y,ll exp)
{
if (x+y==n+1)
{
see(exp,x);
return;
}
exp^=a[x][y];
dfs2(x-1,y,exp);
dfs2(x,y-1,exp);
}
int main()
{
int e;
scanf("%d%d",&n,&e);
for (int i=1;i<=n;++i)
{
for (int j=1;j<=n;++j)
{
scanf("%d",&a[i][j]);
}
}
dfs(1,1,e);
dfs2(n,n,0);
printf("%lld\n",ans);
}