ZOJ Monthly, October 2011 （DP+數學專場!!!）
這套題是暑假打多校的時候拉的一次比賽，感覺題目都很有意思，所以重新拉出來總結一下。
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
,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
,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
,lucas(n-m+1,m,p));
}
else{
if(m>(n/2)) puts(0);
else printf(%lld
,lucas(n-m+1,m,p));
}
}
return 0;
}
