47 lines
1.6 KiB
C++
47 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
int cnt;
|
||
unordered_map<string, int> _map;
|
||
string str;
|
||
/**
|
||
* 功能：预处理填充所有的1-6位字符串+数字映射表
|
||
* @param len 要填充几位的字符串:1,2,3,4,5,6
|
||
* @param pos 在指定长度的字符串前提下，当前正在填充第几位
|
||
*/
|
||
void dfs(int len, int pos) {
|
||
//递归出口,走冒了，就停止
|
||
if (pos > len) {
|
||
_map[str] = ++cnt;
|
||
return;
|
||
}
|
||
//默认第1位是从a开始的
|
||
char start = 'a';
|
||
//如果是2，3，4，5，6位，那么开始的字符应该是当前填充字符串的前面那位+1
|
||
//为什么是k-2呢？这是因为k=1时，start='a';k=2时，需要找now[0]的值然后+1
|
||
if (pos > 1)start = str[pos - 2] + 1;
|
||
//从比最后一位大的字符开始，一直到z，都是可以走的路径，分别派出侦查兵进行探索
|
||
for (char i = start; i <= 'z'; i++) {
|
||
//填充本位置
|
||
str[pos - 1] = i;//字符串的下标是从0开始，所以，第k个字符，下标索引是k-1
|
||
//继续讨论下一个位置
|
||
dfs(len, pos + 1);
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//预处理：不同长度的单词分别处理，len从1到6(最长6位)
|
||
for (int len = 1; len <= 6; len++) {
|
||
//对字符串进行清理和长度设定,这是因为后面需要向指定的位置写入字符，如果不说好长度的话就没法写入
|
||
str.clear();
|
||
str.resize(len);
|
||
//开始深搜
|
||
dfs(len, 1);
|
||
}
|
||
//输入
|
||
string ask;
|
||
cin >> ask;
|
||
//查询输出
|
||
cout << _map[ask] << endl;
|
||
return 0;
|
||
} |