首页 > 代码库 > [coci2011]友好数对 容斥
[coci2011]友好数对 容斥
无趣的小x在玩一个很无趣的数字游戏。他要在n个数字中找他喜欢友好数对。
他对友好数对的定义是：如果有两个数中包含某一个以上相同的数位（单个数字），这两个数就是友好数对。
比如：123和345 就是友好数对，因为都包含数位3，显然123和234也是由号数对。而12和34则不是友好数对，因为它们没有相同的数位。
刚拿到题没怎么读懂，因为我直观的想法是存一下扫一遍就行了，后来一想，得用容斥；又犯蠢了；
其实这道题的容斥比较基本，看代码吧；
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cstdlib>#include<ctime>#include<vector>#include<algorithm>#include<queue>#include<map>using namespace std;#define LL long longint n;LL x=0;int b[1<<11],c[1<<11];void init(){ cin>>n; int y,p; for(int i=1;i<=n;i++){ scanf("%I64d",&x); p=0; while(x!=0){ y=x%10; x/=10; p=p|(1<<y); } b[p]++; }}LL col(LL x){return x*(x-1)/2;}void work(){ for(int i=1;i<1<<10;i++) for(int j=1;j<1<<10;j++) if((i|j)==i)c[j]+=b[i]; int sum=0; LL ans=0; for(int i=1;i<1<<10;i++){ sum=0; for(int j=0;j<10;j++){ if(i&(1<<j))sum++; } if(sum%2)ans+=col(c[i]); else ans-=col(c[i]); } cout<<ans<<endl;}int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); init(); work();}
[coci2011]友好数对 容斥
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。