好久没写题目了，今天趁着校赛选拔把不会的都写一写。

这场ak的人是我见过最多的了，快500人了都（悲），少写一点就500开外了，真是上分（掉分）的好机会啊。

A.小红的陡峭值（一）

陡峭值：数组里所有相邻两个数绝对值之和

判断给出的三个数的陡峭值是否为0，直接模拟就好了

using LL = long long;
void solve(){
    int a1,a2,a3;
    cin>>a1>>a2>>a3;
    if(abs(a1-a2)+abs(a2-a3)==0){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
}

B.小红的陡峭值（二）

给出一个数组，可以将其任意重新排列，能否使得数组的陡峭值尽可能小，输出最小值和对应的方案数。

其实简单分析后可以得知，将其sort从小到大排序后，此时陡峭值之和一定是最小值，倒序也是一样，固有2种方法，再求一下最小值即可。（注意当元素只有一种时只有一种排列方式，这个case应该挡了不少人）

void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1,0);
    int cnt = 0;
    map<int,int> q;
    for(int i=1;i<=n;i++){ 
        cin>>a[i];
        if(!q[a[i]]){
            cnt++;
            q[a[i]]++;
        }
    }
    LL ans = 0;
    sort(a.begin(),a.end());
    for(int i=1;i<n;i++){
        ans+=abs(a[i]-a[i+1]);
    }
    if(cnt==1){//如果此时只有一种元素
        cout<<1<<" "<<ans<<endl;
    }
    else{
        cout<<2<<" "<<ans<<endl;
    }
}

C.小红的陡峭值（三）（easy)

这里定义陡峭值为相邻了两个字符Ascii码的绝对值之和，其实没差。

要求出长度为n的字符串中所有长度为k的连续子串的值之和。

这里的n的范围到1e3,很小，可以考虑直接暴力，但是后面一题的范围就暴力不了了。

我们先考虑暴力做法，先遍历每个字符，然后寻找往后k-1个的连续字串，分离出来，再累加求陡峭值，时间复杂度就是o(n²)了。

using LL = long long;
void solve(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    LL ans = 0;
    for(int i=0;i<n-k+1;i++){
        string t;
        for(int j=i;j<=i+k-1;j++){
            t += s[j];
        }
        for(int j=0;j<t.length()-1;j++){
            ans+=abs(t[j]-t[j+1]);
        }
    }
    cout<<ans<<endl;
}

D.小红的陡峭值（三）（hard）

本题与第三题的区别就是数据量大，无法使用双循环暴力枚举，我们可以考虑贡献法求解。

我们可以先模拟一下，，比如当 abcdef k=3 的时候,会有

abcdef
123456
abc
 bcd 
  cde
   def

不难发现，每个字符出现的次数是有规律的，我们可以采用差分来计算字符出现的次数

for(int i=0;i<n-k+1;i++){
        a[i]++;
        a[i+k]--;
    }

123321 这个就是结果，然后我们还要计算两两之间的陡峭值，可以发现，就是两个字符成对的个数，比如bc 自然在 abc 和bcd里面出现，所以出现次数一定是差分结果中间的小值，而且不会超过k-1,这样我们就得到了核心代码。

using LL = long long;
void solve(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    LL ans = 0;
    vector<int> a(n+1,0);
    for(int i=0;i<n-k+1;i++){
        a[i]++;
        a[i+k]--;
    }
    for(int i=1;i<n;i++){
        a[i]+=a[i-1];
    }
    for(int i=0;i<n-1;i++){
        ans += abs(s[i]-s[i+1])*min(k-1,min(a[i],a[i+1]));//最后还要乘以字符之间的差值
    }
    cout<<ans<<endl;
}

E.小红的陡峭值（四）

给定一棵树，树的陡峭值为连接节点的绝对值之和，要求断掉一条边，求形成两棵树陡峭值之差的最小值。

可以先跑一遍dfs求出整棵树的值，即为1号节点，然后计算每个节点的子数的值，分别存入数组。

再跑一遍dfs，对所有的边进行计算。

设(u,v) f[v] 为以v为根节点的子树值，ans为f[1]

一棵树 f[v]

另一棵树 ans-abs(u-v)-f[v]

枚举取最小值即可

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
vector<int> g[202020];
int n;
LL ans = 1e18;
vector<LL> s(202020,0);
void dfs(int u,int fa){
	for(int i=0;i<g[u].size();i++){
		int t = g[u][i];
		if(t==fa) continue;
		dfs(t,u);
		s[u] += s[t] + abs(u-t);
	}
}
void dfs2(int u,int fa){
	for(int i=0;i<g[u].size();i++){
		int t = g[u][i];
		if(t==fa) continue;
		dfs2(t,u);
        ans = min(ans,abs((s[1]-s[t]-abs(u-t))-s[t]));	
	}
}
void solve(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	dfs2(1,0);
	cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while(t--){
    	solve();
    }
    return 0;
}

FG.小红的陡峭值（五六）（easy-hard）

这里放一手ai✌的数学推理，简单来说还是贡献法求解。

alt

最后贴上代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 1e9+7;
LL kfc(LL x,LL y){
	LL res = 1;
	while(y){
		if(y&1) res = x*res%mod;
		y>>=1;
		x = x*x%mod;
	}
	return res;
}
void solve(){
	int n;
	cin>>n;
	vector<LL> a(n+1,0),fac(n+1,1);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		fac[i] = (fac[i-1]*i)%mod;
	}
	sort(a.begin(),a.end());
	LL sum = 0;
	for(int i=1;i<=n;i++){
		sum += a[i]*(2*i -n - 1);
		if(sum<0) sum+=mod;
		else sum = sum%mod;
	}
	sum = 2*sum%mod;
	cout<<(sum*fac[n-1]%mod*kfc(fac[n],mod-2)%mod)%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while(t--){
    	solve();
    }
    return 0;
}