問(wèn)題 A: 友好整數(shù)

內(nèi)存限制：128 MB時(shí)間限制：1 S標(biāo)準(zhǔn)輸入輸出

題目描述

在成功解決他的數(shù)學(xué)作業(yè)之后，Elly感到很無(wú)聊，于是他造了N個(gè)大整數(shù)。
在這N個(gè)整數(shù)中，他喜歡某些對(duì)整數(shù)，但不喜歡另一些。
Elly稱(chēng)他喜歡的那些對(duì)整數(shù)為友好整數(shù)(Pals)。
兩個(gè)整數(shù)被稱(chēng)為友好整數(shù)(Pals)當(dāng)且僅當(dāng)這兩個(gè)數(shù)至少有一個(gè)數(shù)字相同(不一定在同一位置)。
請(qǐng)幫助Elly計(jì)算出在他的整數(shù)中有多少對(duì)友好整數(shù)(Pals)。

輸入格式

輸入包含多組測(cè)試用例。
每組數(shù)據(jù)第一行包含一個(gè)整數(shù) N，表示Elly的整數(shù)個(gè)數(shù)。
接下來(lái)N行，每行一個(gè)整數(shù)Ai，每個(gè)整數(shù)互不相同。
1≤N≤10^6
1≤Ai≤10^18

輸出格式

每組數(shù)據(jù)輸出一行，表示Pals的對(duì)數(shù)。

輸入樣例 復(fù)制

3
4
20
44
4
32
51
123
282

輸出樣例 復(fù)制

1
4

思路：位運(yùn)算 

把每一個(gè)整數(shù)拆分為單個(gè)數(shù)字，可以把整數(shù)轉(zhuǎn)化為一個(gè)10位二進(jìn)制數(shù)當(dāng)有單個(gè)數(shù)字出現(xiàn)該二進(jìn)制數(shù)對(duì)應(yīng)位置為1，當(dāng)a,b兩個(gè)數(shù)為友好整數(shù) a&b!=0可以用map存儲(chǔ)key為二進(jìn)制數(shù)value為出現(xiàn)次數(shù)，雙重循環(huán)遍歷，不同二進(jìn)制數(shù)次數(shù)相乘，相同二進(jìn)制數(shù)次數(shù)階加

代碼：

#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;
}