又来吐糟了啦。。。
今天照样刷出来的题不多。勉强也只能算个三题半吧!
上午在做上次比赛的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; }
最后,晚上张浩然同学给我们讲了下图论。最小生成树、最短路径、并查集、强连通分量。。。
各种算法,又有事干咯。