问题 A: 友好整数
C语言题库
共 1321字，需浏览 3分钟
·
2021-04-01 17:54
问题 A: 友好整数
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
在成功解决他的数学作业之后，Elly感到很无聊，于是他造了N个大整数。
在这N个整数中，他喜欢某些对整数，但不喜欢另一些。
Elly称他喜欢的那些对整数为友好整数(Pals)。
两个整数被称为友好整数(Pals)当且仅当这两个数至少有一个数字相同(不一定在同一位置)。
请帮助Elly计算出在他的整数中有多少对友好整数(Pals)。
输入格式
输入包含多组测试用例。
每组数据第一行包含一个整数 N，表示Elly的整数个数。
接下来N行，每行一个整数Ai，每个整数互不相同。
1≤N≤10^6
1≤Ai≤10^18
输出格式
每组数据输出一行，表示Pals的对数。
输入样例 复制
3
4
20
44
4
32
51
123
282
输出样例 复制
1
4
思路：位运算
代码：
#include <bits/stdc++.h>
using namespace std;
char a[20];
long long cnt[2005];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++)
{
long long as=0;
scanf("%s",a);
int len=strlen(a);
for(int j=0;j<len;j++)
as|=(1<<(a[j]-'0'));
cnt[as]++;
}
long long sum=0;
for(int i=1;i<=1024;i++)
{
for(int j=i;j<=1024;j++)
{
if(i==j)
sum+=(cnt[i]*(cnt[i]-1)/2);
else if(i&j)
sum +=cnt[i]*cnt[j];
}
}
printf("%lld\n",sum);
}
return 0;
}
评论