
贡献法应用
贡献法适用于答案由大量方案、区间或组合共同构成的情形。直接枚举这些整体对象通常会产生重复计算;更有效的方式是选择一个更小的基本对象,统计它在多少个整体答案中出现,并把“出现次数 单次贡献”累加。
本文的两道题都属于这一类:数组差异题把贡献对象选为排序后的数对或单个元素;函数题把贡献对象选为差分数组中的某个位置。
问题 E:数组差异
题目重述
给定 个数,从中选择 个数组成新数组。一个数组的差异度定义为其中任意两数差值的绝对值之和。要求所有 种选择方案的差异度总和,并对 取模。
关键观察
将数组排序为
排序后任意一对下标 的差值为 。固定这对数后,若一个 元选择方案包含它们,则这对数向该方案的差异度贡献 。剩余 个数可从其余 个位置中选择,因此该数对被计入
次。
也可以进一步按单个元素统计。固定 :
- 它作为较大值时,与前面 个数形成正贡献;
- 它作为较小值时,与后面 个数形成负贡献。
因此 的系数为 。
解析
根据上面的计数,答案为
组合数通过阶乘和逆元预处理。由于模数 为质数,使用快速幂计算 得到乘法逆元。
时间复杂度为 ,瓶颈在排序;空间复杂度为 。
代码
#include <bits/stdc++.h>#include <iomanip>#define ll long long#define N 200005using namespace std;ll ans;ll n, k;ll t;const ll mod = 1e9 + 7;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; vector<ll> s(n + 5, 0); vector<ll> fact(n + 5, 0); vector<ll> fact_inv(n + 5, 0); for (int i = 1; i <= n; i++) { cin >> s[i]; } sort(s.begin() + 1, s.begin() + n + 1); auto qp = [&](ll x, ll k) { ll res = 1; while (k) { if (k & 1) res = (res * x) % mod; x = (x * x) % mod; k >>= 1; } return res; }; auto init = [&]() { fact[0] = 1; fact_inv[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % mod; fact_inv[i] = (fact_inv[i - 1] * i) % mod; } fact_inv[n] = qp(fact[n], mod - 2); for (int i = n - 1; i >= 1; i--) { fact_inv[i] = ((i + 1) * fact_inv[i + 1]) % mod; } }; init(); auto c = [&](ll n, ll m) { return (fact[n] * fact_inv[m] % mod * fact_inv[n - m] % mod); }; ll res = 0; for (int i = 1; i <= n; i++) { res = (res + (i - 1 - (n - i)) * s[i]) % mod; } res = (res * c(n - 2, k - 2)) % mod; cout << res; return 0;}问题 C:函数
题目重述
给定长度为 的序列 和 次询问。对于每个区间 ,要求所有连续子序列 ()的 Lipschitz 常数之和。
序列 的 Lipschitz 常数定义为满足
的最小整数 ,其中 。
关键观察
令相邻差分为
对任意 ,由三角不等式可得
因此 一定满足 Lipschitz 条件。
另一方面,若 是区间内的最大相邻差分,取相邻两点 ,则
所以任意合法的 都不能小于最大相邻差分。两边合并,连续子序列 的 Lipschitz 常数恰好等于差分区间 的最大值。

解析
询问 被转化为:求差分数组 的所有非空连续子数组最大值之和。
对每个差分位置 计算其作为最大值的贡献。设:
- 为 左侧最近的、满足 的位置;若不存在,则为 ;
- 为 右侧最近的、满足 的位置;若不存在,则为 。
左侧使用严格大于、右侧使用大于等于,是为了处理相等最大值。若一个子数组中最大值出现多次,这种边界定义会固定由其中一个位置承担贡献,避免重复计数。
当 作为某个差分子数组的最大值时,左端点可选
种,右端点可选
种。因此 的总贡献为
每次询问用两遍单调栈求出左右边界,再累加所有位置的贡献。由于 ,按询问逐个线性处理区间即可通过。
单次询问复杂度为 ,总时间复杂度为 ,空间复杂度为 。
代码
#include <bits/stdc++.h>#include <iomanip>#include <utility>#define ll long long#define N 200005using namespace std;ll ans;ll n, k, m, q;ll t;#define pr pair<ll, ll>int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; vector<ll> s(n + 5, 0); vector<ll> diff(n + 5, 0); for (int i = 1; i <= n; i++) { cin >> s[i]; diff[i - 1] = abs(s[i] - s[i - 1]); } vector<int> left(n + 5, 0); vector<int> right(n + 5, 0); while (q--) { ll l, r; cin >> l >> r; if (l == r) { cout << 0 << '\n'; continue; } r--; stack<int> sta; for (int i = l; i <= r; i++) { while (sta.size() && diff[sta.top()] <= diff[i]) { sta.pop(); } left[i] = sta.empty() ? l - 1 : sta.top(); sta.push(i); } while (sta.size()) sta.pop(); for (int i = r; i >= l; i--) { while (sta.size() && diff[sta.top()] < diff[i]) { sta.pop(); } right[i] = sta.empty() ? r + 1 : sta.top(); sta.push(i); } ll res = 0; for (int i = l; i <= r; i++) res += diff[i] * (i - left[i]) * (right[i] - i); cout << res << '\n'; } return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 0 天
部分内容可能已过时