P7617 [COCI2011-2012#2] KOMPIĆI

D2T1 · 2021-06-11 23:12:40 · 题解

\color{blue}{\text {pwp }~{\to\textbf{My blog}\gets}}~\text{qwq}

题解

首先考虑一个数不在乎它的每一个数位是什么、哪几个数位相同，只用关心这个数中是否出现了 0\sim9 中的数，所以我们可以用一个 10 位二进制数表示一个输入的数，这个二进制数的第 k 位为 1 表示输入的数中含有数字 k。

然后使用一个数组 k 存储每个二进制数的数量。

然后答案就分为两种情况：

• 两个二进制数不同但进行与运算不为零，O(1024^2) 查找整个数组 k 即可。

• 两个二进制数相同，O(1024) 遍历即可。

总复杂度 O(1024^2)

代码

//P7617
#include <cstdio>
long long ans;
int k[1024+10],n;

int main(){
    scanf("%d",&n);
    while(n--){
        long long a; int x=0;
        scanf("%lld",&a);
        while(a) x|=(1<<(a%10)),a/=10;
        ++k[x];
    }
    for(int i=0; i<1024; ++i)
        for(int j=i+1; j<1024; ++j)
            if(i&j) ans+=(long long)k[i]*k[j];//情况一，乘法原理
    for(int i=0; i<1024; ++i)
        ans+=(long long)k[i]*(k[i]-1)/2;//情况二，组合
    return printf("%lld\n",ans)&0;
}