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;
}