（贡献思考+前缀和优化）
//贡献：首先就是找到区间可以最大化1和最小化1（也就是增和减 最多）
//可以猜证明最大化1个数和原来序列中1的个数这段区间是连续的，可以手动模拟一下
//数据量n方会tle
//先考虑怎么最大化1
//前缀和优化，实时记录0~i的区间的贡献（增加1的个数（可能是负数））
//实时记录0~i内贡献最小的
//所以答案就是ans=max（ans，贡献（0~i）-（i前面最小的贡献））
//最小化也同理
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
int n;
signed main()
{
cin>>n;
vector<int> vc(n+1);
for(int i=1;i<=n;i++){
cin>>vc[i];
}
int pre1=0;
int pre0=0;
int mmin1=0;
int mmin0=0;
int mmax1=0;
int mmax0=0;
for(int i=1;i<=n;i++){
if(vc[i]){
pre1++;
}else{
pre1--;
}
mmax1=max(mmax1,pre1-mmin1);
mmin1=min(mmin1,pre1);
}
for(int i=1;i<=n;i++){
if(vc[i]){
pre0--;
}else{
pre0++;
}
mmax0=max(mmax0,pre0-mmin0);
mmin0=min(mmin0,pre0);
}
cout<<1+mmax0+mmax1;（1代表不增不减的个数）
}
[复杂贡献计算题，见校赛补题]
//若干道力扣贡献计算
子串个数题
class Solution {
public:
long long countVowels(string s) {
long long ans=0;
long long n=s.size();
for(int i=0;i<n;i++){
if(s[i]=='a'||s[i]=='e'||'i'==s[i]||s[i]=='o'||s[i] =='u'){
ans+=(n-i)+(i)+(i)*(n-i-1);
}
}
return ans;
}
};
（贡献思考+前缀和优化）
//贡献：首先就是找到区间可以最大化1和最小化1（也就是增和减 最多）
//可以猜证明最大化1个数和原来序列中1的个数这段区间是连续的，可以手动模拟一下
//数据量n方会tle
//先考虑怎么最大化1
//前缀和优化，实时记录0~i的区间的贡献（增加1的个数（可能是负数））
//实时记录0~i内贡献最小的
//所以答案就是ans=max（ans，贡献（0~i）-（i前面最小的贡献））
//最小化也同理
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
int n;
signed main()
{
cin>>n;
vector<int> vc(n+1);
for(int i=1;i<=n;i++){
cin>>vc[i];
}
int pre1=0;
int pre0=0;
int mmin1=0;
int mmin0=0;
int mmax1=0;
int mmax0=0;
for(int i=1;i<=n;i++){
if(vc[i]){
pre1++;
}else{
pre1--;
}
mmax1=max(mmax1,pre1-mmin1);
mmin1=min(mmin1,pre1);
}
for(int i=1;i<=n;i++){
if(vc[i]){
pre0--;
}else{
pre0++;
}
mmax0=max(mmax0,pre0-mmin0);
mmin0=min(mmin0,pre0);
}
cout<<1+mmax0+mmax1;（1代表不增不减的个数）
}
[复杂贡献计算题，见校赛补题]
//若干道力扣贡献计算
子串个数题
class Solution {
public:
long long countVowels(string s) {
long long ans=0;
long long n=s.size();
for(int i=0;i<n;i++){
if(s[i]=='a'||s[i]=='e'||'i'==s[i]||s[i]=='o'||s[i] =='u'){
ans+=(n-i)+(i)+(i)*(n-i-1);
}
}
return ans;
}
};
class Solution {
public:
int sumOddLengthSubarrays(vector<int>& a) {
int n=a.size();
int ans=0;
int sum1=0;
int cnt1=0;
int sum2=0;
int cnt2=0;
int pre=0;
for(int i=0;i<n;i++){
pre+=a[i];
if(i&1){
ans+=pre*cnt1-sum1;
cnt2++;
sum2+=pre;
}else{
ans+=pre+pre*cnt2-sum2;
cnt1++;
sum1+=pre;
}
}
return ans;
}
};
对于子序列题，无序的一般排列后对贡献无影响：并且排序后毅求max和min；其次就是发现子序列的计算方式方式可以计算贡献
class Solution {
public:
int sumOfPower(vector<int>& nums) {
const int MOD = 1'000'000'007;
ranges::sort(nums);
int ans = 0, s = 0;
for (long long x : nums) { // x 作为最大值
ans = (ans + x * x % MOD * (x + s)) % MOD; // 中间模一次防止溢出
s = (s * 2 + x) % MOD; // 递推计算下一个 s
}
return ans;
}
};
//首先排序无影响
解法1：牛逼的对称法，每个ai都作为最大值和最小值，出现的次数就是2^i-2^n-i+1
class Solution {
public:
int sumSubseqWidths(vector<int>& nums) {
const int MOD = 1'000'000'007;
ranges::sort(nums);
int n = nums.size();
vector<int> pow2(n);
pow2[0] = 1;
for (int i = 1; i < n; i++) {
pow2[i] = pow2[i - 1] * 2 % MOD; // 预处理 2 的幂次
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += long(pow2[i] - pow2[n - 1 - i]) * nums[i]; // 在题目的数据范围下，这不会溢出
}
return (ans % MOD + MOD) % MOD; // 注意上面有减法，ans 可能为负数
}
};
//2采用上一题的递推方法
class Solution {
public:
int sumSubseqWidths(vector<int>& a) {
const int mod = 1e9 + 7;
int n = a.size();
sort(a.begin(), a.end());
// 预处理 2 的幂次
vector<long long> pow2(n + 1);
pow2[0] = 1;
for (int i = 1; i <= n; i++) {
pow2[i] = (pow2[i - 1] * 2) % mod;
}
long long ans = 0;
long long g = 0; // 递推变量
for (int i = 1; i < n; i++) {
long long delta = a[i] - a[i - 1];
g = (2 * g % mod + delta *( pow2[i]-1+mod) % mod) % mod; // 递推式
ans = (ans+ g % mod) % mod; // 累加贡献
}
return ans % mod;
}
};
上一题的加强版，有了更多的限制，为了防止重复计算加之k小采用组合数暴力；并且对称也略有不同
const int MOD = 1'000'000'007;
const int MX = 100'001;
long long F[MX]; // F[i] = i!
long long INV_F[MX]; // INV_F[i] = i!^-1
long long pow(long long x, int n) {
long long res = 1;
for (; n; n /= 2) {
if (n % 2) {
res = res * x % MOD;
}
x = x * x % MOD;
}
return res;
}
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
}
return 0;
}();
long long comb(int n, int m) {
return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}
class Solution {
public:
int minMaxSums(vector<int>& nums, int k) {
ranges::sort(nums);
int n = nums.size();
long long ans = 0;
for (int i = 0; i < n; i++) {
long long s1 = 0;
long long s2 = 0;
for (int j = 0; j < min(k, i + 1); j++) {
s1 += comb(i, j);
}
for (int j = i; j < min(k+i, n); j++) {
s2 += comb(n-i-1, j-i);
}
ans = (ans + (s1+s2) % MOD * (nums[i])) % MOD;
}
return ans;
}
};
//以下两道题都是从树的边上思考贡献的：路径是由边组成的，所有路径长度之和，等同于把「每条边出现在多少条路径中」相加
//搭配人数难以思考，逆向思维想人都可以停留，那么每条边要走多少人？
class Solution {
public:
long long ans = 0;
vector<int> adj[10001];
vector<int> dep;
Solution() : dep(10001, 0) {} // 初始化 dep 向量
void dfs(int u, int fa, int seats) {
dep[u] = 1;
for (int son : adj[u]) {
if (son == fa) continue;
dfs(son, u, seats);
dep[u] += dep[son];
}
if (u != 0) { // 不计算根节点的贡献
ans += ceil(dep[u] * 1.0 / seats);
}
}
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
for (auto& road : roads) {
int i = road[0], j = road[1];
adj[i].push_back(j);
adj[j].push_back(i);
}
dfs(0, -1, seats);
return ans;
}
};
