题解：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

。

增加字符

分为三种情况

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

AC代码

CPP

#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;
}

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

文章操作

思路

预处理

增加字符

AC代码

相关推荐

评论

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