ZOJ Monthly, October 2011 （DP+数学专场!!!）

ZOJ Monthly, October 2011 （DP+数学专场!!!）

【比赛链接】：​​click here~~​​

这套题是暑假打多校的时候拉的一次比赛，感觉题目都很有意思，所以重新拉出来总结一下。

ZOJ 3549   Little Keng

【题意】：Calculate how many 0s at the end of the value below: 1n + 2n + 3n + ... + mn

【思路】：数据不大直接暴力求解。

代码：

/* * Problem: ZOJ No.3549* Running time: 0MS * Complier: G++ * Author: herongwei * Create Time: 16:25 2015/9/24 星期四*/ #include #include #include #include using namespace std;typedef long long LL;const int MOD=1e9;LL m,n;LL poww_mod(LL a,LL b){ LL res=a,ans=1; while(b){ if(b&1) ans=res*ans%MOD; b>>=1; res=res*res%MOD; } return ans;}int main(){ while(cin>>m>>n){ LL sum=0; for(int i=1; i<=m; ++i){ sum+=poww_mod(i,n)%MOD; } int jj=0; while(sum>0){ if(sum%10==0) jj++; else break; sum/=10; } cout<

ZOJ 3550 Big Keng

【题意】：给一个组合体：由一个圆柱和一个圆台组成，当体积一定V时，求组合体表面积的最小值

【思路】看到题，立刻想到是一些常量肯定成某种比例的时候表面积最小，于是推关系，，推关系，，推了大半天，隐隐约约有一种 关系，但是不确定

突然立刻想到二次函数，可以用三分解决，于是三分三分，无限的三分开始了，此题比较麻烦在于先三分上下体积，然后在体积里在三分上下半径，总的来说就是三分无极限

PS：eps写错了，T了一下下午了，，囧~~

代码：

/** Problem: ZOJ No.3550* Running time: 1200MS* Complier: G++* Author: javaherongwei* Create Time: 8:52 2015/9/23 */#include #include #include #include #include using namespace std;const double eps=1e-5; // 错写成-1e5,T了一下午const double pi= acos(-1.0);double R,r,V,v1,v2,H,h,L,ans;int spj(double x){ return (x>eps)-(x<-eps);}double calc(double x){ // the final area r=x; H=v1/(pi*R*R); h=3*v2/(pi*r*r+pi*r*R+pi*R*R); L=sqrt((R-r)*(R-r)+h*h); ans=pi*r*r+2*pi*R*H+pi*L*(R+r); return ans;}double rad(double x){ // after volum and san fen radius v1=x,v2=V-x; double ll=0,rr=R; while(spj(rr-ll)>0){ double mid=ll+(rr-ll)/3; double midd=ll+2*(rr-ll)/3; double midx=calc(mid); double midy=calc(midd); if(midx0){ double mid=ll+(rr-ll)/3; double midd=ll+2*(rr-ll)/3; double midx=rad(mid); double midy=rad(midd); if(midx0){ double mid=ll+(rr-ll)/3; double midd=ll+2*(rr-ll)/3; double midx=vv(mid); double midy=vv(midd); if(midx

ZOJ 3551 BloodSucker

【题意】：

有n - 1个人和1个吸血鬼，每天都会有两个人相遇，如果一个是人一个是吸血鬼，

那么人有p的概率变成吸血鬼，问你所有人都变成吸血鬼的期望天数。

【思路】：此题可以用数学期望，也可以用概率DP，概率DP接触不多，此题算是入门基础题，不过也是想了好久，（博主是个喜欢数学的人，但是数学基因不好~~）

解法一：详细过程可参考：​​click here~~​​

/* * Problem: ZOJ No.3551* Running time: 50MS * Complier: G++ * Author: herongwei * Create Time: 16:25 2015/9/24 星期四*/ #include #include #include #include #include using namespace std;const double eps=1e-5;const double pi= acos(-1.0);const int N = 1e5+10;double dp[N];int main(){ int t,n;double p;scanf("%d",&t); while(t--){ scanf("%d%lf",&n,&p); double ans=0.0; for(int i=1; i

解法二：

/*******************dp[i]表示从i个吸血鬼到n个吸血鬼的天数期望******************/#include #include #include #include #include using namespace std;const int N= 1e5+10;double dp[N];int main(){ int t,n;double p;scanf("%d",&t); while(t--){ scanf("%d%lf",&n,&p); dp[n] = 0; for(int i=n-1; i>=1; i--){ double s1,s2,p1; s1 = (double)n*(n-1)/2; ///从n个人中选两个人出来的选法，也就是C(n,2) s2 = (double)i*(n-i); ///i为从i个人中选出一人的方法，n-i为从吸血鬼中选出一个吸血鬼的总数，共有这么多种 p1 = s2/s1*p; ///人与吸血鬼相遇的概率 dp[i]=(dp[i+1]*p1+1)/p1; } printf("%.3f\n",dp[1]); } return 0;}

ZOJ 3554 A Miser Boss

【题意】：有a、b、c三个车床同时工作，三个车床做不同的任务需要不同的时间，但最后要求三个车床做事情的总时间相同，输出做完所有任务需要的最少时间，如果无法达到三个车床总工作时间相同，则输出“No”

【思路】：（数据不大，可以用搜索枚举全部状态，然后在筛选也可以，其实数据不大，果断暴力枚举也是一种方法）

动态规划问题，由于状态空间有限，可以考虑直接保存状态枚举即可。  * 状态定义：dp[i][j][k]表示三台机器是否分别能工作到i,j,k秒。  * 为了解决物品选取冲突的问题，使用vis记录上一个物品对状态的影响。  * 遍历一遍所有物品，每次枚举所有状态，如果上一个物品使该状态可以达到，则记录到dp中。  * 最后遍历所有物品后，如果有哪个时间满足dp[t][t][t]=1，则说明存在相应的解。  * 由于条件的约束，可以看出每个物品一定会对状态产生影响，所以不会存在物品没用完的问题。 代码：

/** Problem: ZOJ No.3554* Running time: 810MS* Complier: G++* Author: herongwei* Create Time: 16:25 2015/9/24 星期四*/#include #include #include #include #include using namespace std;const double eps=1e-5;const double pi= acos(-1.0);const int N = 120;const int M=120+10;int a[M],b[M],c[M];bool dp[M][M][M];bool vis[M][M][M];int main(){ int t; while(~scanf("%d",&t)){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); vis[0][0][0]=1; for(int i=0; i

ZOJ 3556 How Many Sets I

【题意】：Give a set S, |S| = n, then how many ordered set group (S1, S2, ..., Sk) satisfies S1 ∩ S2 ∩ ... ∩ Sk = ∅. (Si is a subset of S, (1 <= i <= k))

【思路】：

代码：

/** Problem: ZOJ No.3556* Running time: 0MS* Complier: G++* Author: herongwei* Create Time: 16:25 2015/9/24 星期四*/#include #include #include #include #include using namespace std;typedef long long LL;const double eps=1e-5;const double pi= acos(-1.0);const int N = 120;const int M=120+10;const int MOD=1e9+7;LL n,k;LL poww(LL a,LL b){ LL res=a,ans=1; while(b) { if(b&1) ans=res*ans%MOD; res=res*res%MOD; b>>=1; } return ans;}int main(){ while(~scanf("%lld %lld",&n,&k)) { printf("%lld\n",poww(poww(2,k)-1,n)%MOD); }}

ZOJ 3557  How Many Sets II

【题意】： 给一个集合，一共n个元素，从中选取m个元素，满足选出的元素中没有相邻的元素，一共有多少种选法(结果对p取模1 <= p <= 10^9) 【思路】：用插板法求出组合数。既然是从n个数中选择m个数，那么剩下的数为n-m，那么可以产生n-m+1个空，这道题就变成了把m个数插到这n-m+1个空中有多少种方法，即C(n-m+1,m)%p。因为考虑数据范围，然后就Lucas定理。

代码:

/** Problem: ZOJ No.3557* Running time: 0MS* Complier: G++* Author: herongwei* Create Time: 16:25 2015/9/24 星期四*/#include #include #include #include #include using namespace std;typedef long long LL;const double eps=1e-5;const double pi= acos(-1.0);LL n,m,p;LL poww(LL a,LL b){ LL res=a,ans=1; while(b){ if(b&1) ans=res*ans%p; res=res*res%p; b>>=1; } return ans;}LL C(LL a, LL b,LL p){ if(aa-b) b=a-b; LL up=1,down=1; for(int i=0; i(n/2+1)) puts("0"); else printf("%lld\n",lucas(n-m+1,m,p)); } else{ if(m>(n/2)) puts("0"); else printf("%lld\n",lucas(n-m+1,m,p)); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。