题解：P11794 [JOI 2016 Final] 集邮比赛 2 / Collecting Stamps 2

· · 题解

题面传送门

思路

预处理

首先先算出最初的个数，固定枚举 JOI 中间的 O，然后在 O 的前面统计枚举 J，后面统计枚举 I，然后根据乘法原理相乘然后再根据假发原理将每个 O 的情况个数再相加即可。

也就是：totj_i = totj_{i−1}+[s_i=J] 和 toti_i=toti_{i+1}+[s_i=I]，然后再计算 ans=∑[s_i=O]×toti_i×totj_i。

增加字符

分为三种情况

  1. 插入 O：O 必须在 J 和 I 两个字符之间才有贡献，做法和预处理类似，都是用乘法原理，找到个数最多的那个， 也就是 cnt = max(cnt, totj[i] * toti[i+1])。
  2. 插入 J：只有在它之后的字符可以与它组合，于是将它放到最前，再计算枚举每个 O 能搭配的情况个数，相加，即 cnt1 += toti[i]。
  3. 插入 I：同插入 J，只需插到最后面。

    AC代码

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

long long toti[100005]/*I的情况*/, totj[100005]/*J的情况*/;

int main()
{
    long long n, cnt = 0, cnt1 = 0, cnt2 = 0, ans = 0;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> n >> s;
    for(int i = 1; i <= n; i++)
    {
        totj[i] = totj[i - 1];
        if(s[i - 1] == 'J')
            totj[i]++;
    }
    for(int i = n; i >= 1; i--)
    {
        toti[i] = toti[i + 1];
        if(s[i - 1] == 'I')
            toti[i]++; 
    }
    for(int i = 1; i <= n; i++)
    {
        if(s[i - 1] == 'O')
        {
            ans += totj[i] * toti[i];
        }
    }
    //插入O 
    for(int i = 1; i < n; i++)
    {
        cnt = max(cnt, totj[i] * toti[i+1]);
    }
    //插入J 
    for(int i = 1; i <= n; i++)
    {
        if(s[i - 1] == 'O')
        {
            cnt1 += toti[i];
        }
    }
    //插入I 
    for(int i = 1; i <= n; i++)
    {
        if(s[i - 1] == 'O')
        {
            cnt2 += totj[i];
        }
    }
    cnt = max({cnt, cnt1, cnt2}); //比较求最大的 
    ans += cnt;
    cout << ans << endl;
    return 0;
}