题目链接：Educational Codeforces Round 52 (Rated for Div. 2)
A：先暴力全部买，然后看能免费买几个即可。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,s,a,b,c;
inline void solve(){
cin>>s>>a>>b>>c; int res=0;
res=s/c; res+=(res/a)*b;
cout<<res<<'\n';
}
signed main(){
cin>>T;
while(T--) solve();
return 0;
}
B：对于最少的孤立点，肯定先两两之间连，对于最多的孤立点，肯定考虑最少的点最多连多少边。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,res1,res2=2;
signed main(){
cin>>n>>m;
res1=max(0LL,n-2*m);
while((res2-1)*res2/2<m) res2++;
if(m==0) res1=n,res2=0;
cout<<res1<<' '<<n-res2;
return 0;
}
C：先做差分，然后前缀和得到原序列，然后再前缀和。最后扫一遍，贪心处理。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,k,h[N],sum[N],s,mx,res,mi=1e9;
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>h[i],sum[h[i]]++,mx=max(mx,h[i]),mi=min(mi,h[i]);
for(int i=mx;i>=mi;i--) sum[i]+=sum[i+1];
for(int i=mx;i>mi;i--){
s+=sum[i];
if(s>k){
res++; s=sum[i];
}
}
if(s>0) res++;
cout<<res;
return 0;
}
F：树DP，不难想到，我们可以先处理能过走回来的最大价值，然后再考虑从哪个点一直往下，不用回来情况。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
int n,k,dp[N],low[N],res[N],dep[N];
vector<int> g[N];
void dfs1(int x,int fa){
dep[x]=dep[fa]+1;
if(g[x].size()==0){
dp[x]=1; low[x]=dep[x]; return ;
}
int mi=1e9,val=0;
for(auto to:g[x]){
dfs1(to,x);
if(low[to]-dep[x]<=k){
val+=dp[to]; mi=min(mi,low[to]);
}
}
low[x]=mi; dp[x]=val;
}
void dfs2(int x){
res[x]=dp[x];
for(auto to:g[x]){
dfs2(to); int tmp=dp[x];
if(low[to]-dep[x]<=k) tmp-=dp[to];
res[x]=max(res[x],tmp+res[to]);
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>k;
for(int i=2,x;i<=n;i++) cin>>x,g[x].push_back(i);
dfs1(1,0); dfs2(1);
cout<<res[1];
return 0;
}