A题排序然后从l开始由小到大加到不超过最大值即可
B题贪心，但写的烂代码，爆int还tle，看到别人的排序是真帅
D1题是个dp，考虑每个因子的转移，不应该仅想到直接求该数因子，一个考虑遍历方法
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
| LL tt,n,l,r,k;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>tt;
f(sb,1,tt){
cin>>n>>l>>r>>k;
vi v;
f(i,1,n){
int x;
cin>>x;
if(l<=x&&x<=r)v.pb(x);
}
sort(all(v));
int ans=0;
for(auto it:v){
if(k-it>=0){
ans+=1;
k-=it;
}
else break;
}
cout<<ans<<"\n";
}
return 0;
}
|
B
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
| int v[200086];
LL n,tt;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> tt;
f(sb, 1, tt)
{
ull tim=0;
cin >> n;
vi c(n),ans(n);
f(i, 0, n - 1)
{
cin >> v[i];
c[i] =i;
}
sort(all(c),[](LL &a,LL & b){
return v[a]>v[b];
});
f(i,1,n){
ans[c[i-1]]=(i&1?(i+1)>>1:-(i>>1));
tim+=2*abs(ans[c[i-1]])*v[c[i-1]];
}
cout<<tim<<"\n0 ";
f(i,0,n-1){
cout<<ans[i]<<(i==n-1?"\n":" ");
}
}
return 0;
}
|
D1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| LL n,ans=0;
const int N=5e6+86;
int dp[N],cnt[N],m;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
vi v(n);
int ans=0;
f(i,1,n)cin>>v[i-1],m=max(v[i-1],m),cnt[v[i-1]]++;
f(i,1,m){
for(int j=i*2;j<=m;j+=i)cnt[i]+=cnt[j];
}
for(int i=m;i>0;i--){
dp[i]=i*cnt[i];
for(int j=2*i;j<=m;j+=i){
dp[i]=max(dp[i],dp[j]+i*(cnt[i]-cnt[j]));
}
ans=max(dp[i],ans);
}
cout<<ans;
return 0;
}
|