目錄

• @description@
• @solution@
• @accepted code@
• @details@

---

@description@

給定一個長度為 n 的僅包含'B'、'C'、'S'三種字符的字符串，請找到最長的一段連續(xù)子串，使得這一段要么只有一種字符，要么有多種字符，但是沒有任意兩種字符出現(xiàn)次數(shù)相同。

input
第一行包含一個正整數(shù) n(1<=n<=1000000)，表示字符串的長度。
第二行一個長度為 n 的字符串。

output
包含一行一個正整數(shù)，即最長的滿足條件的子串的長度。

sample input
9
CBBSSBCSC
sample output
6

@solution@

在這篇博客內(nèi)有一個很神仙的結(jié)論：

最優(yōu)解 [l, r] 一定滿足 \(l \in [1, 3]\) 或 \(r \in [n-2, n]\)。

至于證明，那位博主略去了。。。

我來嘗試證明一下吧：

性質(zhì) <1>： 如果 [l, r] 滿足沒有任意兩種字符出現(xiàn)次數(shù)相同，則一定能找到合法區(qū)間 [l', r'] 滿足 \(l' \in [l-3,l], r' \in [r,r+3]\)，且 r - l + 1< r' - l' + 1。
使用反證法。不失一般性，假設(shè) [l, r] 內(nèi)三種字符的出現(xiàn)次數(shù)分別為 (a, b, c) 且滿足 a < b < c。

分類討論 l-1 是什么字符：
（1） [l-1, r] 對應(yīng) (a, b, c+1)，始終滿足 a < b < c + 1。
（2） [l-1, r] 對應(yīng) (a, b+1, c)，若不滿足 a < b + 1 < c，則有 b + 1 = c 成立。
（2） [l-1, r] 對應(yīng) (a+1, b, c)，若不滿足 a + 1 < b < c，則有 a + 1 = b 成立。

類似地對 r+1 進(jìn)行分類，可以得到一個初步的結(jié)論：如果性質(zhì)不成立，那么 (a, b, c) 至少要滿足 a + 2 = b + 1 = c。

剩下的證明因為我很懶再加上我也不是專業(yè)的采用 dfs 枚舉所有可能。用于驗證的程序如下：

#include<cstdio> int a[6], s[3]; void dfs(int x) {if( x == 6 ) {for(int i=0;i<=3;i++)for(int j=2;j<=5;j++) {if( i <= j ) {s[0] = -1, s[1] = 0, s[2] = 1;for(int k=i;k<=j;k++)s[a[k]]++;if( s[0] != s[1] && s[0] != s[2] && s[1] != s[2] )return ;}}puts("error");return ;}a[x] = 0; dfs(x + 1);a[x] = 1; dfs(x + 1);a[x] = 2; dfs(x + 1); } int main() {dfs(0); }

性質(zhì) <2>：如果 [l, r] 滿足只有一種字符且 r - l + 1 > 1，則一定能找到合法區(qū)間 [l', r'] 滿足 l - 1 = l' 或 r + 1 = r'。
對于區(qū)間 [l-1, r]，它要么是形如 (0, 0, r - l + 2)，要么是形如 (0, 1, r - l + 1)。
對于區(qū)間 [l, r+1] 同理。

有了這兩個性質(zhì)就可以證明我們的結(jié)論了。
假如最優(yōu)解 [l, r] 不滿足結(jié)論，則有 l > 3, r < n - 2。由性質(zhì) <1> 或性質(zhì) <2> 可知可以通過移動它的左右端點使得區(qū)間長度變大。故它一定不是最優(yōu)解。
有一些不嚴(yán)謹(jǐn)?shù)牡胤?#xff0c;就是如果 r - l + 1 = 1 的時候。這種情況特殊討論一下也成立。

時間復(fù)雜度 O(n)。

@accepted code@

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 1000000 + 5; inline int fun(char ch) {if( ch == 'B' ) return 0;if( ch == 'C' ) return 1;if( ch == 'S' ) return 2; } int n, sum[3][MAXN]; int f(int x, int l, int r) {return sum[x][r] - sum[x][l - 1]; } bool check(int l, int r) {if( f(0, l, r) != f(1, l, r) && f(0, l, r) != f(2, l, r) && f(1, l, r) != f(2, l, r) ) return true;if( (!f(0, l, r) && !f(1, l, r)) || (!f(0, l, r) && !f(2, l, r)) || (!f(1, l, r) && !f(2, l, r)) ) return true;return false; } char s[MAXN]; int main() {int n, ans = 1;scanf("%d%s", &n, s + 1);for(int i=1;i<=n;i++) {sum[0][i] = sum[0][i-1];sum[1][i] = sum[1][i-1];sum[2][i] = sum[2][i-1];sum[fun(s[i])][i]++;}for(int i=1;i<=n;i++) {if( 1 <= i && check(1, i) ) ans = max(ans, i - 0);if( 2 <= i && check(2, i) ) ans = max(ans, i - 1);if( 3 <= i && check(3, i) ) ans = max(ans, i - 2);if( i <= n - 0 && check(i, n - 0) ) ans = max(ans, n - i + 1);if( i <= n - 1 && check(i, n - 1) ) ans = max(ans, n - i);if( i <= n - 2 && check(i, n - 2) ) ans = max(ans, n - i - 1);}printf("%d\n", ans); }

@details@

當(dāng)然這種神仙結(jié)論我肯定是想不到的。

所以，我選用的是另外一種方法：
只含一種字符的區(qū)間顯然可以隨便怎么搞。

定義 sum[i] 表示字符 i 的前綴和。如果區(qū)間 [l + 1, r] 合法，則一定有：
sum[0][r] - sum[0][l] ≠ sum[1][r] - sum[1][l]
sum[0][r] - sum[0][l] ≠ sum[2][r] - sum[2][l]
sum[1][r] - sum[1][l] ≠ sum[2][r] - sum[2][l]

變一下形：
sum[0][r] - sum[1][r] ≠ sum[0][l] - sum[1][l]
sum[0][r] - sum[2][r] ≠ sum[0][l] - sum[2][l]
sum[1][r] - sum[2][r] ≠ sum[1][l] - sum[2][l]

枚舉 r，相當(dāng)于找到一個最小的 l 滿足上述條件。
先判斷它是不是三個前綴和都不一樣，如果是就有 l = 0。
接下來，對于某一個 l，不滿足上述條件的 r 其實很少。我們大力分類討論即可。
時間復(fù)雜度還是 O(n) 的，但是代碼復(fù)雜度……

轉(zhuǎn)載于:https://www.cnblogs.com/Tiw-Air-OAO/p/10364777.html

總結(jié)

以上是生活随笔為你收集整理的@bzoj - 4384@ [POI2015] Trzy wieże的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。