牛客小白月赛17 A 小sun的假期

古城微笑少年丶 2023-10-11 09:40 5阅读 0赞

题意已经很明显了，但是我首先是用暴力方法先把数字离散，再用离散后的值当下标来存这个数字出现了几次

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<map>
     6 using namespace std;
     7 const int maxn=10000000;
     8 map<int,int>r;
     9 int main()
    10 {
    11     //printf("%d\n",0^1^2^3);
    12     int n,sum,a;
    13     sum=0;
    14     scanf("%d",&n);
    15     for(int i=1;i<=n;++i)
    16     {
    17         scanf("%d",&a);
    18         r[a]++;
    19         //printf("%d\n",r[a]);
    20         if(r[a]%2)
    21             sum^=a;
    22         else if((r[a]-1)!=0)
    23             sum^=a;
    24     }
    25     printf("%d\n",sum);
    26     return 0;
    27 }

但是却内存超限

然后我又对所有数字排序，这样就不用存起来，因为排完序后，一样的数字在一起

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<map>
     6 using namespace std;
     7 typedef long long ll;
     8 const int maxn=10000005;
     9 int v[maxn];
    10 int main()
    11 {
    12     int n,sum=0;
    13     scanf("%d",&n);
    14     for(int i=1; i<=n; ++i)
    15     {
    16         scanf("%d",&v[i]);
    17     }
    18     //sort(v+1,v+1+n);
    19     int ci=0;
    20     v[0]=0;
    21     for(int i=1; i<=n; ++i)
    22     {
    23         if(v[i]!=v[i-1])
    24         {
    25             if(ci!=0 && ci%2)
    26                 sum^=v[i-1];
    27             ci=1;
    28         }
    29         else ci++;
    30     }
    31     //printf("%d\n",ci);
    32     if(ci!=0 && ci%2)
    33         sum^=v[n];
    34     printf("%d\n",sum);
    35     return 0;
    36 }

但是又内存超限

我又把sort排序去掉，试着试了一把结果还过了(一脸懵！)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<map>
     6 using namespace std;
     7 typedef long long ll;
     8 const int maxn=10000005;
     9 int main()
    10 {
    11     int n,sum=0,a1,a2,b;
    12     scanf("%d",&n);
    13     scanf("%d",&a1);
    14     b=1;
    15     for(int i=2; i<=n; ++i)
    16     {
    17         scanf("%d",&a2);
    18         if(a1==a2) ++b;
    19         else
    20         {
    21             if(b!=0 && b%2) sum^=a1;
    22             b=1;
    23             a1=a2;
    24         }
    25     }
    26     if(b!=0 && b%2) sum^=a1;
    27     printf("%d\n",sum);
    28     return 0;
    29 }

比赛完之后，听他们说这一道题只需要把全部输入的数据都异或一遍就可以了，因为如果某个数字出现偶数次，那么也会异或偶数次，我们知道一个数字异或偶数次相当于没有异或。那么正好符合题意！

这个代码就不给了

这个时候我就在想了，为什么我那个不加sort就可以过，也是同样的原理

像这样的数据1 2 3 3 2 4 6 4

我的代码没有异或3，但是异或了2，但是却异或了两遍2.所以还是相当于没有异或

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11518877.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif