第46届ICPC区域赛(上海)题解

E. Strange_Integers

从小到大排序,贪心即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
vector<ll> a(n);
for(auto &i:a)cin>>i;
sort(a.begin(),a.end());
auto pos=a.begin();
int ans=0;
while(pos<a.end()){
ans++;
pos=lower_bound(pos+1,a.end(),(*pos)+k);
}
cout<<ans;
}

D. Strange_Fractions

,先把 都给约分一下,然后再把右边式子化简一下

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
bool is_int(long double x){
return x==(ll)x;
}
void solve(){
ll p,q;
cin>>p>>q;
ll gcd1=gcd(p,q);
p/=gcd1;
q/=gcd1;
long double delta=sqrt((long double)(p*p-4*q*q));
if(is_int(delta)){
ll d=delta;
ll a2=p+d;
if(a2%2==0){
a2/=2;
ll b2=(p-d)/2;
long double a=sqrt((long double)a2),b=sqrt((long double)b2);
if(is_int(a)&&is_int(b)){
cout<<a<<" "<<b<<"\n";
return;
}
}
}
cout<<"0 0\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}

I. Steadily Growing Steam

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>
using namespace std;
#define ll long long
#define inf (-0x7fffffffffffffff-1)
ll f[2][111][2666];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
for(int i=0;i<=1;i++){
for(int j=0;j<=100;j++){
for(int k=0;k<=2600;k++){
f[i][j][k]=inf;
}
}
}
f[0][0][0]=0;
int n,m;
cin>>n>>m;
vector<ll> v(n+1),t(n+1);
for(int i=1;i<=n;i++){
cin>>v[i]>>t[i];
}
int tt=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=2600;k++){
f[tt][j][k]=f[tt^1][j][k];
if(k>=t[i]&&f[tt^1][j][k-t[i]]!=inf)
f[tt][j][k]=max(f[tt][j][k],f[tt^1][j][k-t[i]]+v[i]);
if(k+t[i]<=2600&&f[tt^1][j][k+t[i]]!=inf)
f[tt][j][k]=max(f[tt][j][k],f[tt^1][j][k+t[i]]+v[i]);
if(j>=1&&k>=2*t[i]&&f[tt^1][j-1][k-2*t[i]]!=inf)
f[tt][j][k]=max(f[tt][j][k],f[tt^1][j-1][k-2*t[i]]+v[i]);
if(j>=1&&k+2*t[i]<=2600&&f[tt^1][j-1][k+2*t[i]]!=inf)
f[tt][j][k]=max(f[tt][j][k],f[tt^1][j-1][k+2*t[i]]+v[i]);
}
}
tt^=1;
}
tt^=1;
ll ans=0;
for(int j=0;j<=m;j++){
ans=max(ans,f[tt][j][0]);
}
cout<<ans;
}

第46届ICPC区域赛(上海)题解

http://blog.therehello.top/2021ICPC-Shanghai/

发布于

2022-04-15

更新于

2022-04-17

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...