題目鏈接：點擊查看

題目大意：給出一個字符串s，該字符串是由一臺壞掉的打字機生成的，壞掉的打字機會將m打成nn，將w打成uu，問現(xiàn)在給出字符串s，其原本的字符串有多少種可能性

題目分析：因為m會變成nn，w會變成uu，首先字符串s中肯定不能出現(xiàn)字符m和w，特判一下，這是輸出0的情況，特判完之后我們只需要找相鄰的uu或nn就行了，一開始我的想法是nn不好處理的情況是nnn，所以我們可以優(yōu)先特判一下nnn，如果不是nnn的話那么我們讓相鄰兩個n結(jié)合就好了，但是我忘記了一個很關(guān)鍵的問題，比如一個長度為4的uuuu，我們給他編號分別為1 2 3 4，如果只是相鄰兩兩考慮的話，那么只是1與2的結(jié)合，以及3與4的結(jié)合，其實實際上2與3也是可以結(jié)合的，所以漏情況了

而這個題的正解也是十分巧妙的，我們可以先試著寫寫看前幾項：

u：1

u

uu：2

uu,w

uuu：3

uuu,um,mu

uuuu：5

uuuu,muu,umu,uum,mm

uuuuu：8

uuuuu,muuu,umuu,uumu,uuum,umm,mum,mmu

到此為止吧，我們可以很清楚的觀察到，隨著相鄰的u越來越多，其增長趨勢就是個斐波那契數(shù)列，這樣我們就可以直接預(yù)處理一下斐波那契后模擬就好了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;const int mod=1e9+7;LL f[N];void init() {f[0]=f[1]=1;for(int i=2;i<N;i++)f[i]=(f[i-1]+f[i-2])%mod; }bool check(string& s) {for(int i=0;i<s.size();i++)if(s[i]=='m'||s[i]=='w')return true;return false; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();string s;cin>>s;if(check(s))return 0*printf("0\n");LL ans=1;for(int i=0;i<s.size();i++){if(s[i]=='u'){int sum=1;while(s[i+1]=='u'){i++,sum++;}ans=ans*f[sum]%mod;}else if(s[i]=='n'){int sum=1;while(s[i+1]=='n'){i++,sum++;}ans=ans*f[sum]%mod;}}printf("%lld\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1245C Constanze's Machine(思维+找规律)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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