Arpa’s obvious problem and Mehrdad’s terrible solution

Love The Way You Lie 2022-06-12 11:59 137阅读 0赞

![Center][]![Center 1][]

思路：此题考察了异或运算符，自己做的比较拙，用sign标记出现的数的次数，然后从头遍历，将x的两个异或因子的sign相乘， 加到pair里。 还有一种思路是一位大佬写的，用map从前往后记录与自己相异或的数字，如果后面出现了这个数字，那么就在总数中加上。  下面第一个是自己的代码，第二个是大佬的。

注：a^b=c => b=a^c;

#include<iostream>
    #include<cstdio>
    #define ll long long
    using namespace std;
    const int maxn = 1e6+5;
    ll a[maxn], sign[maxn];
    
    int main(){
    	ll pair=0;
    	ll n, x;
    	scanf("%lld%lld", &n, &x);
    	for(int i=1; i<=n; i++)
    	{
    		scanf("%lld", a+i);
    		sign[a[i]]++;
    	}
    	for(int i=1; i<=n; i++)
    	{
    		if(sign[a[i]] && (ll)(a[i]^x)<(ll)maxn && sign[a[i]^x])// "<"两边的数一定要强制类型转换，因为相异或的数可能很大。
    		{
    			if(x==0)
     {
    				pair+= sign[a[i]]*(sign[a[i]]-1)/2;//异或的元素是本身，对数就是从x个元素中挑两个元素 Cx2。
    				sign[a[i]]=0;
    			}
    			else
    			{
    				pair+=sign[a[i]] * sign[a[i]^x];
    				sign[a[i]]=0;
    				sign[a[i]^x]=0;
    			}
    			
    		}
    	}
    	cout<<pair<<endl;
    	return 0;
    }

#include <cstdio>  
    #include <map>  
    using namespace std;  
    typedef long long ll;  
    ll a[100100];  
    map <ll,ll>mp;  
    int main()  
    {  
        ll m,n;  
        ll cnt = 0;  
        scanf("%lld%lld",&m,&n);  
        for(int i = 0; i < m ;i++)  
        {  
            ll x;  
            scanf("%lld",&x);  
            cnt += mp[x];//加上前面出现过的相异或的元素的个数。
            ll tmp = x ^ n;  
            mp[tmp]++;  
        }  
        printf("%lld\n",cnt);  
        return 0;  
    }

代码是不是很短^\_^

[Center]: https://img-blog.csdn.net/20170722192834424?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZHVfbHVu/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220612/8f92441e5c9e431285b978383a546d77.png