gym 102875 H. Happy Morse Code

題意：

一個長度為n的字符串，現在給你m個小字符串，問小字符串拼成大字符串有多少種方法？
答案mod128

題解：

其實也不難，但是本人對于dp及其不敏感，我看出來是dp，也明白用O（MN）的方法來做，但就是寫不出遞推式，唉，還要多練
設dp[i]表示以i結尾的字符串有多少種表示方法
（dp[ i ]表示模式串前i個字符組成的子串 可以由已提供的字符串拼接而成的方法數）
轉移方程就是：dp[i]+=dp[i-len[j]]，（條件s.substr(i-zlen[j],zlen[j]) == z[ j ]）
i枚舉的是模式串的每一位，j枚舉的是每一個小字符串
含義：對于長度為i的字符串可以由長度為i-len[j]的字符串拼接第j個小字符串得到，當且僅當s.substr(i-zlen[j],zlen[j])等于z[ j ]
但是題目說了要mod128，且根據最終的答案輸出不同東西
那么dp[]可以就有多個含義，
dp[i] = 0的含義：
1.可以拼成長度為i的字符串，方案數mod128后等于0
2.不能拼成長度為i的字符串，方案數為0
dp[i] =1的含義：
1.有多種構成方式，只是mod后為1，題目要求輸出puppymousecat 1
2.只有一種構成方式，題目要求輸出happymorsecode
我們可以引入一個數組flag來記錄每一位的值到底是mod后，還是原本的值
比如flag[i] = 0,dp[i] = 0,說明不能拼成長度為i的字符串，如果flag[i] = 1，就是第一種情況
詳細見代碼：

代碼：

#include <iostream> #include <fstream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int maxn=100010; ll dp[maxn]; string s; string z[100]; ll zlen[100]={0}; ll flag[100010]={0}; int t,m,n; int main() {scanf("%d",&t);while (t--) {scanf("%d%d",&n,&m);memset(dp,0,sizeof(dp));memset(zlen,0,sizeof(zlen));memset(flag,0,sizeof(flag));string x;for(int i=1;i<=m;i++){cin>>x>>z[i];zlen[i]=z[i].length();}cin>>s;dp[0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i-zlen[j]>=0){string ww=s.substr(i-zlen[j],zlen[j]);if(ww==z[j])//如果一樣 {dp[i]+=dp[i-zlen[j]];//增加答案 if(flag[i-zlen[j]]==1)//根據前一個狀態是否為mod結果，來判斷后一個狀態是不是 flag[i]=1;if(dp[i]>=128){dp[i]%=128;flag[i]=1;}}}}}if(flag[n]==1){printf("puppymousecat %d\n",dp[n]);}else{if(dp[n]==0)printf("nonono\n");else if(dp[n]==1)printf("happymorsecode\n");else printf("puppymousecat %d\n",dp[n]);}}return 0; }

總結

以上是生活随笔為你收集整理的gym 102875 H. Happy Morse Code的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。