比赛 NOIP模拟赛1 评测结果 C
题目名称 异或 最终得分 0
用户昵称 君皓寒丶 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2018-02-08 21:23:31
显示代码纯文本
  1. #include<cstdio>
  2. #include<cstring>
  3. using namespace std;
  4. int pre[100000];//下一个比x大的
  5. int a[100000],b[100000];
  6. int begin;
  7. int doit(int x)
  8. {int t=begin;
  9. if(pre[begin]==begin)
  10. {if(begin>x)
  11. return -1;
  12. else return t;
  13. }
  14. if(begin>x)
  15. return -1;
  16. while(t<x)
  17. {if(pre[t]<x)
  18. t=pre[t];
  19. if(pre[t]>x)
  20. break;
  21. else if(pre[t]==t)
  22. break;
  23. }
  24. return t;
  25. }
  26. void enter(int x)
  27. {int p=doit(x);//第一个比x小的
  28. if(p==-1)//没有比x小的
  29. {pre[x]=begin;
  30. begin=x;
  31. return ;
  32. }
  33. if(pre[p]==p)
  34. {pre[x]=x;
  35. }
  36. else pre[x]=pre[p];
  37. pre[p]=x;
  38. }
  39. int main()
  40. {freopen("xorxor.in","r",stdin);
  41. freopen("xorxor.out","w",stdout);
  42. int n,k,x;
  43. scanf("%d%d",&n,&k);
  44. for(int i=0;i<=n*n;i++)
  45. pre[i]=-1;
  46. scanf("%d",&x);//初始化数组
  47. //a[x]++;// 计数
  48. b[1]=x;
  49. //pre[x]=x;//队尾
  50. //begin=x;//队头
  51. for(int i=2;i<=n;i++)
  52. {scanf("%d",&b[i]);
  53. // if(a[b[i]]==0)//队中已有
  54. // enter(b[i]);//入队
  55. // a[b[i]]++;
  56. }
  57. x=b[1]^b[2];
  58. a[x]++;
  59. pre[x]=x;
  60. begin=x;
  61. for(int i=1;i<=n;i++)
  62. for(int j=i+1;j<=n;j++)
  63. {if(j==2&&i==1)
  64. continue;
  65. x=b[i]^b[j];
  66. if(a[x]>0)//队中已有
  67. a[x]++;
  68. else if(a[x]==0)
  69. {enter(x);//入队
  70. a[x]++;
  71. }
  72. }
  73. k-=a[begin];
  74. while(k>0)
  75. {begin=pre[begin];
  76. k-=a[begin];
  77. }
  78. printf("%d",begin);
  79. return 0;
  80. }