A22928. 字符数对
填空题
较难
知识点
题目描述
字符数对
题目描述
给定一个由字符 o 和 x 组成的长度为 N 的字符串 S。
请计算满足以下所有条件的整数对 (l, r) 的数量：
1 ≤ l ≤ r ≤ N；
在字符串 S 的子串 S[l..r]（从第 l 个字符到第 r 个字符）中，同时包含 o 和 x 两种字符。
输入格式
第一行，一个整数 N；
第二行，一个字符串 S。
输出格式
输出满足条件的整数对的数量。
输入样例#1
4
oxxo输出样例#1
5输入样例#2
7
xoxooxx输出样例#2
19参考答案
#include <iostream>
int main() {
int64_t N;
std::string S;
std::cin >> N >> S;
S.push_back('!');
int64_t result = N * N;
char last_c = S[0];
int64_t last_id = 0;
for (int64_t i = 1; i <= N; i++) {
if (S[i] == last_c) continue;
result -= (i - last_id) * (i - last_id);
last_id = i;
last_c = S[i];
}
std::cout << result / 2 << std::endl;
}
上一题
下一题