@TryMyEdge
2017-03-07T09:33:53.000000Z
字数 5558
阅读 966
题解
A Strange fuction
题目大意：
F(x)=6*x^7+8*x^6+7*x^3+5*x^2-y*x，给定y(0<y<10^10)，求当0<=x<=100时F(x)的最小值。
T(T<=100)组数据。
解题思路：
F'(x)=42*x^6+48*x^5+21*x^2+10x-y，因为0<=x<=100，所以F'(x)是递增的。二分找到F'(x)最接近0的位置，此时的x对应F(x)的最小值。
时间复杂度o(T*log(10^8))，空间复杂度o(1)。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007double y;double gg(double x){return 42*x*x*x*x*x*x+48*x*x*x*x*x+21*x*x+10*x-y;}double ask(){double l=0,r=100;while(r-l>0.00001){if(gg((l+r)/2)<0)l=(l+r)/2;elser=(l+r)/2;}return (l+r)/2;}int main(){int t;double x;cin>>t;while(t--){cin>>y;x=ask();printf("%.4f\n",6*x*x*x*x*x*x*x+8*x*x*x*x*x*x+7*x*x*x+5*x*x-y*x);}return 0;}
B Can you find it?
题目大意：
给三个长度分别为L、M、N(1<=L，N，M<=500)的数列A、B、C，然后有S(1<=S<=1000)个询问，每个询问包含一个整数X，问是否存在Ai+Bj+Ck=X。A、B、C中的数和X都为32位整数。
多组数据，EOF。
解题思路：
一种比较朴素的想法是把所有Ai+Bj+Ck的情况枚举出来然后对于每个询问二分查询是否存在某个组合的值为X。时间复杂度为o(L*M*N*log(L*M*N)+S*log(L*M*N))，空间复杂度为o(L*M*N)，BOOM！
我们注意到预处理的时空复杂度都很爆炸，于是我们考虑把预处理的复杂度降下来，摊分到查询中去，具体做法为把所有Ai+Bj的情况枚举出来，然后对于每个询问枚举Ck，二分查询是否存在某个组合的值为X-Ck。
32位整数就不可能用数组打表了，多组的情况下map也会炸。。。
时间复杂度o(L*M*log(L*M)+S*N*log(L*M))，空间复杂度o(L*M)。
AC代码：
#include<iostream>#include<bits/stdc++.h>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int numa[505],numb[505],numc[505];int nums[250005],len;int a,b,c,t=0;bool ask(int x){int l=0,r=len-1,mid;while(l<r){mid=(l+r)/2;if(nums[mid]<x)l=mid+1;elser=mid;}return nums[l]==x;}bool ok(int x){for(int i=0;i<c;i++){if(ask(x-numc[i]))return 1;}return 0;}int main(){int s,now;while(~scanf("%d%d%d",&a,&b,&c)){len=0;t++;printf("Case %d:\n",t);for(int i=0;i<a;i++)scanf("%d",numa+i);for(int i=0;i<b;i++)scanf("%d",numb+i);for(int i=0;i<c;i++)scanf("%d",numc+i);for(int i=0;i<a;i++)for(int j=0;j<b;j++)nums[len++]=numa[i]+numb[j];sort(nums,nums+len);scanf("%d",&s);for(int i=0;i<s;i++){scanf("%d",&now);if(ok(now))printf("YES\n");elseprintf("NO\n");}}return 0;}
C Monthly Expense
题目大意：
有N(1<=N<=10^5)天，第i天的花费为Pi(1<=Pi<10^4)，现在将这N天分成M(1<=M<=N)段，每段包含的天数至少为1并且这些天连续，每一段的预算为这一段中的花费的总和，问预算最多的一段的预算至少为多少。
解题思路：
当预算确定的时候，我们可以看出最优策略是当前段如果剩余预算足够支付当前天的花费就把当前天算入当前段，否则把当前天算入下一段，并且当前段结束。于是在确定预算的情况下我们可以知道需要多少段。
二分预算，判断段数是否大于M。
小细节：我用的是左闭右闭的二分方法，二分的左端点初值为Pmax，右端点初值为sum(Pi)。
时间复杂度o(N*log(sum(Pi)))，空间复杂度o(N)。
AC代码：
#include<iostream>#include<cstdio>#include<cmath>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int num[100005],n,m,l=0,r=0;int ask(int x){int now=0,ans=1;for(int i=0;i<n;i++){if(now+num[i]<=x)now+=num[i];else{ans++;now=num[i];}}return ans;}int main(){cin>>n>>m;for(int i=0;i<n;i++){scanf("%d",num+i);l=max(l,num[i]);r+=num[i];}int mid;while(l<r){mid=(l+r)/2;if(ask(mid)<=m)r=mid;elsel=mid+1;}cout<<l<<endl;return 0;}
D River Hopscotch
题目大意：
有一条宽为L(1<=L<=10^9)，河中有N(0<=N<=50000)块石头，每块石头离出发点的距离为Di(0<Di<L)，从中移走M(0<=M<=N)块石头，问从出发点到终点，距离最短的一次跳跃最大值为多少。
解题思路：
如果考虑移走哪些石头，那复杂度就会是指数级别的，BOOM！
于是我们反过来考虑，如果确定了一个最短距离，那么当下一个位置和当前位置距离超过最短距离的时候就跳过去，否则就移掉一块石头，由此可以知道每个最短距离至少需要移走多少块石头才能实现。
二分最短距离，判断需要移走的石头数是否大于M。
依然是左闭右闭的二分:二分的左端点初值为0，右端点初值为L。
小细节：注意把终点也加到石头序列里。
时间复杂度o(N*log(L))，空间复杂度o(N)。
AC代码:
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int l,n,m;int num[50005];int gg(int x){int now=0,ans=0;for(int i=0;i<=n;i++){if(num[i]-now<x)ans++;elsenow=num[i];}return ans;}int main(){cin>>l>>n>>m;for(int i=0;i<n;i++)scanf("%d",num+i);num[n]=l;sort(num,num+n);int lans=0,rans=l,mid;while(lans<rans){mid=(lans+rans)/2+1;if(gg(mid)>m)rans=mid-1;elselans=mid;}cout<<lans<<endl;return 0;}
E Communication System
题目大意：
有N(1<=N<=100)种设备，第i种设备有Mi(1<=Mi<=100)种选择，每个设备有两个属性带宽B和价格P，整套系统的总带宽为所选设备中最小的带宽值，总价格为所选设备的总价格，求总带宽除以总价格的最大值。
B和P都是正整数，范围不超过int。
T(T<=10)组数据。
解题思路：
枚举带宽，在每一种设备用二分搜索能满足带宽要求的最低价格来求出总价格，更新答案。
需要预处理两个内容：(1)需要保证枚举的某一个带宽都能有方案可以满足；(2)保证每个带宽对应的价格是满足该带宽需求的最小价格。第一点容易实现，第二点要先将每种设备的备选按照带宽从小到大，如果带宽相同价格从大到小的顺序排序，然后从后往前用更小的价格去更新前面的选择。因为后面的选择带宽一定大于等于前面的，如果带宽相同，价格又一定小于等于前面的，所以可以覆盖前面的需求。
时间复杂度o(T*sum(Mi)*sum(log(Mi)))，空间复杂度o(sum(Mi))。
AC代码：
#include<iostream>//#include<bits/stdc++.h>#include<cstdio>#include<cmath>#include<algorithm>#define pq priority_queue#define Pi acos(-1.0)using namespace std;int m[105],n;struct Prod{int b,p;}pr[105][105];int num[10005];bool cmp(Prod x1,Prod x2){if(x1.b==x2.b)return x1.p>x2.p;elsereturn x1.b<x2.b;}double ask(int x){double now=0;int l,r,mid;for(int i=1;i<=n;i++){l=1;r=m[i];while(l!=r){mid=(l+r)/2;if(pr[i][mid].b>=x)r=mid;elsel=mid+1;}now+=pr[i][l].p;}return x/now;}int main(){int t,temp,rr,len;double ans;cin>>t;while(t--){ans=0;cin>>n;for(int i=1;i<=n;i++){scanf("%d",m+i);temp=0;for(int j=1;j<=m[i];j++){scanf("%d%d",&pr[i][j].b,&pr[i][j].p);temp=max(temp,pr[i][j].b);}if(i>1)rr=min(rr,temp);elserr=temp;}len=0;for(int i=1;i<=n;i++){for(int j=1;j<=m[i];j++)if(pr[i][j].b<=rr)num[len++]=pr[i][j].b;sort(pr[i]+1,pr[i]+1+m[i],cmp);for(int j=m[i]-1;j;j--)if(pr[i][j].p>pr[i][j+1].p)pr[i][j].p=pr[i][j+1].p;}sort(num,num+len);for(int i=0;i<len;i++)ans=max(ans,ask(num[i]));printf("%.3f\n",ans);}return 0;}
F Light Bulb
题目大意：
一个身高为h(0.01<=h<=1000)的人站在房子中，他左边有一盏高度为H(0.01+h<=H<=1000)的灯，右边有一面墙，灯和墙的水平距离为D(0.01<=D<=1000)，问这个人的影子的长度最长为多少。
T(T<=100)组数据。
解题思路：
这题其实可以直接推公式求最值2333333
给定人和灯的水平距离，分影子全在地上和有一部分在墙上，可以算出影子的长度。
影子长度关于人灯距离的图像是一个凸型函数，所以可以三分人灯距离。
小细节：注意结束条件的设置。
时间复杂度o(T*log(D*10^7))，空间复杂度o(1)。
AC代码：
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#define pq priority_queue#define Pi acos(-1.0)using namespace std;double H,h,D;double ask(double x){return D+H-x-D*(H-h)/x;}int main(){int t;cin>>t;double l,r,mid1,mid2;while(t--){cin>>H>>h>>D;l=(H-h)*D/H;r=D;while(r-l>0.0000001){mid1=l+(r-l)/3;mid2=l+r-mid1;if(ask(mid1)<ask(mid2))l=mid1;elser=mid2;}printf("%.3f\n",max(ask(l),ask(r)));}return 0;}