首页 > 试题广场 > 小易的字典
[编程题]小易的字典

小易在学校中学习了关于字符串的理论, 于是他基于此完成了一个字典的项目。

小易的这个字典很奇特, 字典内的每个单词都包含n个'a'和m个'z', 并且所有单词按照字典序排列。

小易现在希望你能帮他找出第k个单词是什么。


输入描述:

输入包括一行三个整数n, m, k(1 <= n, m <= 100, 1 <= k <= 109), 以空格分割。



输出描述:
输出第k个字典中的字符串,如果无解,输出-1。
示例1

输入

2 2 6

输出

zzaa

说明

字典中的字符串依次为aazz azaz azza zaaz zaza zzaa

排列组合,n个'a'和m个'z',只能组成$C_{n+m}^n$,记为count(n+m,n) 个单词。

思路:

  1. 假设第一个字符为a,则剩下n-1个'a'和m个'z'组成的子序列只能构成count(n-1+m,n-1)个单词,且是字典中前count(n-1+m,n-1)个单词。
  2. 比较k和count(n-1+m,n-1),若k小,说明k是前count(n-1+m,n-1)个单词,则第一个字符必为'a'。子问题化为在子序列(n-1个'a'和m个'z')找到第k个单词
  3. 若k大,则说明第一个字符必为'z',单词是以'z'开头的单词中的第k-count(n-1+m,n-1)个。子问题化为在子序列(n个'a'和m-1个'z')找到第k-count(n+m-1,m-1)个单词。

eg:n=2,m=2,k=5

  1. 假设第一个字符为a,则剩下1个a,2个z只能构成3个单词,且是字典中前3个单词(aamm,amam,amma)
  2. k>3,则第一个字符必为z。原问题化为在n=2,m=1,k=2,即在剩下2个a,1个z中找到第2个单词
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    void solve(int n, int m, long long k) {
        vector<char> x;//
        while (n && m) {
            //每次迭代问题规模缩减一个单位
            ////排列组合:假设当前序列首字符为a,剩下n-1个a放在剩下n - 1 +m 个位置共有的可能数
            long long count = 1;
            for (int i = 0; i < n - 1; i++) {//求组合数
                count *= n - 1 + m - i;
                count /= (i + 1);
                if (count > k)break;//防止越界。count>k就可以退出计算了
            }
            if (k <= count) {//如果k小于等于count,则表明首字符的确应为a
                x.push_back('a');
                n--;//问题缩减为 n-1个a和m个z 中找第k大
            } 
            else {
                x.push_back('z');
                m--;//问题缩减为 n-1个a和m个z 中找第k-count大
                k -= count;
            }
        }
        //循环结束后,剩余子序列只存在"aa..aaa" 或 "zz..zzz"1种情况
        if (k != 1) {//
            cout << -1;
            return;
        }
        while (n--)x.push_back('a');
        while (m--)x.push_back('z');
        for (int i = 0; i < x.size(); i++) {
            cout << x[i];
        }
    }
};
int main() {
    Solution a;
    int n, m;
    long long k;
    while (cin >> n >> m >> k) {
        a.solve(n, m, k);
    }
    return 0;
}
编辑于 2018-08-15 16:31:00 回复(23)
def Cnm(a, b):
    ans =1
    for i in range(a+1, a + b +1):
        ans *=i
    for i in range(1, b +1):
        ans //=i
    return ans

n, m, k =map(int, input().strip().split())
if Cnm(n, m) < k:
    print(-1)
else:
    ans =""
    while n > 0 and m > 0:
        temp =Cnm(n -1, m)
        if temp <k:
            k-=temp
            ans +="z"
            m -=1
        else:
            ans +="a"
            n -=1
    ans +="a"*n
    ans +="z"*m
    print(ans)
python3的答案,注意除法那里要改成“//”,要不然会溢出报错,参考了上面python2的答案。
编辑于 2018-08-15 10:54:27 回复(5)
//参考52Hz'大佬C++代码改写为Java
import java.util.ArrayList;
import java.util.Scanner; public class Main {     public static void main(String[] args) {         Scanner scan = new Scanner(System.in);         int m = scan.nextInt();//a的个数         int n = scan.nextInt();//z的个数         long target = scan.nextInt();//目标第几个         long k =0;         ArrayList<String> list = new ArrayList<String>();         while(m>0&&n>0) {//当a和z均存在时执行             k = pz(m-1,n,target);//假设a确定,出去a之后剩余a和z的排列组合个数             if(k>=target) {//如果确定a之后,剩余的排列组合数大于目标,则说明a已确定                 list.add("a");                 m--;//a的个数减1             }else {//如果确定a之后,剩余的排列组合数小于目标,则说明不是a。                 list.add("z");                 n--;//z的个数减1                 target -= k;//目标减掉排列组合数。因为如果a开头可以有k中情况,                             //减掉k之后即为确定z开头之后,接下来找第target个即可。             }         }         if(target != 1) {//存在经过计算之后必为1             System.out.println("-1");             return;         }else {             while(m>0) {//如果z的个数为0,则将a追加到最后即可                 list.add("a");                 m--;             }             while(n>0) {//如果a的个数为0,则将z追加到最后即可                 list.add("z");                 n--;             }         }         for (int i = 0; i < list.size(); i++) {             System.out.print(list.get(i));         }     }     public static long pz(int m,int n,long target) {//计算假设a确定之后,a之后的部分排列组合数         if(m==0||n==0)             return 1;         long sum = m+n;         long k = 1;         n = Math.min(m, n);//C(m+n) n=C(m+n) m  取最小即可         for (int i = 0; i < n ; i++) {             k *= sum-i;             k /= (i+1);             if(k>target)//防止大数。如果k>target 则只进行list.add("a")和m--//a的个数减1。                         //没有target -= k;因此不影响                 break;         }         return k;     } }

发表于 2018-09-01 22:41:46 回复(1)
思路:最早的启发源于计算机组成原理中的格雷码(循环码),开始与末尾的编码具有高度对称性,每确定一个字符,就相当于将编码范围划分为两半,符合条件的编码数也被划分为两半,故算法框架类似于二分法; 对于n ‘a’+ m 'z'符合调价的编码个数为C(n+m,n), 另外在具体实现时,利用了组合的性质:C(n+m,m)=C(n+m,n)。
特别注意:k的值非常大,超过了int的范围,应设置为long类型,!!!!


编辑于 2018-09-13 23:01:10 回复(0)
 var line = readline().split(' ');
    var n = parseInt(line[0]),
        m = parseInt(line[1]),
        k = parseInt(line[2]);
    var str = '';
    while(n && m){
        var cnt = 1;
        for(var i=0;i<n-1;i++){
            cnt *= n-1+m-i;
            cnt /= i+1;  //计算n-1+m个位置放n-1个a
            if(cnt > k) break; //防止越界。count>k就可以退出计算了
        }
        if(cnt >= k) {
            //说明首字母就是'a'
            str += 'a';
            n--;  //问题缩减为 n-1个a和m个z 中找第k个单词
        }else{
            str += 'z';
            m--;   //问题缩减为 n个a和m-1个z 中找第k-cnt个单词
            k -= cnt;
        }
    }
    //循环结束后,剩余子序列只存在"aa..aaa" 或 "zz..zzz"1种情况
    if(k!=1){
        print(-1);
    }else{
        while(n--){
            str += 'a';
        }
        while(m--){
            str += 'z';
        }
        print(str);
    }    


发表于 2018-10-04 20:34:22 回复(0)

//思路,利用字典排序的规律进行选择:
构造一个排列计算函数,计算m+n长度的字符串中,m个z的排列共有多少种可能性C(m,m+n)
首先固定第一位为a,
假如在剩下的m+n-1个位置中选择m个z的位置的排列数小于选取序号k,则说明不在这个排列集合中,此时,可以确定,序号k的数在剩下的排列数中,则第一位序号为z,此时m=m-1,k=k-C(m,m+n-1)
​假如选取序号k<C(m,m+n-1),则说明该数在首字母为a的排列数中,此时n=n-1,继续在剩下的字符中按照这种规则进行判断序号k和排列数的关系,直到m和n一方变为0未知
最后,将剩下的m或n补全即可

def C(n, m):
    ret = 1
    for i in range(n + 1, n + m + 1):
        ret *= i
    for i in range(1, m + 1):
        ret //= i
    return ret

if __name__ == "__main__":
    n, m, k = map(int, input().strip().split(' '))
    ans = ""
    if C(n, m) < k:
        ans += '-1'
    else:
        while n and m:
            temp = C(n - 1, m)
            if temp < k:
                k -= temp
                ans += 'z'
                m -= 1
            else:
                ans += 'a'
                n -= 1
        ans += 'a' * n
        ans += 'z' * m
    print(ans)
发表于 2019-07-24 17:23:20 回复(3)
import java.math.BigInteger;
import java.util.Scanner;

//java版本,虽然AC,但是求总组合数用到了大数,不知道大佬们有没有好的解决方案
public class Main{
    static StringBuilder str = new StringBuilder();
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            if(new BigInteger(k+"").compareTo(count(m,n)) > 0) {
                System.out.println(-1);
            }else {
                hh(n,m,k);
                System.out.println(str.toString());
            }
        }
    }
    
    public static void hh(int m, int n, int k) {
        if(m == 0) {
            for(int i = 0; i < n; i++) {
                str.append("z");
            }
            return;
        
        if(n ==0) {
            for(int i = 0; i < m; i++) {
                str.append("a");
            }
            return;
        }
        BigInteger count = count(m-1,n);
        if(count.compareTo(new BigInteger(k+""))>=0) {
            str.append("a");
            hh(m-1,n,k);
        } else {
            str.append("z");
            k -= count(m-1,n).intValue();
            hh(m,n-1,k);
        }
    }
    //计算C(m,m+n)
    private static BigInteger count(int m,int n) {
        int min = Math.min(m, n);
        BigInteger count = new BigInteger("1");
        for(int i = m+n-min+1; i <= m+n; i++) {
            count = count.multiply(new BigInteger(i+""));
        }
        for(int i = 1; i <= min; i++) {
            count = count.divide(new BigInteger(i+""));
        }
        return count;
    }
    
}

发表于 2018-08-30 16:28:10 回复(1)
#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define BIG 1000000000
using namespace std;

typedef long long ll;

vector<char> res;
int ok;

// 求全排列C(n,m),如果越界,返回BIG
long long Col(ll n, ll m){

    m = (n-m)<m?(n-m): m;
    ll div = m;
    ll ret = 1;
    for(ll i=n; i>=n-m+1; i--){
        ret *= i;
        while(ret%div==0 && div!=1)
            ret/= div--;

        if(ret<0)//越界啦
            return BIG;
    }

    return ret;
}

void solve(ll n, ll m, ll k){

    ll cTot = Col(n+m , m);

    //k大于全排列数,无解
    if(cTot < k) {
        ok = 0;
        return;
    }

    //n==0,或者m==0表示解唯一了啊
    if((!n || !m)){
        if(n>0)
            while(n--)
                res.push_back('a');
        else if(m>0)
            while(m--)
                res.push_back('z');
        return;
    }


    ll c0 = Col(n-1+m, m);
    if(c0 >=k){
        //#当前位置取'a'
        res.push_back('a');
        solve(n-1,m, k);
    } else{
        //#当前位置取'z'
        res.push_back('z');
        solve(n,m-1, k-c0);
    }

}


int main() {

    int n,m,k;

    while(~scanf("%d%d%d",&n, &m, &k)){

        ok = 1;
        res.clear();
        solve(n,m,k);

        if(ok){
            for(int i=0; i<res.size(); i++)
                printf("%c",res[i]);
            puts("");
        } else
            puts("-1");
    }



    return 0;
}

发表于 2018-08-15 00:17:36 回复(0)
顶我上去,全场最好理解

1.n个'z'和m个‘a’组成的组合数的关系

dp[i][j]=dp[i-1][j]+dp[i][j-1]

2.关于找第几个的问题,递归

固定右边x位,从m-1个z开始固定,a的个数逐渐增加

刚好没有进入下一层递归,就应该是aaazz..zzaaa这种形式

如果不是k不是刚好减去就应该是aa...aazxxxxx后面就进入xxxx里面再做一层递归

import java.util.*; public class Main { public static void main(String[] args) {
           Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int k=sc.nextInt(); long[][] dp=new long[101][101]; //dp[i][j]i个'a'和j个'b'的组合数 for(int i=0;i<101;i++)
               dp[i][0]=1; for(int j=1;j<101;j++)
               dp[0][j]=1; for(int i=1;i<101;i++) { for(int j=1;j<101;j++) {               
                   dp[i][j]=dp[i-1][j]+dp[i][j-1];                                                      
                 }
           } if(dp[n][m]<k)
           {
               System.out.println("-1"); return;
           }
           Main main=new Main();
           StringBuilder sb=new StringBuilder();
           main.solve(n, m, k, sb, dp);          
    } public void solve(int a,int z,int k,StringBuilder sb,long[][] dp) { if(a==0) { for(int i=0;i<z;i++) sb.append("z");
              System.out.println(sb.toString()); return;
           } if(z==0) { for(int i=0;i<a;i++) sb.append("a");
              System.out.println(sb.toString()); return;
           } int la=0,lz=z-1; while(k-dp[la][lz]>=0)
           {
              k-=dp[la][lz];
              la++;
           } if(k==0)
           { for(int i=0;i<a-la+1;i++) sb.append("a"); for(int i=0;i<z;i++) sb.append("z"); for(int i=0;i<la-1;i++) sb.append("a");
              System.out.println(sb.toString()); return;
           } for(int i=0;i<a-la;i++) sb.append("a");
           sb.append("z");
           solve(la,lz,k,sb,dp);
     }
}

编辑于 2019-07-27 14:10:29 回复(0)
"""
n个'a'和m个'z',排列组合有C(n,m)种结果
利用以上性质找到字典序第k个单词
"""
import sys


def C(n, m):
    ret = 1
    for i in range(n + 1, n + m + 1):
        ret *= i
    for i in range(1, m + 1):
        ret //= i
    return ret


if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n, m, k = list(map(int, input().strip().split()))
    ans = ""
    if C(n, m) < k:
        ans += '-1'
    else:
        while n and m:
            temp = C(n - 1, m)
            if temp < k:
                k -= temp
                ans += 'z'
                m -= 1
            else:
                ans += 'a'
                n -= 1
        ans += 'a' * n
        ans += 'z' * m
    print(ans)

发表于 2019-07-03 20:14:39 回复(0)
import math
n, m, k =list(map(int,input().split()))
def C(n,m):    #组合公式
    return  math.factorial(n+m)/(math.factorial(n)*math.factorial(m))
r = []
def solve(n,m,k):
    if n ==0:
        for i in range(m):
            r.append('z')
        return
    if m ==0:
        for i in range(n):
            r.append('a')
        return
    if k > C(n-1,m):    #以a开头可能的字符串为C(n-1,m)种,均排在以z开头前,
        r.append('z')
        solve(n,m-1,k-C(n-1,m))    #以z开头,问题转为剩余字串中第k-C(n-1,m)个
    else:
        r.append('a')
        solve(n-1,m,k)
if k> max_k:
    print(-1)
else :
    solve(n,m,k)
    print(''.join(r))



编辑于 2019-03-17 11:39:42 回复(0)
n,m,k=list(map(int,input().split()))
nn=n;mm=m
l=[]
jc=[1]
for i in range(m+n):
    jc.append((i+1)*jc[i])
if k>jc[n+m]/(jc[m]*jc[n]):
    print('-1')
else:
    for i in range(1,mm+nn+1):
        an=jc[m+n-1]/(jc[n-1]*jc[m])
        if k<=an:
            l.append('a')
            n-=1
        else:
            l.append('z')
            m-=1
            k=k-an
    l=''.join(l)
    print(l)

发表于 2018-11-05 00:25:01 回复(0)
  // 读取
  const input = readline().split(/\s/)
  const n = parseInt(input[0])
  const m = parseInt(input[1])
  const k = parseInt(input[2])

  let answer
  let queue = []
  let i = 0
  let aDone = false

  // 跳床
  function trampoline(f){
    var func = f;
    while (typeof func === 'function'){
      func = func();
    }
    return func;
  }

  // 递归
  // 先考虑a, 再考虑z
  function getItem (n, m, ret) {

    if (n === 0 && m === 0) {

      ++i

      if (i === k) {
        answer = ret
        aDone = true
        queue.length = 0
        return
      }

      if (queue.length > 0) {
        let _ret = queue.pop()
        let _m = queue.pop()
        let _n = queue.pop()
        return getItem.bind(null, _n, _m, _ret)
      }
    }

    if (n > 0 && m > 0) {

      queue.push(n, m - 1, ret.concat('z'))

      return getItem.bind(null, n - 1, m, ret.concat('a'))


    } else if (n > 0) {

      return getItem.bind(null, n - 1, m, ret.concat('a'))

    } else if (m > 0) {

      return getItem.bind(null, n, m - 1, ret.concat('z'))

    }

  }
  // 全排列 [aazz azaz azza zaaz zaza zzaa]
  // 递归改循环, 避免js内存溢出
  const getList = () => {

    // a开头
    trampoline(getItem.bind(null, n - 1, m, 'a'))

    // z开头
    !aDone && trampoline(getItem.bind(null, n, m - 1, 'z'))

  }

  // 查找 ? xxxx : -1
  getList()
  print(answer || -1)

1 40%, 超时
2 循环大数据时CPU超100%
3 谁能用js做出
100 100 Math.pow(10, 9)
或者说 100%的 大神 麻烦贴下代码, 先给您跪了

编辑于 2018-09-08 00:38:54 回复(0)

#include<iostream>
using namespace std;
/*c[a][z] 表示a个'a',z个'z'共有的组合数*/
int c[101][101];
/*递归从左只右计算每个'z'的前面有几个'a'并打印*/
void print(int a,int z,int k)
{
    if(a==0)
    {
        for(int i=0;i<z;i++) cout<<'z';
        return;
    }
    if(z==0)
    {
        for(int i=0;i<z;i++) cout<<'a';
        return;
    }
    
    int la=0,lz=z-1;
    while(k-c[la][lz]>=0)
    {
        k-=c[la][lz];
        la++;
    }
    if(k==0)
    {
        for(int i=0;i<a-la+1;i++) cout<<'a';
        for(int i=0;i<z;i++) cout<<'z';
        for(int i=0;i<la-1;i++) cout<<'a';
        return;
    }
    for(int i=0;i<a-la;i++) cout<<'a';
    cout<<'z';
    print(la,lz,k);
}

int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    
    int i,j;
    /*计算所有情况的组合数(1=<a,z<=100,由于k<10^9所以不需要超过int范围的组合数的计算,所以此处溢出的数直接表示为int_max)*/
    for(i=0;i<101;i++)
    {
        c[0][i]=1;
        c[i][0]=1;
    }
    for(i=1;i<101;i++)
    {
        for(j=1;j<101;j++)
        {
            c[i][j]=c[i-1][j]+c[i][j-1];
            if(c[i][j]<0)
            {
                c[i][j]=0x7FFFFFFF;
            }
        }
    }
    if(c[n][m]<k)
    {
        cout<<c[n][m]<<" "<<k<<endl;
        cout<<-1;
        return 0;
    }
    print(n,m,k);
    return 0;
}

若有需要解释可以提问
编辑于 2018-08-14 23:29:59 回复(0)
#include <stdio.h>
 
long long pz(int n, int m, long long k)
{
    if(!n || !m)
        return 1;
    int min = (n>m) ? m : n;
    long long count = 1;
    for(int i=0; i<min; i++)
    {
        count *= m+n-i;
        count /= i+1;
        if(count > k) break;
    }
    return count;
}
 
int main()
{
    int n,m;
    long long k;
    while(scanf("%d%d%lld", &n,&m,&k) != EOF)
    {
        char *res = (char *)malloc((n+m+1) * sizeof(char));
        int idx=0;
        while(n && m)
        {
            long long count = pz(n-1,m,k);
            if(k <= count)
            {
                res[idx] = 'a';
                idx++;
                n--;
            }
            else
            {
                res[idx] = 'z';
                idx++;
                m--;
                k -= count;
            }
        }
        if(k != 1)
        {
            printf("%d\n", -1);
            break;
        }
        else
        {
            while(n--)
            {
                res[idx] = 'a';
                idx++;
            }
            while(m--)
            {
                res[idx] = 'z';
                idx++;
            }
        }
        res[m+n] = '\0';
        puts(res);
        free(res);
        res = NULL;
    }
    return 0;
}


发表于 2019-10-21 00:07:51 回复(0)
f(n,m) = f(n-1,m) + f(n,m-1)
生成一个表 然后从右下角起步。   
<=  f(row-1,col)  插入 a 大于插入z
最后 判断row,col  为0 的情况  
其实和热评第一一样的思路,只是我只想到这个,数学差啊TvT. 
n,m,k = map(int,input().split())

f = list([0] * (m+1) for i in range(n+1))
for i in range(m+1):
    f[0][i] = 1
for i in range(n+1):
    f[i][0] = 1

for i in range(1, n+1):
    for j in range(1, m+1):
        f[i][j] = f[i-1][j] + f[i][j-1]

row = n
col = m
rst = list()

if k > f[row][col]:
    print(-1)
else:
    while(True):
        if not row:
            rst.append('z'* col)
            break
        if not col:
            rst.append('a'* row)
            break
        if k <= f[row][col]:
            if k <= f[row-1][col]:
                rst.append('a')
                row -= 1
            else:
                rst.append('z')
                k -= f[row-1][col]
                col -= 1
    print(''.join(rst))


发表于 2019-09-07 11:05:50 回复(0)
def cu(a,b):
    s=1
    if a*b==0:return 1
    for i in range(a+b,a,-1):
        s*=i
    for i in range(1,b+1):
        s=s//i
    return s
n,m,k=list(map(int,input().split(" ")))
str=""
t=n+m
if cu(n,m)<k:print (-1)
else:
    while len(str)<t:
        f=cu(n-1,m)
        if k>f :
            str+="z"
            k=k-f
            m=m-1
        else:
            str+="a"
            n=n-1
    if str=="":print(-1)
    else:print(str)

发表于 2019-09-05 16:21:22 回复(0)
import sys
n, m, k = list(map(int, sys.stdin.readline().strip().split()))

res = ''


def Cnm(n, m):
    count = 1
    for i in range(n+m, n, -1):
        count *= i
        count /= (n+m - i + 1)
    return count


def find_kth_string(n, m, k):
    count = Cnm(n, m)
    if count < k:
        return -1

    if k == 1 and ((m == 0) or (n == 0)):
        global res
        if n != 0:
            res += 'a' * n
        else:
            res += 'z' * m
        return

    count2 = Cnm(n - 1, m)
    if count2 >= k:
        global res
        res += 'a'
        find_kth_string(n - 1, m, k)
    else:
        global res
        res += 'z'
        find_kth_string(n, m - 1, k - count2)


find_kth_string(n, m, k)

if res == '':
    print(-1)
else:
    print(res)
编辑于 2019-09-01 11:53:35 回复(0)
假设第一个位置是a,则共有C(m+n-1,n-1)种可能,若k大于它,第一个位置应该是z,否则为a,依次类推分析第二个位置。
需要注意求组合数C(m+n-1,n-1)时容易溢出,可以把k传进去,大于k的时候就没有必要算了。
#include<vector>
#include<iostream>
using namespace std;
long long C(int N, int M, int k) {
	long long sum = 1;
	for(int i=1;i<=M; i++) {
		sum=sum*(N-M+i)/i;
        if(sum>=k) return sum;
	}
	return sum;
}
int main(){
    int n, m, k;
    cin>>n>>m>>k;
    int total = m+n;
    total--;
    string res="";
    while(n && m){
        long long tmp = C(total, n-1, k);
        if(tmp<k){
            res += "z";
            m--;
            k -= tmp;
        }
        else{
            res += "a";
            n--;
        }
        total--;
    }
    if(k!=1){
        cout<<"-1";
        return 0;
    }
    while(n--) res += "a";
    while(m--) res += "z";
    cout<<res;
}


发表于 2019-08-30 18:03:39 回复(0)
利用STL库函数中的字典序查找算法next_permutation()暴力搜索,完成度50%,用时超过1000ms,失败了,看见热评第一的答案,给大佬跪了。
#include<iostream>
#include<cstring>
#include<algorithm>
typedef unsigned char BYTE;
typedef unsigned short DBYTE;
using namespace std;
 
class Solution
{
public:
    void FetchKthWord(unsigned int k, const char *init_word, char **target_word, DBYTE len)
    {
        char temp[len];
        *target_word=NULL;
        strcpy(temp, init_word);
        unsigned int i=1;
        do
        {
            if(i==k)
            {
                *target_word=temp;
                break;
            }
            else
            {
                i++;
            }
        }while(next_permutation(temp,temp+len));
        if (i!=k) std::cout<<-1<<std::endl;
        else std::cout<<*target_word<<std::endl;
    }
     
};
 
int main()
{
    DBYTE n,m;
    unsigned int k;
    std::cin>>n>>m>>k;
    std::string aarray(n,'a');
    std::string zarray(m,'z');
    std::string orignal=aarray+zarray;
    char *tar=NULL;
    Solution solver;
    solver.FetchKthWord(k,orignal.c_str(),&tar,n+m);
    return 0;
}


发表于 2019-08-24 21:14:29 回复(0)

热门推荐

通过挑战的用户

查看代码