又是一道数学题：（三分法）
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 using namespace std; 5 int main() 6 { 7 double H,h,D,l,r,mid,mmid; 8 int n; 9 scanf("%d",&n); 10 while(n--) 11 { 12 scanf("%lf%lf%lf",&H,&h,&D); 13 l=(H-h)*D/H; 14 r=D;mid=0;mmid=0; 15 while(r-l>1e-9) 16 { 17 mid=(l+r)/2; 18 mmid=(mid+r)/2; 19 if((mid+(H-h)*D/mid)>(mmid+(H-h)*D/mmid)) 20 l=mid; 21 else if((mid+(H-h)*D/mid)<(mmid+(H-h)*D/mmid)) 22 r=mmid; 23 else 24 break; 25 } 26 printf("%.3lf ",D+H-(l+(H-h)*D/l)); 27 } 28 return 0; 29 }
貌似不能二分角度！没有图不好说，具体参见：http://blog.csdn.net/freezhanacmore/article/details/9887115（里面有数学解法）
Palindrome POJ 3974
一道求最长回文子串：（必须是连续的）
就是用什么Manacher算法：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<string.h> 5 #include<string> 6 using namespace std; 7 char a[1000005],b[2000005]; 8 int d[2000005]; 9 int main() 10 { 11 int n,i,mia,ip,max1,d1=0; 12 while(scanf("%s",a)!=EOF) 13 { 14 if(a[0]=='E') 15 break; 16 n=strlen(a); 17 b[0]='@'; 18 b[1]='#'; 19 for(i=0;i<n;i++) 20 { 21 b[i*2+2]=a[i]; 22 b[i*2+3]='#'; 23 } 24 b[2*n+2]=' '; 25 n=2*n+2; 26 mia=0; 27 ip=0; 28 max1=1; 29 for(i=0;i<n;i++) 30 { 31 if(mia>i) 32 d[i]=min(d[2*ip-i],mia-i); 33 else 34 d[i]=1; 35 for(;b[i-d[i]]==b[i+d[i]];d[i]++) 36 if(i+d[i]>mia) 37 { 38 mia=i+d[i]; 39 ip=i; 40 } 41 max1=max(max1,d[i]); 42 } 43 printf("Case %d: %d ",++d1,max1-1); 44 } 45 return 0; 46 }
该算法的基本思路：
先是把原字符串扩大两倍：每隔一个插上‘#’，听说可以避免奇偶性的讨论。
之后还有一个剪枝问题：具体参见：http://www.2cto.com/kf/201210/164253.html
Minimum Inversion Number HDU 1394
一道线段树的问题，可以暴力也可树状数组：（由于精力有限，只用了线段数）
还是逆序数的问题：（这道不用离散化）
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 using namespace std; 5 struct line 6 { 7 int left; 8 int right; 9 int ma; 10 }a[5005]; 11 void build(int left,int right,int root) 12 { 13 a[root].left=left; 14 a[root].right=right; 15 a[root].ma=0; 16 if(left==right) 17 return ; 18 build(left,(left+right)/2,2*root); 19 build((left+right)/2+1,right,2*root+1); 20 } 21 void insert1(int x,int root) 22 { 23 if(x<a[root].left||x>a[root].right) 24 return ; 25 if(x==a[root].left&&x==a[root].right) 26 { 27 a[root].ma++;return ; 28 } 29 if(x>=a[root].left&&x<=a[root].right) 30 a[root].ma++; 31 insert1(x,2*root); 32 insert1(x,2*root+1); 33 } 34 int find1(int left,int right,int root) 35 { 36 if(a[root].left>=left&&a[root].right<=right) 37 return a[root].ma; 38 if(a[root].left>right||left>a[root].right) 39 return 0; 40 return (find1(left,right,2*root)+find1(left,right,2*root+1)); 41 } 42 int main() 43 { 44 int sum,min1,n,i; 45 int a1[5005]; 46 while(scanf("%d",&n)!=EOF) 47 { 48 build(1,n,1); 49 sum=0; 50 for(i=1;i<=n;i++) 51 { 52 scanf("%d",&a1[i]); 53 a1[i]++; 54 insert1(a1[i],1); 55 sum+=find1(a1[i]+1,n,1);//需要边更新，边求值 56 } 57 min1=sum; 58 for(i=1;i<=n-1;i++) 59 { 60 sum-=a1[i]-1; 61 sum+=n-a1[i];//题目求的是最小值，每次把第一个数移到最后的最小值（逆序数的变化很明显） 62 if(sum<min1) 63 min1=sum; 64 } 65 printf("%d ",min1); 66 } 67 return 0; 68 }
要得出答案主要是利用了一个结论：如果是0到n的排列，那么如果把第一个数放到最后，对于这个数列，逆序数是减少y[i],而增加n-1-y[i]的。（可以这样想，因为是第一个数，所有的数都在它后面，那么在当前位置pos比它大的数也在它后面，那么第一个数调到后面之后，在pos不成立的逆序数就成立了，所以多了n-y[i]-1，但是也少了在pos成立的逆序数，即y[i]个）
Line belt HDU 3400
三分题：（要进行两次三分求解）
1 #include<stdio.h> 2 #include<iostream> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<string.h> 7 using namespace std; 8 struct point 9 { 10 double x,y; 11 }; 12 double dis(point a,point b) 13 { 14 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 15 } 16 double p,q,r; 17 double find2(point a,point c,point d) 18 { 19 point left,right; 20 point mid,midmid; 21 double t1,t2; 22 left=c; 23 right=d; 24 do 25 { 26 mid.x=(left.x+right.x)/2; 27 mid.y=(left.y+right.y)/2; 28 midmid.x=(mid.x+right.x)/2; 29 midmid.y=(mid.y+right.y)/2; 30 t1=dis(a,mid)/r+dis(mid,d)/q; 31 t2=dis(a,midmid)/r+dis(midmid,d)/q; 32 if(t1>t2) 33 left=mid; 34 else 35 right=midmid; 36 }while(dis(left,right)>=1e-9); 37 return t1; 38 } 39 double find(point a,point b,point c,point d) 40 { 41 point left,right; 42 point mid,midmid; 43 double t1,t2; 44 left=a; 45 right=b; 46 do 47 { 48 mid.x=(left.x+right.x)/2; 49 mid.y=(left.y+right.y)/2; 50 midmid.x=(mid.x+right.x)/2; 51 midmid.y=(mid.y+right.y)/2; 52 t1=dis(a,mid)/p+find2(mid,c,d); 53 t2=dis(a,midmid)/p+find2(midmid,c,d); 54 if(t1>t2) 55 left=mid; 56 else 57 right=midmid; 58 }while(dis(left,right)>=1e-9); 59 return t1; 60 } 61 int main() 62 { 63 int T; 64 point a,b,c,d; 65 scanf("%d",&T); 66 while(T--) 67 { 68 scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y); 69 scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y); 70 scanf("%lf%lf%lf",&p,&q,&r); 71 printf("%.2lf ",find(a,b,c,d)); 72 } 73 return 0; 74 }
之后是到母函数：可以说是模板题了。
Fruit HDU 2152
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int main() 7 { 8 int a[105],b[105]; 9 int c1[10005],c2[10005]; 10 int n,m,i,j,k; 11 while(scanf("%d%d",&n,&m)!=EOF) 12 { 13 for(i=1;i<=n;i++) 14 scanf("%d%d",&a[i],&b[i]); 15 memset(c1,0,sizeof(c1)); 16 memset(c2,0,sizeof(c2)); 17 c1[0]=1; 18 for(i=1;i<=n;i++) 19 { 20 for(j=0;j<=m;j++) 21 for(k=a[i];k<=m&&k<=b[i];k++) 22 c2[k+j]+=c1[j]; 23 for(j=0;j<=m;j++) 24 { 25 c1[j]=c2[j]; 26 c2[j]=0; 27 } 28 } 29 printf("%d ",c1[m]); 30 } 31 return 0; 32 }