4.友好数对(kompici)

题目描述

 在顺利完成家庭作业以后,Mirko感到非常的厌倦。所以,他列出了N个数,这些数中有些数对他是喜欢的,有些数对他是不喜欢的。

他喜欢的数对叫做友好数对,如果两个数至少有一个相同的数字(不要求在相同的位置),那么这两个数就是友好数对。请帮助Mirko在这N个数找出有多少友好数对。

输入

第一行一个正整数N(1<=N<=1000000)。

接下来N行,每行一个正整数,范围在1到1018之间。N个数中任意两个数都是不同的。

输出

只有一行一个整数,表示友好数对的个数。

样例输入和输出

正解
转化为二进制+玄学
AC代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,b,a[100005];
long long x,s;
int main()
{
   
	freopen("kompici.in","r",stdin);
	freopen("kompici.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
   
		b=0;
		cin>>x;
		while(x!=0)//变二进制
		{
   
			b=b|(1<<(x%10));
			x/=10;
		}
		a[b]++;
	}
	for(int i=1;i<=1023;i++)//下面是玄学
	 if(a[i]!=0)
	 {
   
	 	for(int j=1;j<=1023;j++)
	 	 if(a[j]!=0&&(i&j)!=0&&i!=j)
	 	  s+=a[i]*a[j];
	    s+=a[i]*(a[i]-1);
	 }
	cout<<s/2; 
	return 0;
}

下面附本次比赛的其他题目

2020.02.19普及C组模拟赛8(第一题)
2020.02.19普及C组模拟赛8(第二题)
2020.02.19普及C组模拟赛8(第三题)
2020.02.19普及C组模拟赛8(第四题)
2020.02.19普及C组模拟赛8(总结)

谢谢