大一训练赛20181105-二分三分分治部分
A题-二分枚举C看是否满足即可，注意真实有可能会出现除0以及出现速度为负值，应该加以判断,舍去。由于C可能很大，或者很小建议开到+-1e9范围。
1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdio.h> 5 #include<math.h> 6 using namespace std; 7 struct node{ 8 int d,s; 9 }a[1005]; 10 int n,t; 11 double ans; 12 int check(double s) 13 { 14 double time=0; 15 for(int i=1;i<=n;i++){ 16 time+=a[i].d*1.0/(a[i].s+s); 17 if (a[i].s+s<0)return 0; 18 } 19 if (time>t)return 0; 20 else return 1; 21 return 1; 22 } 23 24 void fen(double l,double r) 25 { 26 if(r-l>0.00000001) 27 { 28 double mid=(l+r)/2; 29 if (check(mid)) 30 { 31 ans=mid; 32 fen(l,mid); 33 } 34 else 35 { 36 fen(mid,r); 37 } 38 } 39 return; 40 } 41 int main() 42 { 43 while(~scanf("%d%d",&n,&t)) 44 { 45 double l=-1e9,r=1e9; 46 for (int i=1;i<=n;i++){ 47 48 scanf("%d%d",&a[i].d,&a[i].s); 49 } 50 fen(l,r); 51 printf("%.9f\n",ans); 52 } 53 return 0; 54 }
B题-利用前缀和保存字符对x,y坐标的贡献，然后去二分最短的区间，然后判段这一段的区间是否满足，满足条件就是我需要走的步数是小于等于我这段区间的长度，并且剩下的必须是偶数步。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 const int maxx = 2e5+10; 7 int n; 8 int x,y; 9 char s[maxx]; 10 int a[maxx]; 11 int b[maxx]; 12 int ans=-1; 13 bool check(int len) 14 { 15 for (int i=1; i+len-1<=n; i++) 16 { 17 int xx = a[n] - a[i+len-1] + a[i-1]; 18 int yy = b[n] - b[i+len-1] + b[i-1]; 19 int tx = x-xx; 20 int ty = y-yy; 21 if (abs(tx)+abs(ty)<=len && (len-abs(tx)-abs(ty))%2==0) 22 return true; 23 } 24 return false; 25 } 26 void fen(int l,int r) 27 { 28 int mid = (l+r)/2; 29 if (l<=r) 30 { 31 if (check(mid)) 32 { 33 ans=mid; 34 fen(l,mid-1); 35 } 36 else 37 { 38 fen(mid+1,r); 39 } 40 } 41 } 42 int main() 43 { 44 while(~scanf("%d",&n)) 45 { 46 scanf("%s",s+1); 47 scanf("%d%d",&x,&y); 48 a[0]=0; 49 b[0]=0; 50 for (int i=1; i<=n; i++) 51 { 52 if(s[i]=='R') 53 { 54 a[i]=a[i-1]+1; 55 b[i]=b[i-1]; 56 } 57 else if (s[i]=='L') 58 { 59 a[i]=a[i-1]-1; 60 b[i]=b[i-1]; 61 } 62 else if (s[i]=='U') 63 { 64 a[i]=a[i-1]; 65 b[i]=b[i-1]+1; 66 } 67 else 68 { 69 a[i]=a[i-1]; 70 b[i]=b[i-1]-1; 71 } 72 } 73 ans=-1; 74 fen(0,n); 75 printf("%d\n",ans); 76 } 77 return 0; 78 }
C题-二分答案即可
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 using namespace std; 5 int m,n; 6 int a[100005]; 7 bool check(int mid) 8 { 9 int num=0; 10 for (int i=1; i<=m; i++) 11 { 12 num++; 13 int j=i; 14 int res=0; 15 while (j<=m) 16 { 17 res+=a[j]; 18 if (res>mid) 19 { 20 j--; 21 break; 22 } 23 j++; 24 } 25 i=j; 26 } 27 return(num<=n); 28 } 29 30 int main() 31 { 32 while(~scanf("%d%d",&m,&n)) 33 { 34 int sum=0; 35 int maxx = 0; 36 for (int i=1; i<=m; i++) 37 { 38 scanf("%d",&a[i]); 39 maxx=max(maxx,a[i]); 40 sum=sum+a[i]; 41 } 42 int res=0; 43 int l=maxx; 44 int r=sum; 45 int mid; 46 while (l<=r) 47 { 48 mid=(l+r)/2; 49 if (check(mid)) 50 { 51 res=mid; 52 r=mid-1; 53 } 54 else 55 { 56 l=mid+1; 57 } 58 } 59 printf("%d\n",res); 60 } 61 return 0; 62 }
D题-贪心+二分答案判断即可。让每个位置的值尽可能的小，同时保证要大于前一个，因此当这个值能降到前一个值+1的情况，就变成a[i]=a[i]+1，如果能降到最小大于前一个，就降到最小，否则不合理。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int ans; int a[100007]; int b[100007]; int n; bool check(int x) { for (int i=1; i<=n; i++) { if (i==1) { b[i]=a[i]-x; } else { if (b[i-1]+1>=a[i]-x && a[i]+x>=b[i-1]+1) { b[i]=b[i-1]+1; } else if (a[i]-x>=b[i-1]+1) { b[i]=a[i]-x; } else { return 0; } } } return 1; } void fen(int l,int r) { int mid=(l+r)/2; if (l<=r) { if (check(mid)) { ans=mid; fen(l,mid-1); } else { fen(mid+1,r); } } } int main() { int t; scanf("%d",&t); int cnt=0; while(t--) { cnt++; scanf("%d",&n); int maxx=0; for(int i=1; i<=n; i++) { scanf("%d",&a[i]); maxx=max(maxx,a[i]); } fen(0,1000005); printf("Case #%d:\n",cnt); printf("%d\n",ans); } return 0; }
E题-贪心+二分答案 和C题一样。
1 #include<iostream> 2 #include<algorithm> 3 #include<string.h> 4 #include<stdio.h> 5 using namespace std; 6 const int maxx = 2000006; 7 int ans; 8 int a[maxx]; 9 int n,m; 10 bool check(int x) 11 { 12 int d=0; 13 for (int i=1; i<=n; i++) 14 { 15 if (a[i]%x==0) 16 { 17 d+=a[i]/x; 18 } 19 else 20 { 21 d+=(a[i]/x+1); 22 } 23 if (d>m)return 0; 24 } 25 return 1; 26 } 27 void fen(int l,int r) 28 { 29 //cout<<l<<" "<<r<<endl; 30 int mid=(l+r)/2; 31 if (l<=r) 32 { 33 if (check(mid)) 34 { 35 ans=mid; 36 fen(l,mid-1); 37 } 38 else 39 { 40 fen(mid+1,r); 41 } 42 } 43 } 44 int main() 45 { 46 while(~scanf("%d%d",&n,&m)) 47 { 48 if (n==-1 && m==-1)break; 49 int maxx=0; 50 for (int i=1; i<=n; i++) 51 { 52 scanf("%d",&a[i]); 53 maxx=max(maxx,a[i]); 54 } 55 fen(1,maxx); 56 printf("%d\n",ans); 57 } 58 return 0; 59 }
F题-归并排序-课上原题
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int a[10005]; 7 int n; 8 int b[10005]; 9 int ans=0; 10 void gb(int l,int r){ 11 if (l==r)return; 12 int mid=(l+r)/2; 13 gb(l,mid); 14 gb(mid+1,r); 15 int i=l,j=mid+1,k=l; 16 while(i<=mid && j<=r) 17 { 18 if (a[i]<=a[j]) 19 { 20 b[k]=a[i]; 21 k++; 22 i++; 23 }else 24 { 25 b[k]=a[j]; 26 k++; 27 j++; 28 ans+=(mid-i+1); 29 } 30 } 31 while(i<=mid) 32 { 33 b[k]=a[i]; 34 k++; 35 i++; 36 } 37 while(j<=r) 38 { 39 b[k]=a[j]; 40 k++; 41 j++; 42 } 43 for (int i=l;i<=r;i++) 44 a[i]=b[i]; 45 } 46 int main(){ 47 while(~scanf("%d",&n)){ 48 ans=0; 49 for (int i=1;i<=n;i++){ 50 scanf("%d",&a[i]); 51 } 52 gb(1,n); 53 54 printf("%d\n",ans); 55 } 56 return 0; 57 }
G题-物理题，三分，按照物理写出最大距离的公式，三分答案就行
1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdio.h> 5 #include<math.h> 6 using namespace std; 7 const double pi = acos(-1); 8 const double g = 9.8; 9 int h; 10 int v; 11 double ans; 12 double check(double a) 13 { 14 return v*cos(a)*(v*sin(a)/g+sqrt(2*h/g+v*v*sin(a)*sin(a)/(g*g))); 15 } 16 void fen(double l,double r) 17 { 18 double mid_l,mid_r; 19 if (r-l>=0.000001){ 20 mid_l=(r-l)/3+l; 21 mid_r=r-(r-l)/3; 22 if (check(mid_l)<check(mid_r)){ 23 fen(mid_l,r); 24 ans=max(ans,check(mid_r)); 25 } 26 else { 27 fen(l,mid_r); 28 ans=max(ans,check(mid_l)); 29 } 30 } 31 } 32 int main(){ 33 int t; 34 scanf("%d",&t); 35 while(t--) 36 { 37 scanf("%d%d",&h,&v); 38 ans=0; 39 double l=0.00; 40 double r=pi/2; 41 fen(l,r/2); 42 printf("%.2f\n",ans); 43 } 44 return 0; 45 }
H题-最近邻点问题，分治，分两部分考虑，左边和右边，最后求出一个左边和右边的最小值之一，然后取这个最小值来优化判断一个在左边，一个在右边的情况。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<math.h> 6 using namespace std; 7 const int maxx = 1e5+7; 8 const double INF = 1e20; 9 struct node{ 10 double x,y; 11 }p[maxx]; 12 node b[maxx]; 13 double dist(node a,node b) 14 { 15 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 16 } 17 bool cmp1(node a,node b) 18 { 19 if (a.x==b.x) return a.y<b.y; 20 else return a.x<b.x; 21 } 22 bool cmp2(node a,node b) 23 { 24 return a.y<b.y; 25 } 26 double nearest(int left,int right) 27 { 28 double d = INF; 29 if(left == right)return d; 30 if(left + 1 == right) 31 return dist(p[left],p[right]); 32 int mid = (left+right)/2; 33 double d1 = nearest(left,mid); 34 double d2 = nearest(mid+1,right); 35 d = min(d1,d2); 36 int k = 0; 37 for(int i = left; i <= right; i++) 38 { 39 if(fabs(p[mid].x - p[i].x) <= d) 40 b[k++] = p[i]; 41 } 42 sort(b,b+k,cmp2); 43 for(int i = 0; i <k; i++) 44 { 45 for(int j = i+1; j < k && b[j].y - b[i].y < d; j++) 46 { 47 d = min(d,dist(b[i],b[j])); 48 } 49 } 50 return d; 51 } 52 int main() 53 { 54 int n; 55 while(~scanf("%d",&n) && n) 56 { 57 for (int i=0;i<n;i++){ 58 scanf("%lf%lf",&p[i].x,&p[i].y); 59 } 60 sort(p,p+n,cmp1); 61 printf("%.2f\n",nearest(0,n-1)/2); 62 } 63 return 0; 64 }
