【題解】FBI序列

題目描述

? ? ? ? 兩伙外星人策劃在未來的XXXX年侵略地球，侵略前自然要交換信息咯，現在，作為全球保衛隊隊長，你截獲了外星人用來交換信息的一段僅由“F”，“B”，“I”，“O”組成的序列。為了保衛地球和平，為了使家園不受破壞，你要機智地破解密碼，勇敢地迎擊外星人！記住，你不是一個人在戰斗！你不是一個人！你的背后是千千萬萬的地球人！

?

輸入輸出格式

輸入格式

? ? ? ? 一組僅由“F”、“B”、“I”、“0”組成的序列（“F”、“B”、“I”、“0”這四個字母中的某一個或某幾個不一定會出現，且保證序列長度≤2000）

? ? ? ? 規定這個序列所要傳達的信息就是這組序列有多少個“FBI”（子序列）

?

輸出格式

? ? ? ? 一行，一個數,表示這組序列有多少個“FBI”的子序列（保證答案≤2^31，且FBI必須是正序，即IBF或者BIF或者FIB或者BFI或者IFB都不能算是一個FBI）

?

輸入輸出樣例

輸入樣例

FBIIBFOI

?

輸出樣例

4

?

題解

? ? ? ? 樸素做法很明顯，枚舉F，B，I的位置，暴力統計，時間復雜度O(n3)，數據水的話還能卡過去。

? ? ? ? 顯然我們不能用這種做法。可以考慮枚舉B的位置i（假設從1開始計數），然后統計字符串的第一位到第i-1位里F的數量和第i+1位到第n位I的數量，根據乘法原理統計結果，而事實上統計F，I的數量也可以用兩個變量維護，枚舉i的過程中判斷要不要更改這兩個變量，這樣即可做到O(n)的時間復雜度。

#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;char s[2005];
int len;
int cnt_F, cnt_I;
int ans;int main()
{scanf("%s", s);len = strlen(s);for(register int i = 0; i < len; ++i){if(s[i] == 'I') ++cnt_I;}for(register int i = 0; i < len; ++i){if(s[i] == 'B') ans += cnt_F * cnt_I;else if(s[i] == 'F') ++cnt_F;else if(s[i] == 'I') --cnt_I;}printf("%d", ans);
}

?