首页 > 代码库 > HDU1006、3037、2084、1176题解

HDU1006、3037、2084、1176题解

2024-07-06 15:29:19   222人阅读

最近就只有早起做题，做完就上课，周六日可以做些恶心点点的，平时要上课就只有做做DP，数学题什么的了。

HDU1006，十分恶心的一题，实际上我还不是很懂，看着kuangbin大神的代码基本对着拍，没有什么改进。

题目的意思就是时钟里有三条针，时分秒针，两两超过D度就开心，问一天有百分只几是开心的。

思路就是：模拟，区间交，关键，精度问题，这个针算是连续的～不是60秒动一下分针！

/*************************************************************************
> OS     : Linux 3.2.0-60-generic #91-Ubuntu
> Author : yaolong
> Mail   : dengyaolong@yeah.net 
> Created Time: 2014年05月24日 星期六 07:18:50
************************************************************************/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
struct segment{
    double l,r;
    segment(){}
    segment(double lt,double rt){
        l=lt;
        r=rt;

    }
    segment(const segment & s){
        l=s.l;
        r=s.r;

    }

};
double D;
segment intersect(segment a,segment b){
    segment p;
    p.l=max(a.l,b.l);
    p.r=min(a.r,b.r);
    if(p.l>=p.r){
        p.l=p.r=0;

    }
    return p;

}
segment  solve(double a,double b){

    //D<=a*x+b<=360-D,求出最大区间[l,r]
    segment p;
    if(a>0){
        p.l=(D-b)/a;
        p.r=(360-D-b)/a;

    }else{
        p.r=(D-b)/a;
        p.l=(360-D-b)/a;

    }
    segment s(0,60);
    return intersect(s,p);

}
double cal(int h,int m){
    double a,b,res=0;
    segment s[3][2];
    segment s1;
    /*
    //double hh=30*h+m/2.0+s/120.0
    //double mm=6*m+s/10
    //double ss=6*s
    //求解D<=|hh-m|<=360-D
    double hh=30*h+m/2.0+1/120.0;
    double mm=6*m+1.0/10;
    double ss=6.0;
    s[0][0]=solve(hh,-mm);
    s[0][1]=solve(-hh,mm);

    //解方程 D<=|hh-ss|<=360-D
    s[1][0]=solve(hh,-ss);
    s[1][1]=solve(-hh,ss);

    //解方程 D<=|ww-ss|<=360-D
    s[2][0]=solve(mm,-ss);
    s[2][1]=solve(-mm,ss);
    */
    //解方程 D<=|hh-mm|<=360-D 
    //hh=30*h+m/2+s/120;
    //mm=6*m+s/10;
    a=1.0/120-0.1;
    b=30*h+m/2.0-6*m;
    s[0][0]=solve(a,b);
    s[0][1]=solve(-a,-b);

    //解方程  D<=|hh-ss|<=360-D 
    //hh=30*h+m/2+s/120;
    //ss=6*s;
    a=1.0/120-6.0;
    b=30*h+m/2.0;
    s[1][0]=solve(a,b);
    s[1][1]=solve(-a,-b);

    //解方程  D<=|mm-ss|<=360-D 
    //mm=6*m+s/10;
    //ss=6*s;
    a=0.1-6;
    b=6*m;
    s[2][0]=solve(a,b);
    s[2][1]=solve(-a,-b);
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){

                s1=intersect(intersect(s[0][i],s[1][j]),s[2][k]);
                res+=s1.r-s1.l;

            }

        }

    }
return res;
}
double solve(){
    double res=0;
    for(int i=0;i<12;i++){
        for(int j=0;j<60;j++){
            res+=cal(i,j);
            //        cout<<res<<endl;

        }

    }
    return res*100/(60*60*12);

}
int main(){
    while(scanf("%lf",&D)&&D!=-1){
        printf("%.3lf\n",solve() );

    } 
    return 0; 

}

HDU3037

组合数学，裸题一道，Lucas，我还做过一题高校俱乐部的Lucas题目，题目是正多边形对角线，当时看大神们给的公式，完全不理解～对着来拍。

言归正传，这题目意思是n颗树之间最多放m个豆，问有多少种可能。

我们可以这样理解，我们考虑成n+m颗树，之后抽m颗出来，如果我们抽到我们手动添加的树，那么就是有豆没放。这样就是C(n+m,m)%P的结果。

Lucas的用法：p一定要是素数，且数量级在10^5。

我们可以递归成为

C(n,m)%p=C(n%p,m%p)*Lucas(n/p,m/p)

m=0返回1。

另外，这题目交lld会错！！linux用户不服！

/*************************************************************************
    > OS     : Linux 3.2.0-60-generic #91-Ubuntu
    > Author : yaolong
    > Mail   : dengyaolong@yeah.net 
    > Created Time: 2014年05月24日 星期六 23:30:08
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef  long long LL;
LL fact[100001];
void init(LL p){
    fact[0]=1;
    for(int i=1;i<=p;i++){
        fact[i]=(fact[i-1]*i)%p;
    }
}
LL pow_mod(LL n,LL m,LL p){
    LL res=1;
    while(m){

        if(m&1){
            res=(res*n)%p;
        }
        n=n*n%p;
        m>>=1;
    }
    return res;
}
/*LL Lucas(LL n,LL k,LL p){
    if(k==0)
    return 1;
    LL a=n%p;
    LL b=k%p;
    return fact[a]*pow_mod(fact[b]*fact[a-b],p-2,p)*Lucas(n/p,k/p,p)%p;
}*/
LL Lucas(LL n,LL m,LL p){  
    LL ret=1;  
    while(n&&m){  
        LL a=n%p,b=m%p;  
        if(a<b) return 0;  
        ret=(ret*fact[a]*pow_mod(fact[b]*fact[a-b]%p,p-2,p))%p;  
        n/=p;  
        m/=p;  
    }  
    return ret;  
}  
int main(){
    int T;
    LL m,n,p,i;
    
    scanf("%d",&T);
    while(T--){
        scanf("%I64d%I64d%I64d",&m,&n,&p);
        LL res=0;
        init(p);
        res=Lucas(n+m,m,p);
        printf("%I64d\n",res);
    }
   return 0; 
}
HDU2084、1176都是经典都不能再经典的数塔dp了，之前对dp基本不做...一直吃亏，现在基础练起。不废话，直接上代码好了。

hdu2084

/***********************************************************
> OS     : Linux 3.2.0-60-generic #91-Ubuntu
> Author : yaolong
> Mail   : dengyaolong@yeah.net 
> Time   : 2014年05月26日 星期一 07:12:40
**********************************************************/
#include<iostream>
using namespace std;
int dp[105][105];
int main(){
    int T;
    int N;
    cin>>T;
    while(T--){
        cin>>N;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=i;j++){
                cin>>dp[i][j];

            }     

        }
        for(int i=N-1;i>=1;i--)
        {
            for(int j=1;j<=i;j++)
            {
                dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i+1][j+1]) ;

            }


        }
        cout<<dp[1][1]<<endl;

    }



    return 0;

}
hdu1176
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[100015][12];
int main(){

    int n;
    while(scanf("%d",&n)&&n){

        int t,x;
        int max_t=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x,&t);
            dp[t][x]++;
            max_t=max(t,max_t);
        }

        for(int i=max_t;i>=0;i--){
            for(int j=0;j<=10;j++){
            if(j>0&&j<10)
            dp[i][j]=dp[i][j]+max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]);
            else if(j==10)
            dp[i][j]=dp[i][j]+max(dp[i+1][j-1],dp[i+1][j]);
            else if(j==0)
            dp[i][j]=dp[i][j]+max(dp[i+1][j+1],dp[i+1][j]);

            }

        }

        printf("%d\n",dp[0][5]);
    }



    return 0;
}


联系
我们