2024台湾ICPC网络赛 B.Business Magic
目的：找出用蓝色魔法最优的那段区间。
计算每个数用蓝色魔法和绿色魔法的贡献差值，累加到sum中，若sum比之前存的贡献差值res更大则更新res，若sum为正数则说明当前枚举的则一段用蓝色魔法比绿色魔法更优，若sum出现负数则说明若当前该数用蓝色魔法的贡献小于绿色魔法的贡献，则当前区间到此为止，以下一个数为起点枚举下一个区间，因为当前数用蓝色魔法的贡献减绿色魔法的贡献为负数，若从当前数字开始枚举区间则会更劣。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+10;
int a[N];

signed main()
{
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    int sum = 0, res = 0, ll=1, l=1, r;
    for(int i=1; i<=n; i++)
    {
        sum += (a[i]*2-abs(a[i]));//计算用俩种操作的贡献差值
        if(sum < 0) sum = 0, ll = i+1;
        if(sum > res)
        {
            res = sum;
            l = ll;
            r = i;
        }
    }
    int ans = 0;
    for(int i=1; i<=n; i++)
    {
        if(i >= l && i <= r)
        {
            ans += a[i]*2;
        }
        else ans += abs(a[i]);
    }
    cout << ans;
    return 0;
}

4261. 孤独的照片

若枚举每个区间则需要O(n^2)，计算每头牛的贡献最后累加到答案则只需要O(n)的复杂度，观察每头牛对区间的影响范围，发现其影响范围为左边相同的牛到右边相同的牛之内

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+10;
int l[N], r[N];
string s;

signed main()
{
    int n;
    cin >> n >> s;
    //预处理出每头牛左边和右边与连续其不相同品种牛的数量的个数
    for(int i=0, sh=0, sg=0; i<n; i++)
        if(s[i] == 'H') l[i] = sg, sh++, sg = 0;
        else if(s[i] == 'G') l[i] = sh, sh = 0, sg++;

    for(int i=n-1, sh=0, sg=0; i>=0; i--)
        if(s[i] == 'H') r[i] = sg, sh++, sg = 0;
        else if(s[i] == 'G') r[i] = sh, sh=0, sg++;
    int ans = 0;
    for(int i=0; i<n; i++)
        ans += l[i]*r[i]+max(0LL, r[i]-1)+max(0LL, l[i]-1);//累加每头牛的贡献
    cout << ans;
    return 0;
}

3689. 约数求和
直接求每个数的约数再累加会超时，考虑直接计算每个约数对总答案的贡献最后累加

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i=1; i<=n; i++)
        ans += n/i*i;   //计算每个约数的贡献
    cout << ans;
    return 0;
}

2868. 子串分值
若枚举每一个区间计算则时间复杂度为O(n^2)，考虑枚举每个字符所影响的区间个数，即对答案的贡献是多少最后累加，时间复杂度O(n)
代码1

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int l[N], r[N];
int c[30];

signed main()
{
    string s;
    cin >> s;
    memset(c, -1, sizeof c);
    //计算每个字符左边有多少个非s[i]的数
    for(int i=0; i<s.size(); i++)
    {
        if(i == 0)
            l[i] = 0;
        else if(c[s[i]-'a'] == -1)
            l[i] = i;
        else l[i] = i-c[s[i]-'a']-1; 
        c[s[i]-'a'] = i;
    }
    memset(c, -1, sizeof c);
    //计算每个字符右边有多少个非s[i]的数
    for(int i=s.size()-1; i>=0; i--)
    {
        if(i == s.size()-1)
            r[i] = 0;
        else if(c[s[i]-'a'] == -1)
            r[i] = s.size()-1-i;
        else r[i] = c[s[i]-'a']-i-1;
        c[s[i]-'a'] = i;
    }
    int ans = 0;
    //统计答案
    for(int i=0; i<s.size(); i++)
        ans += l[i]*r[i]+l[i]+r[i]+1;
    cout << ans;
    return 0;
}

代码2

 #include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int l[N], r[N];
char str[N];
int p[30];

signed main()
{
    scanf("%s", str+1);
    int n = strlen(str+1);
    //计算左边第一个相同字符的位置，设置哨兵，因为若字符第一次出现则可认为前一个字符的位置为0，方便计算
    for(int i=1; i<=n; i++)
    {
        int t = str[i]-'a';
        l[i] = p[t];
        p[t] = i;
    }
    //计算左边第一个相同字符的位置，最后一个字符设置为哨兵，因为若字符第一次出现则可认为后一个字符的位置为n+1

    for(int i=0; i<=26; i++)
        p[i] = n+1;
    for(int i=n; i>=1; i--)
    {
        int t = str[i]-'a';
        r[i] = p[t];
        p[t] = i;
    }
    int ans = 0;
    //计算每个字符的贡献值
    for(int i=1; i<=n; i++)
        ans += (i-l[i])*(r[i]-i);
    cout << ans;
    return 0;
}

5154. 牛的基因学
关键在于对题目的理解，题目中的距离函数解读完之后起始就是t字符串每个字符对s字符串每个字符匹配相同字符的数量之和，考虑每个字符的贡献可发现s字符串中出现次数最多的字符对距离的贡献最大，所以若要让俩字符串的距离最大化则只需要将t字符串每个字符全设置为s字符串中出现次数最多的字符，由于出现次数最多的字符串可能不止一个，所以答案为出现次数最多的字符种类cnt^n

代码1

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
string s;

signed main()
{
    int n;
    cin >> n >> s;
    int a=0, c=0, g=0, t=0;

    for(int i=0; i<n; i++)
    {
        if(s[i] == 'A') a++;
        else if(s[i] == 'G') g++;
        else if(s[i] == 'C') c++;
        else if(s[i] == 'T') t++;
    }
    int mx = max({a, g, c, t});
    int cnt = 0;
    if(a == mx) cnt++;
    if(g == mx) cnt++;
    if(c == mx) cnt++;
    if(t == mx) cnt++;
    int ans = 1;
    for(int i=1; i<=n; i++)
        ans = ans*cnt%mod;
    cout << ans;
    return 0;
}

代码2

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
string s;
int c[200];

signed main()
{
    int n;
    cin >> n >> s;
    int mx = 0, cnt = 0;

    for(int i=0; i<n; i++)
    {
        int t = ++c[s[i]];
        if(t > mx) mx = t, cnt = 1;
        else if(t == mx) cnt++;
    }

    int ans = 1;
    for(int i=1; i<=n; i++)
        ans = ans*cnt%mod;
    cout << ans;
    return 0;
}