简答题
偏难
#13135
字符数对 给定一个由字符 o 和 x 组成的长度为 N 的字符串 S。请计算满足以下所有条件的整数对(l,r)的数量: (1)1≤l≤r≤N; (2)在字符串…
字符数对
给定一个由字符 o 和 x 组成的长度为 N 的字符串 S。请计算满足以下所有条件的整数对(l,r)的数量:
(1)1≤l≤r≤N;
(2)在字符串 S 的子串 S[l...r](从第 l 个字符到第 r 个字符)中,同时包含 o 和 x 两种字符。
时间限制:1000ms,内存限制:256MB
输入格式
第一行,一个整数 N;
第二行,一个字符串 S。
输出格式
输出满足条件的整数对的数量。
输入样例#1
4 oxxo
输出样例#1
5
输入样例#2
7 xoxooxx
输出样例#2
19
数据范围:
1≤N≤106;S 仅由字符 o 和 x 组成。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
char s[1000005];
int main() {
int n, cnt = 0;
cin >> n >> s;
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
//检查s[i...j]是否包括o和x
bool of=false, xf=false;
for(int k=i; k<=j; k++) {
if(s[k] == 'o')
of = true;
if(s[k] == 'x')
xf = true;
if(of && xf)
break;
}
if(of && xf)
cnt++;
}
}
printf("%d", cnt);
return 0;
}</pre>
这道题暂未补解析。