算法——贡献法

news/2024/9/19 22:12:54 标签: 算法

前天的AtCoder Beginner Contest 371 D题碰到了这个贡献法，刚好之前的第十一届蓝桥杯省赛第二场真题AcWing 2868. 子串分值也是用的这个方法hh,但是赛时没有搞出来。。。

AcWing 2868. 子串分值

对于一个字符串 SS，我们定义 SS 的分值 f(S)f(S) 为 SS 中恰好出现一次的字符个数。

例如 f(“aba”)=1f(“aba”)=1，f(“abc”)=3f(“abc”)=3, f(“aaa”)=0f(“aaa”)=0。

现在给定一个字符串 S[0…n−1]S[0…n−1]（长度为 nn），请你计算对于所有 SS 的非空子串 S[i…j](0≤i≤j<n)S[i…j](0≤i≤j<n)， f(S[i…j])f(S[i…j]) 的和是多少。

输入格式

输入一行包含一个由小写字母组成的字符串 SS。

输出格式

输出一个整数表示答案。

数据范围

对于 20%20% 的评测用例，1≤n≤101≤n≤10；
对于 40%40% 的评测用例，1≤n≤1001≤n≤100；
对于 50%50% 的评测用例，1≤n≤10001≤n≤1000；
对于 60%60% 的评测用例，1≤n≤100001≤n≤10000；
对于所有评测用例，1≤n≤1000001≤n≤100000。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int l[N],r[N],p[26];
char str[N];
typedef long long ll;
int main(){
    cin>>str+1;
    int n=strlen(str+1);
    for(int i=1;i<=n;i++){
        int t=str[i]-'a';
        l[i]=p[t];
        p[t]=i;
    }
    for(int i=0;i<26;i++)p[i]=n+1;
    for(int i=n;i;i--){
        int t=str[i]-'a';
        r[i]=p[t];
        p[t]=i;
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=(ll)(i-l[i])*(r[i]-i);
    }
    cout<<res;
    return 0;
}

这道题里面一个字符只有恰好出现一次才贡献为1，出现了多次就贡献为0；

所以，只有在L[i]~~R[i]区间内贡献1，超过了就贡献0；

然后，乘法原理得res+=(ll)(i-l[i])*(r[i]-i);。。。记得加（ll)强制类型转换。

p[]的作用是临时数组。

AtCoder Beginner Contest 371 D题

E - I Hate Sigma Problems (atcoder.jp)

Problem Statement

You are given a sequence of integers A=(A1,A2,…,AN)A=(A1,A2,…,AN) of length NN. Define f(l,r)f(l,r) as:

the number of distinct values in the subsequence (Al,Al+1,…,Ar)(Al,Al+1,…,Ar).

Evaluate the following expression:

∑i=1N∑j=iNf(i,j)i=1∑Nj=i∑Nf(i,j).

Constraints

1≤N≤2×1051≤N≤2×105
1≤Ai≤N1≤Ai≤N
All input values are integers.

Input

The input is given from Standard Input in the following format:

NN
A1A1 …… ANAN

Output

Print the answer.

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int a[N],r[N],p[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)p[i]=n+1;
    for(int i=n;i;i--){
        int t=a[i];
        r[i]=p[t];
        p[t]=i;
    }
    ll  res=0;
    for(int i=1;i<=n;i++)
    {
        res+=(ll)(i-0)*(r[i]-i);
    }
    // for(int i=1;i<=n;i++){//用左端点的写法
    //     int t=a[i];
    //     l[i]=p[t];
    //     p[t]=i;
    // }
    // ll res=0;
    // for(int i=1;i<=n;i++){
    //     res+=(ll)(i-l[i])*(n-i+1);
    // }
    cout<<res;
    return 0;
}