第十四周训练总结（二）

716 阅读 0 评论 473 点赞

我是靠谱客的博主想人陪棉花糖，最近开发中收集的这篇文章主要介绍第十四周训练总结（二），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这几天重点看了一下容斥原理。容斥原理，在高中学过一点，但是用来解题的话，还是有障碍，特别是不知道怎么写代码。

容斥原理的想法就是求多个集合的并集.所以要先设计好集合。组合数学问题中,正面解决会困难,常用方法是正难则反,使用容斥原理求反向在用全集减去.将对立面的限制条件分析清楚。例如求区间互质的数的个数,则用除法等计算出一个数的倍数的方法再减去。

容斥原理的常见代码写法DFS法。

模板：

 
   #include<iostream>  
 #include<algorithm>  
 #include<cstdio>   
 #include<iomanip>  
 using namespace std;  
 #define out(x) cout<<#x<<": "<<x<<endl  
 const double eps(1e-8);  
 const int maxn=10100;  
 const long long maxint=-1u>>1;  
 const long long maxlong=maxint*maxint;  
 typedef long long lint;  
 int n;  
 double p[maxn],ans;  
   
 void init()  
 {  
     for (int i=1; i<=n; i++)  
         cin>>p[i];  
 }  
   
 void dfs(int x, int tot, double sum)  
 {  
     if (x==n+1)  
     {  
         if (sum==0.0) return;//divide by zero is illegal  
         if (tot&1)  
             ans+=1/sum;  
         else  
             ans-=1/sum;  
         return;  
     }  
     dfs(x+1,tot,sum);  
     dfs(x+1,tot+1,sum+p[x]);  
 }      
   
 void work()  
 {  
     ans=0;  
     dfs(1,0,0.0);  
     printf("%.4fn",ans);  
 }  
   
 int main()  
 {  
     while(cin>>n)  
     {  
     init();  
     work();  
     }  
     return 0;  
 }  
 
 