专栏文章

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

EELECTRODE_kaf
P11794题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipuwlcf
此快照首次捕获于
2025/12/03 18:20
3 个月前
此快照最后确认于
2025/12/03 18:20
3 个月前
查看原文
先考虑修改前的答案。统计前缀中 J 的个数和后缀中 I 的个数，每一个 O 前后相乘加起来即可。
若添加 J，则贪心地加在开头，对于每一个 O，贡献即为后缀中 I 的数量。添加 I 同理。
若添加 O，则枚举每个位置插入，贡献计算方法不变。
复杂度线性。
CPP
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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...