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);
}