2017acm final

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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 1050
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
#include<bits/stdc++.h>
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
#include<bits/stdc++.h>
#define LL long long
#define N 333
#define n 257
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

文章目录
  1. 1. 2017acm final
    1. 1.1. E
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
    2. 1.2. I
      1. 1.2.1. 参考AC代码
      2. 1.2.2. 思路
    3. 1.3. F
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
|