1003.Xor Sum 1004.Labyrinth

本文主要是介绍1003.Xor Sum 1004.Labyrinth，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

百度之星初赛的 C D 题

Problem: 1003 Xor Sum

题意：n个数字，m个查询，n个数字为一个集合，每次查询x,求集合中的某个数字与x抑或的值最大

思路：建一棵二进制字典树,注意 long long

Code：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NODE 3200010
#define N 100010
typedef long long LL;
LL n,node,next[NODE][2],lend[NODE];
void add(LL cur,LL k)
{memset(next[node],0,sizeof(next[node]));lend[node]=0;next[cur][k]=node++;
}
LL cal(LL x)
{LL i,k,cur=0;for(i=60;i>=0;i--){k=(((LL (1))<<i)&x)?0:1;if(next[cur][k]) cur=next[cur][k];else    cur=next[cur][1-k];}return (x^lend[cur]);
}
int main()
{LL i,j,k,x,y,cur,m,cas=0,T; scanf("%I64d",&T);while(T--){scanf("%I64d%I64d",&n,&m);node=1;memset(next[0],0,sizeof(next[0]));for(i=0;i<n;i++){scanf("%I64d",&x),cur=0;for(j=60;j>=0;j--){k=((((LL)1)<<j)&x)?1:0;if(next[cur][k]==0) add(cur,k);cur=next[cur][k];}lend[cur]=x;}printf("Case #%I64d:\n",++cas);for(i=0;i<m;i++){scanf("%I64d",&y);printf("%I64d\n",y^cal(y));}}return 0;
}

Problem: 1004 Labyrinth

题意：给出一个n*m的矩阵(n,m<=100),每次只能往上或往下或往右，但不能走经过的路，现在从左上角出发到达右上角，求和的最大值。

思路：对于每列，枚举当列从st进入，从ed退出，进到下一行，暴力O(n^3)

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
#define maxn 110
int a[maxn][maxn];
int ans[maxn];
int sum[maxn][maxn];
int tmp[maxn];
int main(){int T,cas=0; scanf("%d",&T);while(T--){int row,col; scanf("%d%d",&row,&col);memset(sum,0,sizeof(sum));for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){scanf("%d",&a[i][j]);sum[i][j]=sum[i-1][j]+a[i][j];}}memset(ans,-0x3f,sizeof(ans));ans[1]=0;for(int i=1;i<=col;i++){memset(tmp,-0x3f,sizeof(tmp));for(int st=1;st<=row;st++){for(int ed=1;ed<=row;ed++){int cnt;if(ed>st) cnt=sum[ed][i]-sum[st-1][i];else cnt=sum[st][i]-sum[ed-1][i];tmp[ed]=max(tmp[ed],ans[st]+cnt);}}memcpy(ans,tmp,sizeof(tmp));}printf("Case #%d:\n%d\n",++cas,ans[1]);}return 0;
}

这篇关于1003.Xor Sum 1004.Labyrinth的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---