小易的字典
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/94563972
题目描述：
小易在学校中学习了关于字符串的理论, 于是他基于此完成了一个字典的项目。
小易的这个字典很奇特, 字典内的每个单词都包含n个'a'和m个'z', 并且所有单词按照字典序排列。
小易现在希望你能帮他找出第k个单词是什么。
输入描述：
输入包括一行三个整数n, m, k(1 <= n, m <= 100, 1 <= k <= 109), 以空格分割。
输出描述：
输出第k个字典中的字符串，如果无解，输出-1。
输入样例：
2 2 6输出样例：
zzaa样例说明：
测试用例中字典里的字符串依次为aazz azaz azza zaaz zaza zzaa。
解题思路：
网易校招题。我一开始的想法就是暴力破解，先调用next_permutation来求全排列，然后将所有的字符串都存入unordered_map中，最后输出unordered_map中的第k个字符串即可，若无解则输出-1。然而我提交代码后出现了MLE 只通过30%的测试用例就出现内存超限啦。?
那没得一点办法 我只能把unordered_map去掉了，不再存储字符串，换成一个if语句，如果当前全排列的字符串是第k个就将它进行输出，如果无解就输出-1。然而这次提交代码后TLE了 通过50%的测试用例后就出现了运行超时。"100 100 1000000000"这个测试用例谁顶得住啊？?
我哭了?今天运筹学考炸了，本来是想刷下题找成就感，结果这道题又是MLE又是TLE的。很显然网易不准C++玩家用next_permutation来暴力破解这道题。根据排列组合的知识可以知道，n个'a'和m个'z'只能组成
个字符串，我在这里暂且把
表示为C(n,n+m)吧。先假设第一个字符为'a'，那么剩下n-1个'a'和m个'z'组成的子序列能构成字典中的前C(n-1+m,n-1)个字符串。然后比较k和C(n-1+m,n-1)，这里有俩种情况：①若k小于等于C(n-1+m,n-1)，就说明第k个字符串是字典里前C(n-1+m,n-1)个中的一个（显然该字符串的第一个字符必为'a'），所以该问题又可以缩减为在子序列(n-1个'a'和m个'z')找到第k个字符串。②若k大于C(n-1+m,n-1)，就说明结果字符串ans是以'z'开头的字符串中的第k-C(n-1+m,n-1)个字符串，所以该问题又可以缩减为在子序列(n个'a'和m-1个'z')找到第k-count(n+m-1,m-1)个字符串。while(n&&m)循环结束后，剩余子序列中只存在"aaa...a"或"zzz...z"的情况，若k不为1则说明无解输出-1，否则在字符串ans后补'a'或'z'，最后输出ans即可。提交代码终于AC了！含泪AC?。
AC代码：MLE代码：
#include <bits/stdc++.h>
using namespace std;
string init(int n,int m) //初始化,得到字典中的第一个单词
{
string ans = "";
while(n--)
{
ans += 'a';
}
while(m--)
{
ans += 'z';
}
return ans;
}
int main()
{
int n,m,k; //字典中每个单词包含n个'a',m个'z',求第k个单词
while(cin >> n >> m >> k)
{
string str = init(n,m);
unordered_map<int,string> dictionary; //小易的字典,key为单词,value为单词的次序
int cnt = 0; //计数器,记录当前字典的次序
do{
dictionary[++cnt] = str; //存入字典中
}while(next_permutation(str.begin(),str.end())); //全排列
cout << (k <= dictionary.size() ? dictionary[k] : "-1") << endl; //输出字典中的第k个字符串,如果无解则输出-1
}
return 0;
}AC代码：TLE代码：
#include <bits/stdc++.h>
using namespace std;
string init(int n,int m) //初始化,得到字典中的第一个单词
{
string ans = "";
while(n--)
{
ans += 'a';
}
while(m--)
{
ans += 'z';
}
return ans;
}
int main()
{
int n,m,k; //字典中每个单词包含n个'a',m个'z',求第k个单词
while(cin >> n >> m >> k)
{
bool flag = false; //判断有无解,默认为false无解
string str = init(n,m);
int cnt = 0; //计数器,用来记录当前字典中的单词个数
do{
if(++cnt == k)
{
flag = true; //有解
cout << str << endl; //输出字典中第k个字符串
break;
}
}while(next_permutation(str.begin(), str.end())); //全排列
if(!flag) //若无解,则输出-1
{
cout << -1 << endl;
}
}
return 0;
}AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m,k; //字典中每个单词包含n个'a',m个'z',求第k个单词
while(cin >> n >> m >> k)
{
string ans = "";
while(n && m)
{
long long cnt = 1; //一定要long long
for(int i = 1; i < n; i++) //求组合数
{
cnt *= (n+m-i);
cnt /= i;
if(cnt > k) break; //防止越界,cnt>k就跳出for循环
}
if(k <= cnt)
{
ans += "a";
n--; //问题缩减为n-1个a和m个z中找第k个字符串
}
else
{
ans += "z";
m--;
k -= cnt; //问题缩减为n-1个a和m个z中找第k-cnt个字符串
}
}
if(k != 1) //若k不为1说明无解
{
cout << -1 << endl;
}
else
{
//while(n&&m)循环结束后,剩余子序列中只存在"aaa...a"或"zzz...z"的情况
while(n--)
{
ans += "a";
}
while(m--)
{
ans += "z";
}
cout << ans << endl;
}
}
return 0;
}腾讯云开发者
