codeforces Round #258(div2) D問題解決レポート_html/css_WEB-ITnose

D. 適切な部分文字列のカウント

テストあたりの時間制限

2 秒

テストあたりのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

を呼び出します連続するすべての等しい文字を結合した後、結果の文字列が回文になる場合、文字列は良好です。たとえば、「aabba」は、結合ステップの後は「aba」になるため、適切です。

文字列を指定すると、次の 2 つの値を見つける必要があります:

1. 偶数の長さの適切な部分文字列の数;
2. 数奇数の長さの適切な部分文字列。

入力

入力の最初の行には、長さ n (1?≤?n?≤?105) の単一の文字列が含まれます。文字列の各文字は、'a' または 'b' になります。

出力

スペースで区切られた 2 つの整数: 偶数長の適切な部分文字列の数と、奇数長の適切な部分文字列の数を出力します。

サンプルテスト

入力

bb

出力

1 2

入力

baab

出力

2 4

入力

babb

出力

2 5

入力

babaa

出力

2 7

注意

例 1 には、適切な部分文字列が 3 つあります ("b"、"b"、および "bb")。そのうちの 1 つは偶数の長さで、そのうちの 2 つは奇数の長さです。

例 2 には、適切な部分文字列が 6 つあります (つまり、「b」、「a」、「a」、「b」、「aa」、「baab」) ）。そのうち 2 つは偶数の長さで、そのうち 4 つは奇数の長さです。

例 3 には、7 つの適切な部分文字列があります (つまり、「b」、「a」、「b」、「b」、「bb」、「bab」) 、「バブ」）。そのうち 2 つは偶数の長さで、そのうち 5 つは奇数の長さです。

定義

文字列 s?=?s1s2 の部分文字列 s[l,?r] (1?≤?l?≤?r?≤?n) ... sn は文字列 slsl?+?1... sr.

文字列 s?=?s1s2... sn は、文字列 snsn?-?1... s1.

と等しい場合、回文になります。

目標大意:

は a と b だけを含む文字列を出力します。

まず最初に、2 つの既知の条件に注意してください:

1. 文字列は組み合わせることができます。例: abba abbb 合并之後就是abab

2. 只有两个字符a，b

我们可発行现，合并次的字列一定是aba または者abab 型的，那么合并次的字列如果是回文的话，第一文字符肯定与最後の 1 つの文字列は同じですが、反動はありません。

私たちはさらに、2 つの異なる位置、文字列が同じ、その間に構成される文字列が適切な部分文字列であるという結論を得ることができます。時間の重複が求められますが、要求されるのは長さが奇数と偶数の数であること、つまり、最初に、すべての数を求める方法があります。与位置は偶数の文字符構成偶数長さの良好な部分文字列，

与位置は奇数の文字符構成奇数長度の良好な部分文字列，

位置は偶数の文字，与位置は偶数の文字構成奇数長さの良い部分文字列、

与位置は奇数的字符构成偶数数長度の良好な部分文字列，

代码：

#include <string>#include <iostream>#define LL long longusing namespace std;string st;LL ansOdd, ansEven;LL Odd[2], Even[2];void init() {	cin >> st;}void solve() {	for (int i = 0; i < st.size(); i++) {		ansOdd++;		int j = st[i]-'a';		if ((i+1)&1) {			ansOdd += Odd[j];			ansEven += Even[j];			Odd[j]++;		}		else {			ansEven += Odd[j];			ansOdd += Even[j];			Even[j]++;		}	}	cout << ansEven << ' ' << ansOdd << endl;}int main() {	init();	solve();}