比赛 NOIP模拟赛1 评测结果 C
题目名称 异或 最终得分 0
用户昵称 君皓寒丶 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2018-02-08 21:23:31
显示代码纯文本
#include<cstdio>
#include<cstring>
using namespace std;
int pre[100000];//下一个比x大的 
int a[100000],b[100000];
int begin;
int doit(int x)
        {int t=begin;
		 if(pre[begin]==begin)
		   {if(begin>x)
		      return -1;
		    else return t;
		   }
		 if(begin>x)
		   return -1;
		 while(t<x)
		      {if(pre[t]<x)
		         t=pre[t];
		       if(pre[t]>x)
                      break;
			   else if(pre[t]==t)
		              break;
		       
		      }
		 return t;
		}
void enter(int x)
          {int p=doit(x);//第一个比x小的 
           if(p==-1)//没有比x小的 
             {pre[x]=begin;
              begin=x;
              return ;
			 }
		   if(pre[p]==p)
		     {pre[x]=x;
			 }
		    else pre[x]=pre[p];
		   pre[p]=x;
		  }
int main()
{freopen("xorxor.in","r",stdin);
 freopen("xorxor.out","w",stdout);
 int n,k,x;
 scanf("%d%d",&n,&k);
 for(int i=0;i<=n*n;i++)
    pre[i]=-1;
 scanf("%d",&x);//初始化数组 
 //a[x]++;// 计数 
 b[1]=x;
 //pre[x]=x;//队尾 
 //begin=x;//队头 
 for(int i=2;i<=n;i++)
    {scanf("%d",&b[i]);
 //    if(a[b[i]]==0)//队中已有 
//	   enter(b[i]);//入队
//	 a[b[i]]++; 
	}
 x=b[1]^b[2];
 a[x]++;
 pre[x]=x;
 begin=x;
 for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
       {if(j==2&&i==1)
          continue;
	    x=b[i]^b[j];
	    if(a[x]>0)//队中已有 
          a[x]++;
	    else if(a[x]==0)
		       {enter(x);//入队
		        a[x]++; 
	           }
	    }
 k-=a[begin];
 while(k>0)
      {begin=pre[begin];
	   k-=a[begin];
	  }
 printf("%d",begin);
 return 0;
}