回 帖 发 新 帖 刷新版面

主题:第66次编程比赛

[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]

回复列表 (共27个回复)

21 楼


#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 楼

[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 楼

学习学习

24 楼


学习学习

25 楼

#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 楼

新手来学习的,希望大家多多指教哦

27 楼


?

我来回复

您尚未登录,请登录后再回复。点此登录或注册