首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#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 &lt;bits/stdc++.h&gt; using namespace std; char s[1000005]; int main() {     int n, cnt = 0;     cin &gt;&gt; n &gt;&gt; s;     for(int i=0; i&lt;n; i++) {         for(int j=i+1; j&lt;n; j++) {             //检查s[i...j]是否包括o和x             bool of=false, xf=false;             for(int k=i; k&lt;=j; k++) {                 if(s[k] == 'o')                     of = true;                 if(s[k] == 'x')                     xf = true;                 if(of &amp;&amp; xf)                     break;             }             if(of &amp;&amp; xf)                 cnt++;         }     }     printf("%d", cnt);     return 0; }</pre>
这道题暂未补解析。