比赛 |
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;
- }