題目描述

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

?

輸入輸出格式

輸入格式

? ? ? ? 一組僅由“F”、“B”、“I”、“0”組成的序列（“F”、“B”、“I”、“0”這四個(gè)字母中的某一個(gè)或某幾個(gè)不一定會(huì)出現(xiàn)，且保證序列長(zhǎng)度≤2000）

? ? ? ? 規(guī)定這個(gè)序列所要傳達(dá)的信息就是這組序列有多少個(gè)“FBI”（子序列）

?

輸出格式

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

?

輸入輸出樣例

輸入樣例

FBIIBFOI

?

輸出樣例

4

?

題解

? ? ? ? 樸素做法很明顯，枚舉F，B，I的位置，暴力統(tǒng)計(jì)，時(shí)間復(fù)雜度O(n3)，數(shù)據(jù)水的話還能卡過(guò)去。

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

#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); } 參考程序

?

轉(zhuǎn)載于:https://www.cnblogs.com/kcn999/p/10353481.html

總結(jié)

以上是生活随笔為你收集整理的【题解】FBI序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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