創作內容

0 GP

ZeroJudge - c412: 四、多麼OwO(OwO) 解題心得

作者:Not In My Back Yard│2018-11-08 23:08:37│贊助:0│人氣:10
題目連結:


題目大意:
給定一正整數 T ,代表接下來有 T 行輸入。每行輸入有一個字串 S ,求在 S 中為「OwO」的子序列之數目(取 10 ^ 9 + 7 之餘數)。 T * |S| ≦ 10 ^ 8 。

註:本題記憶體限制為 15 MB。



範例輸入:
2
OwOwOb
aObwcOd



範例輸出:
4
1



解題思維:
因為考量到記憶體限制的緣故,因此本人使用 C++ 內建的 getchar() 函式,一個字元一個字元去讀,直到換行。

因為是要找子序列為「OwO」的數目,所以其他字元可以無視。

觀察例子,S = OwwOOwOwOww:

第一個字元 O ,接不了任何東西,跳過。

第二個字元 w ,可以接在前面的 O 後面,有潛在的可能性。現有的可能組合為 1 。

第三個字元 w ,與上同理。可能的組合為 2 。

第四個字元 O ,前面有 W ,而 W 也有前面的 O 可以接,因此現有方法數為 2 (有 2 個 W ,各自前面有 1 個 O 可接,所以總共 2 種的可能性)。

第五個字元 O ,與上同理。現有方法數為 4 。

第六個字元 w ,同理,前面總共有 3 個 O 。可能的組合為 5 。

第七個字元 O ,同理。現有方法數為 9 。

第八個字元 w ,同理。可能組合為 9 。

第九個字元 O ,同理。方法數為 18 。

第十個字元 w ,同理。可能數 14 。

第十一個字元 w ,同理。可能數 19 。

所以這個例子,總共有 18 個子序列為「OwO」。



從以上的例子可以看到,讀到 W 的時候,就把潛在的可能數(一開始為 0 )加上前面有多少個 O 之數目;而讀到 O 時,把方法數(一開始也是 0 )加上剛剛算出的可能數,然後把遇到過的 O 數目 + 1 。(記得每一步驟都要取餘數)

讀到換行,代表 S 字串的內容結束了。可以輸出結果。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4188884
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|字串處理|動態規劃(DP)

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

訂閱私訊

作品資料夾

leo25127米吶
我的小屋正連載輕小說『公爵家的獨生子』,歡迎各位前來我的小屋看看,喜歡在幫我GP或訂閱。看更多我要大聲說昨天09:05


face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】