- 题意： 给定一个点权为\(a_i\) 边权为\(|a_i-a_j|\) 的完全图，求这个图的最大生成树
- 部分分：
- 100pts：贪心，设权值最大点为\(a_{max}\)，权值最小点为\(a_{min}\) 则\(max(|a_{max}-a_i|,|a_{min}-a_i|)\)一定为\(a_i\)的对答案最大贡献
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define int long long
#define frer freopen("in.in","r",stdin);
#define frew freopen("out.out","w",stdout);
using namespace std;
const int Max = 1e5+10;
int n;
int a[Max];
int e[Max];
int m;
int ans;
inline int read(){
int num=0,fl=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fl=-1;
c=getchar();
}
while(c >='0'&&c <='9'){
num=(num<<3)+(num<<1)+(c^48);
c=getchar();
}
return num*fl;
}
inline bool cmp(int a,int b){
return a>b;
}
signed main(){
n=read();
for(int i = 1;i <= n;i++){
a[i]=read();
}
sort(a+1,a+n+1,cmp);
for(int i = 1;i < n;i++){
e[i]=max(abs(a[1]-a[i]),abs(a[n]-a[i]));
}
sort(e+1,e+n+1,cmp);
for(int i = 1;i < n;i++){
ans+=e[i];
}
printf("%lld",ans);
return 0;
}
- 题意：给定一棵\(n\)个点的有根树，根为节点1，初始每个点都是红色，有次操作，每次操作会把\(p_i\)变成黑色，保证操作序列\(p\)是一个排列，输出有多少个子树是红黑树。
- 部分分：
- 50pts：每次遍历以每个节点为根的子树（没调出来）。
- 80pts: 暴力跳爹（没打）
- 100pts: 差分：用\(fir\)记录每个子树第一个黑点出现的时间，用\(fin\)记录每个子树最后一个红点被覆盖的时间。并用差分维护（可以理解为在区间内此子树一直为红黑树）
- 注意：\(fin\)数组维护差分时为
sum[fin[i]-1+1]，“-1”是因为\(fin[i]\)时此子树已经不是红黑树，“+1”是因为差分。
#include <iostream>
#include <cstdio>
#define int long long
#define frer freopen("in.in","r",stdin);
#define frew freopen("out.out","w",stdout);
using namespace std;
const int Max = 1e5+10;
int n;
int ans,f;
int Head[Max],Next[Max],Ver[Max],tot;
int times[Max];
int fir[Max],fin[Max];
int sum[Max];
inline void add(int x,int y){
Ver[++tot]=y;Next[tot]=Head[x];Head[x]=tot;
}
inline int read(){
int num=0,fl=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fl=-1;
c=getchar();
}
while(c >='0'&&c <='9'){
num=(num<<3)+(num<<1)+(c^48);
c=getchar();
}
return num*fl;
}
inline void dfs(int x){
fir[x]=times[x],fin[x]=times[x];
for(int i = Head[x];i;i=Next[i]){
int y=Ver[i];
dfs(y);
fir[x]=min(fir[x],fir[y]);
fin[x]=max(fin[x],fin[y]);
}
}
signed main(){
frer;
frew;
n=read();
for(int i = 1;i < n;i++){
int x=read();
add(x,i+1);
}
for(int i = 1;i <= n;i++){
int x=read();
times[x]=i;
}
dfs(1);
for(int i = 1;i <= n;i++){
sum[fir[i]]++;
sum[fin[i]-1+1]--;
}
for(int i = 1;i <= n;i++){
ans+=sum[i];
printf("%lld ",ans);
}
return 0;
}
- 题意：校门外有\(n\)棵树，每棵树有一个初始高度\(h_i\)和生长速度\(v_i\)，在接下来的\(m\)天中，第\(i\)棵树会长高\(v_i\)，之后有两种事件可能会发生:
- 操作一：将\([l,r]\)区间内的\(v_i\)增加v。
- 操作二：求\(\sum_{i=l}^{r} h_i\)
- 部分分：