主题:第66次编程比赛
雨中飞燕 [专家分:18980] 发布于 2008-05-22 23:02:00
[size=3]问题题目:最大的异或
[color=0000FF]题目描述:[/color]
给你n个正整数,你要找出哪两个数按位异或运算后的结果是最大的
[color=0000FF]输入:[/color]
输入一个整数n(2<=n<=100000),然后就是n个1e9以内的正整数
[color=0000FF]输出:[/color]
输出最大的按位异或运算结果
[color=0000FF]样例输入:[/color]
4
1 3 4 7
[color=0000FF]样例输出:[/color]
7
[color=0000FF]提示:[/color]
3和4的异或的结果是7,已经最大
参加比赛者直接回复本帖子即可,回复帖子不可见
结束时间:6月2日[/size]
最后更新于:2008-05-27 09:59:00
回复列表 (共27个回复)
21 楼
yfbsg [专家分:30] 发布于 2008-05-31 09:13:00
#include<stdio.h>
int main()
{
int a[100000]={0};
int n;
printf("请输入 n\n");
scanf("%d",&n);
if(n<2||n>100000)
return 0;
int i,max=0,j,c;//***************init*************
printf("请输入 1e9 以内的正整数\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=n-2;i>=0;i--)
for(j=0;j<=i;j++)
{
c=(a[j]^a[j+1]);
if(c>max)
{
max=c;
}
}
printf("max:%d\n",max);
for(i=n-2;i>=0;i--)
for(j=0;j<=i;j++)
if(a[j]>a[j+1])
{
c=a[j];
a[j]=a[j+1];
a[j+1]=c;
}
getchar();
getchar();
return 1;
}
22 楼
卧龙孔明 [专家分:240] 发布于 2008-05-31 10:27:00
[code]
/*
问题题目:最大的异或
题目描述:
给你n个正整数,你要找出哪两个数按位异或运算后的结果是最大的
输入:
输入一个整数n(2<=n<=100000),然后就是n个1e9以内的正整数
输出:
输出最大的按位异或运算结果
样例输入:
4
1 3 4 7
样例输出:
7
提示:
3和4的异或的结果是7,已经最大
*/
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
struct KEY
{
int n; /*数字*/
char x[32]; /*2进制*/
} key[100001];
int best;
void sort(int low,int high,struct KEY key[])
{
int i=low,j=high;
struct KEY tag;
if(i<j)
{
tag=key[low];
do
{
while(tag.n<key[j].n && i<j) j--;
if(i<j)
{
key[i]=key[j];
i++;
while(tag.n>=key[i].n && i<j) i++;
if(i<j)
{
key[j]=key[i];
j--;
}
}
} while(i<j);
key[i]=tag;
sort(low,i-1,key);
sort(j+1,high,key);
}
}
int search(int x,int left,int right,int t)
{
int l=left,r=right,mid;
int p=!key[x].x[t];
if(left==right)
{
if(best < (key[x].n ^ key[left].n))
{
best=(key[x].n ^ key[left].n);
}
return 0;
}
while(l<=r)
{
mid=(l+r)>>1;
if(key[mid].x[t]) r=mid-1; else l=mid+1;
}
if(p)
{
if(l<=right)
{
search(x,l,right,t-1);
}
else
search(x,left,r,t-1);
}
else
{
if(left<=r)
{
search(x,left,r,t-1);
}
else
search(x,l,right,t-1);
}
return 0;
}
int main(void)
{
int i,j,tmp;
int m,from,big;
srand((unsigned)time(NULL));
while(scanf("%d",&m)!=EOF)
{
memset(key,0,sizeof(key));
for(i=1;i<=m;i++)
{
scanf("%d",&key[i].n);
tmp=key[i].n;
j=0;
while(tmp)
{
key[i].x[j]=tmp&1;
tmp>>=1;
j++;
}
}
{
struct KEY t;
int c1,c2;
for(i=m/6*5;i<m;i++)
{
c1=((rand()<<4)+rand())%m+1;
c2=((rand()<<4)+rand())%m+1;
t=key[c1]; key[c1]=key[c2]; key[c2]=t;
}
}
sort(1,m,key);
i=0; big=0;
while(i<32)
{
if(key[m].x[i]) big=i;
i++;
}
from=m;
while(key[from].x[big]) from--; from++; best=0;
for(i=from;i<=m;i++)
{
search(i,1,m,big);
}
printf("%d\n",best);
}
return 0;
}
[/code]
23 楼
左脚湾风 [专家分:0] 发布于 2008-05-31 12:43:00
学习学习
24 楼
左脚湾风 [专家分:0] 发布于 2008-05-31 12:45:00
学习学习
25 楼
地球人民 [专家分:70] 发布于 2008-05-31 14:20:00
#include"stdio.h"
#include"conio.h"
#define N 100
int max(int a,int b) //求最大值的函数.
{
return (a>b)?a:b;
}
main()
{
int i,j,k,Max=0,t,p[N],n;
clrscr();
printf("How many numbers:");
scanf("%d",&n);
printf("They are:");
for(i=0;i<n;i++)
scanf("%d",&p[i]);
for(j=0;j<n;j++)
for(k=0;k<n&&k!=j;k++)
{
t=p[j]^p[k]; //把两个数的异或值赋给t.
Max=max(t,Max); //求t和Max的最大值,赋给Max.
}
printf("%d",Max);
getch();
}
26 楼
suplucky [专家分:0] 发布于 2008-05-31 20:51:00
新手来学习的,希望大家多多指教哦
27 楼
wzz55 [专家分:0] 发布于 2008-06-02 14:04:00
?
我来回复