posts - 64, comments - 4, trackbacks - 0, articles - 0

容斥原理及代码

Posted on 2010-08-19 12:01 acronix 阅读(585) 评论(0)  编辑 收藏 引用 所属分类: hzshuai解题中算法总结

下面是容斥原理的代码(主要用来计数):f(i)是指具有性质i的个数

 

Code:
int s = 0;
 
for(int i=1;i<(1<<n);i++){
 
int ccount = 0;
 
for(int j=0;j<n;j++){
 
int test = ((1<<j)&i);
 
if(test!=0) ccount++;
 }
 
if(ccount&1) s += f(i);
 
else        s -= f(i);
 }

 

练习:

PKU 2773

HDU 3507


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理