程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> ZOJ Monthly, October 2011 (DP+數學專場!!!)

ZOJ Monthly, October 2011 (DP+數學專場!!!)

編輯:關於C++

 

這套題是暑假打多校的時候拉的一次比賽,感覺題目都很有意思,所以重新拉出來總結一下。

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





 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved