错题集2——秘密编码

文章目录

• 题目信息
• 解题思路
• • 0 ~ 10分思路（搜索枚举）
  • 100分思路（动态规划）
• 代码实现
• 总结

题目信息

• 题目描述

Primo和Saoirsi需要给彼此发一些个秘密信息，他们正在热火朝天地讨论解密这些个编码的方法。

Primo: 让我们整简单点。我们将分配字母’A’给数字1，'B’给数字2，所以以此类推，'Z’给数字26。

Saoirse:你好笨啊！Primo。假设我给你发了个"BEAN"的单词，他的编码是25114，你可以用各种不同的方法对它解码！

Primo:是啊，你可以整啊。不过你能得到啥单词呢？除了"BEAN"你还可以得到“BEAAD“，YAAD“，“YAN”,“YKD"以及"BEKD”。我认为你有能力算出正确的编码。所以说到底，你为什么要给我发"BEAN"这个单词？

Saoirse:OK，也许这是个糟糕的例子。但是哦我的上帝啊，我打个赌，如果你搞一个长度为5000的字符串编码，将会有成千上万不同的解码方式，你觉得你能在这么多不同的解码方式中找到正确的解码方式吗？

Primo:所以有多少种不同的解码方式呢？

Saoirse:亿万种…

因为一些个原因，Primo始终不相信Saoirse的争论所以她需要一个程序来算出对于Saoirse给出的编码，有多少不同的解码方式？

• 输入

本题将有多组测试数据。每组数据会包含一行最多5000个数字，表示一种合法的加密。（比如就不会有合法的加密是以0开头）。数字之间不会有空格。如果有一行数据为一个数字’0’，那么它代表输入结束。

• 输出

对于每一组数据，输出可行的解码方案数。所有答案将在64位有符号整数的范围内。

• 输入样例1

25114

1111111111

3333333333

3

• 输出样例1

6

89

1

解题思路

• 0 ~ 10分思路（搜索枚举）

枚举所有字符串字串，依次判断。
           

优点

便于理解、实现。
           

缺点

时、空复杂度较高。
           

• 100分思路（动态规划）

状态设定

f[i] 表示这个数（因为数据太大，所以要用string或者char*存储）前 i 位有多少种合法的加密。

分析

首先，当f[i]不是'0'的时候，就只能是'1' ~ '9'，合法，此时f[i] 可以从 f[i - 1]推出。
其次，如果 10 ≤ 以f[i - 2]为十位f[i]各位的两位数 ≤ 26, 那么f[i]也可以从 f[i - 2]推出。
这样就可以推出状态转移方程了。
           

状态转移方程

// 括号里的东东就是一些布尔类的条件，条件为真值为1，否则为0。
// check(char, char)表示以第一个字符为十位，第二个字符为个位的两位数是否可以称为合法加密。
f[i] = f[i - 1] * (s[i] != '0') + f[i - 2] * check(s[i - 1], s[i]);
           

易错点

忘记处理’0’。

代码实现

#include <bits/stdc++.h>
using namespace std;
long long f[5000];
inline bool check(char a, char b) {	// check(char, char)表示以第一个字符为十位，第二个字符为个位的两位数是否可以称为合法加密。
	return a == '1' || (a == '2' && b <= '6');	// 10 ~ 19 或 20 ~ 26均合法。
}
int main() {
	string s;
	while (cin >> s && s != "0") {	// 按题意，是 "0" 就结束程序
		memset(f, 0, sizeof f);	// 不要忘记每次重置 f 数组
		f[0] = 1;	// 题目保证第一位不会是'0'
		f[1] = check(s[0], s[1]) + (s[1] != '0');	// 可以是s[0]（一位数）和s[1]（一位数）
													// 也可以是s[0] * 10 + s[1]（两位数）
		for (int i = 2; i < s.size(); ++i) {
			f[i] = f[i - 1] * (s[i] != '0') + f[i - 2] * check(s[i - 1], s[i]);
		}
		cout << f[s.size() - 1] << '\n';
	}
	return 0;
}
           

总结

这次蒟蒻君总结了蒟蒻君的一道经典错题。看完这篇文章后，希望大家不要犯和蒟蒻君一样的错误啦ヾ(￣▽￣)ByeBye