2017acm final
E
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| using namespace std; int n,t; double d[maxn],s[maxn]; double ans=-1; bool check(double x){ double ret=0; for(int i=1;i<=n;i++) ret+=d[i]/(s[i]+x); return ret>=t; } int main(){ // freopen("input.txt","r",stdin); ios::sync_with_stdio(false); cin.tie(0); cin>>n>>t; int Min=inf; for(int i=1;i<=n;i++){ cin>>d[i]>>s[i]; Min=min(Min,(int)s[i]); } Min=-Min; double l=(double)Min,r=1000000000.0,mid=0.0; while(l-r<=1e-7){ mid=(l+r)/2.0; if(check(mid)){ ans=mid; l=mid+1e-7; } else r=mid-(1e-7); } printf("%.6lf\n",ans); return 0; }
|
思路
二分答案
注意精度 下限用速度必须非负算出 上限1e9
check里返回ret>=t
I
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| int g[30][30]; using namespace std; int main(){ // freopen("input.txt","r",stdin); ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>m>>n; memset(g,0,sizeof(g)); for(int i=1;i<=m;i++){ char a,b; cin>>a>>b; g[a-'a'][b-'a']=1; } for(int i=0;i<26;i++){ for(int j=0;j<26;j++){ if(g[i][j]==1){ for(int k=0;k<26;k++){ if(g[k][i]==1) g[k][j]=1; } } } } for(int i=1;i<=n;i++){ string s1,s2; cin>>s1>>s2; if(s1.length()!=s2.length()){ cout<<"no"<<endl; continue; } int flag=0; for(int j=0;j<s1.length();j++){ if((s1[j]==s2[j])||(s1[j]!=s2[j]&&g[s1[j]-'a'][s2[j]-'a']==1)) flag++; } if(flag==s1.length()) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }
|
思路
n大小为26暴力即可
类似存图的关系存储转换关系
F
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| const LL inf =1e18; using namespace std; LL f[N][N],cost[N][N]; int a[N]; int main(){ // freopen("input.txt","r",stdin); ios::sync_with_stdio(false); cin.tie(0); int d,p; cin>>d>>p; p++; for(int i=0;i<d;i++){ int x,y; cin>>x>>y; a[x+1]=y; } for(int i=0;i<n;i++){ for(int j=i+1;j<=n;j++){ cost[i][j]=0; for(int k=i+1;k<=j-1;k++){ int dist=min(i==0?n:k-i,j==n?n:j-k); cost[i][j]+=a[k]*1LL*dist*dist; } } } for(int i=0;i<=n;i++){ for(int j=0;j<=p;j++){ f[i][j]=inf; } } f[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<p;j++){ if(f[i][j]==inf) continue; for(int k=i+1;k<=n;k++){ f[k][j+1]=min(f[k][j+1],f[i][j]+cost[i][k]); } } } cout<<f[n][p]<<endl; return 0; }
|
思路
dp