錯題集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