22/7/2012 ICPC培训 第七天

又来吐糟了啦。。。

今天照样刷出来的题不多。勉强也只能算个三题半吧！

上午在做上次比赛的B题。

要用数据结构，vector和deque。也第一次感受到了数据结构的魅力，的确把时间复杂度优化的很好。

按照出题者的思路写出了代码，TLE了。结果你懂得，各种纠结，再也想不到如何优化了。。。

然后，就在刚才，把出题人-—唐爽童鞋的代码拿来，居然也TLE了。神马情况。

快到中午，眼看没A题。唉，退而求其次，A一水题吧。

HDU2289，求圆台的高。

主要就是根据性质求出高和半径的关系。然后根据圆台体积公式得到体积和高的关系。最后就是二分

解方程了。坑爹的是这题要求的精度很高、pi不取好也很难A。。。

代码：

#include<iostream>#include<cmath>#include<iomanip>using namespace std;const double pi=3.1415926535897931;const double accurate=1e-7;double r,R,H,V,h;double calculate(double x){    return pi*x*(r*r+pow(r+(R-r)/H*x,2)+r*(r+(R-r)/H*x))/3.0;}void binSearch(double low,double high){    double mid=(low+high)*1.0/2.0;        if(high-low<=accurate)  //这句没加，超时了几次，二分查找对出口一定得判断好     {                       //但理论上我认为这是不对的，根本就没有逼近V，只是         h=mid;              //递归的出口，否则超时         return;    }        if(fabs(calculate(mid)-V)<=accurate)    {        h=mid;        return;    }    else if(calculate(mid)>V)    {        binSearch(low,mid);    }    else    {        binSearch(mid,high);    }}int main(){    int cas;        cin>>cas;        while(cas--)    {        cin>>r>>R>>H>>V;                binSearch(0,H);                cout<<setiosflags(ios::fixed)<<setprecision(6)<<h<<endl;    }        return 0;}

下午刷了HDU4301。

用DP来做，其实我是看解题报告才懂得！

上次比赛，居然还搞3*n！！！果断做不出来。

我就不嗦了，不懂可直接看解题报告：点击打开链接

代码：

//dp[i][0][j]表示前i行分成j部分且第i行的两块属于同一部分//dp[i][1][j]表示前i行分成j部分且第i行的两块属于不同部分           #include<iostream>#include<cstring>using namespace std;const int MAX=1010;const int MOD=100000007;__int64 dp[MAX][2][MAX*2];int n,k;void DP(){    memset(dp,0,sizeof(dp));        dp[1][0][1]=dp[1][1][2]=1;  //初值         for(int i=1;i<=999;i++)    {        for(int j=1;j<=2000;j++)        {            //状态转移方程             dp[i+1][0][j]=(dp[i+1][0][j]+dp[i][0][j]+dp[i][1][j]*2)%MOD;            dp[i+1][1][j]=(dp[i+1][1][j]+dp[i][1][j])%MOD;            dp[i+1][0][j+1]=(dp[i+1][0][j+1]+dp[i][0][j]+dp[i][1][j])%MOD;             dp[i+1][1][j+1]=(dp[i+1][1][j+1]+dp[i][0][j]*2+dp[i][1][j]*2)%MOD;            dp[i+1][1][j+2]=(dp[i+1][1][j+2]+dp[i][0][j]+dp[i][1][j])%MOD;        }    }}             int main(){    DP();         int cas;        cin>>cas;    while(cas--)    {        cin>>n>>k;                cout<<(dp[n][0][k]+dp[n][1][k])%MOD<<endl;    }        return 0;} 

最后一题（HDU1969）

这还是一道二分题。

还是被卡了一会的。主要因为对递归还是不太明白。

这样的题比较好。它不像在一维数组内查找一个数是否存在，它要求不仅要求出结果，还要是最大或最小的。

当然，是在一定精度范围内。

另外就是，这两类二分题其实在代码上都是有规律可循的。刷两道题，总结下即可。

代码：

#include<iostream>#include<algorithm> using namespace std;const double pi=3.1415926535897931;const double accurate=1e-5;const int MAX=10000; double volume[MAX],maxPiece; int numPie,numFriend; inline double calculate(double r){    return pi*r*r;} void input(){    int radii;         for(int i=0;i<numPie;i++)    {        scanf("%d",&radii);        volume[i]=calculate(radii);    }    sort(volume,volume+numPie); } int calculateNum(double v){    int num=0;        for(int i=0;i<numPie;i++)    {        num+=int(volume[i]/v);                if(num>numFriend+1) break;    }        if(num>=numFriend+1)    {        maxPiece=maxPiece>v?maxPiece:v;    }         return num;} void binSearch(double low,double high){    double mid=(low+high)/2;           if(high-low<=accurate)    {         //maxPiece=maxPiece>mid?maxPiece:mid;         return;    }        if(calculateNum(mid)>=numFriend+1)    {        binSearch(mid,high);    }    else    {        binSearch(low,mid);    } }         int main(){    int cas;        scanf("%d",&cas);    while(cas--)    {        scanf("%d%d",&numPie,&numFriend);                input();                maxPiece=-1;                 binSearch(0,volume[numPie-1]);                printf("%.4lf\n",maxPiece);      }          return 0;} 

最后，晚上张浩然同学给我们讲了下图论。最小生成树、最短路径、并查集、强连通分量。。。

各种算法，又有事干咯。