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

ELECTRODE_kaf · 2025-03-21 19:44:26 · 题解

先考虑修改前的答案。统计前缀中 J 的个数和后缀中 I 的个数，每一个 O 前后相乘加起来即可。

若添加 J，则贪心地加在开头，对于每一个 O，贡献即为后缀中 I 的数量。添加 I 同理。

若添加 O，则枚举每个位置插入，贡献计算方法不变。

复杂度线性。

const ll N = 1e5 + 10;
ll n, ps[N], ss[N], sum, ans;
string s;

void cal_j() {
    ll add = 0;

    rep(i, 0, n - 1) {
        if (s[i] == 'O')
            add += ss[i];
    }

    update(ans, sum + add, max);
}

void cal_i() {
    ll add = 0;

    rep(i, 0, n - 1) {
        if (s[i] == 'O')
            add += ps[i];
    }

    update(ans, sum + add, max);
}

void cal_o() {
    ll add = 0;

    rep(i, 0, n - 2) update(add, ps[i]*ss[i], max);

    update(ans, sum + add, max);
}

int main() {
    cin >> n >> s;
    ps[0] = s[0] == 'J';

    rep(i, 1, n - 1) ps[i] = ps[i - 1] + (s[i] == 'J');

    ss[n - 1] = s[n - 1] == 'I';

    rep_(i, n - 2, 0) ss[i] = ss[i + 1] + (s[i] == 'I');

    rep(i, 1, n - 2) {
        if (s[i] == 'O')
            sum += ps[i] * ss[i];
    }

//  cout << "sum=" << sum << '\n';
//  pause;
    cal_j();
    cal_o();
    cal_i();
    cout << ans;
}