信息學(xué)奧賽一本通T1462-Antisymmetry

提交: 22 解決: 8

題目描述

對(duì)于一個(gè)01字符串，如果將這個(gè)字符串0和1取反后，再將整個(gè)串反過(guò)來(lái)和原串一樣，就稱作“反對(duì)稱”字符串。比如00001111和010101就是反對(duì)稱的，1001就不是。

現(xiàn)在給出一個(gè)長(zhǎng)度為N的01字符串，求它有多少個(gè)子串是反對(duì)稱的。

第一行一個(gè)正整數(shù)N (N ≤ 500,000)。第二行一個(gè)長(zhǎng)度為N的01字符串。

一個(gè)正整數(shù)，表示反對(duì)稱子串的個(gè)數(shù)。

8
11001011

7個(gè)反對(duì)稱子串分別是：01(出現(xiàn)兩次), 10(出現(xiàn)兩次), 0101, 1100和001011

標(biāo)簽

上一題下一題