广州易网网站建设,移动互联网开发技术题库,asp.net+h5网站开发,规划设计公司排名gym 102875 H. Happy Morse Code
题意#xff1a;
一个长度为n的字符串#xff0c;现在给你m个小字符串#xff0c;问小字符串拼成大字符串有多少种方法#xff1f; 答案mod128
题解#xff1a;
其实也不难#xff0c;但是本人对于dp及其不敏感#xff0c;我看出来是…gym 102875 H. Happy Morse Code
题意
一个长度为n的字符串现在给你m个小字符串问小字符串拼成大字符串有多少种方法 答案mod128
题解
其实也不难但是本人对于dp及其不敏感我看出来是dp也明白用OMN的方法来做但就是写不出递推式唉还要多练 设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 maxn100010;
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 i1;im;i){cinxz[i];zlen[i]z[i].length();}cins;dp[0]1;for(int i1;in;i){for(int j1;jm;j){if(i-zlen[j]0){string wws.substr(i-zlen[j],zlen[j]);if(wwz[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;
}
