首页 > 试题广场 > 小易的字典
[编程题]小易的字典
  • 热度指数:15461 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

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

小易的这个字典很奇特, 字典内的每个单词都包含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 回复(32)
//参考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 回复(3)
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)
思路:最早的启发源于计算机组成原理中的格雷码(循环码),开始与末尾的编码具有高度对称性,每确定一个字符,就相当于将编码范围划分为两半,符合条件的编码数也被划分为两半,故算法框架类似于二分法; 对于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)

//思路,利用字典排序的规律进行选择:
构造一个排列计算函数,计算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 回复(4)
 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)
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 回复(1)
"""
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 <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    int n,m;
    ll k;
    while(cin>>n>>m>>k){
        string s = "";
        while(n && m){
            ll cnt = 1;
            for(int i=0;i<n-1;i++){
                cnt *= (n-1+m-i);
                cnt /= (i+1);
                if(cnt>k)
                    break;
            }
            if(k<=cnt){
                s += 'a';
                n--;
            }else{
                s += 'z';
                m--;
                k -= cnt;
            }
        }
        if(k!=1)
            cout<<-1<<endl;
        else{
            while(n--)
                s += 'a';
            while(m--)
                s += 'z';
            cout<<s<<endl;
        }
    }
    return 0;
}

发表于 2019-12-12 09:15:32 回复(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)

递归解法,每次确定一位字母

string _findk(int n, int m, int k){
    if(n==0){
        return string(m,'z');
    }else if(m==0){
        return string(n, 'a');
    }
    n--;
    long long cnt = 1;
    for(int i=0; i<n; i++){
        cnt *= (m+n-i);
        cnt /= (i+1);
        if(cnt>k) break;
    }
    if(cnt>=k){
        return "a" + _findk(n, m, k);
    }else{
        if(cnt*(n+m+1)/(n+1)<k) return "-1";
        return "z" + _findk(n+1, m-1, k-cnt);  
    }
}
void _azword(){
    int n,m,k;
    cin >> n >> m >> k;
    cout << _findk(n,m,k) << endl;
}
发表于 2020-06-27 11:29:15 回复(0)
/*
count(n,m)=count(n-1,m)+count(n,m-1)
count(0,k)=1
count(k,0)=1
*/
#include<bits/stdc++.h>
using namespace std;
const long long maxValue=1e9;
int main()
{
    string res="";
    int n,m;
    long long k;
    cin>>n>>m;
    cin>>k;
    vector<vector<long long >>count(n+1,vector<long long>(m+1,0));
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0)
            {
                count[i][j]=1;
            }
            else
            {
                if(count[i-1][j]+count[i][j-1]>=maxValue)
                {
                    count[i][j]=maxValue;
                }
                else
                {
                    count[i][j]=count[i-1][j]+count[i][j-1];
                }
            }
        }
     
    int i=n;
    int j=m;
    if(count[i][j]<k)
    {
        cout<<-1<<endl;
        return 0;
    }
    while(i&&j)
    {
        if(i>0)
        {
            if(k<=count[i-1][j])
            {
                res=res+'a';
                i--;
            }
            else if(j>0)
            {
                res=res+'z';
                k=k-count[i-1][j];
                j--;
            }
        }
    }
    while(i>0)
    {
        res=res+'a';
        i--;
    }
    while(j>0)
    {
        res=res+'z';
        j--;
    }
    cout<<res<<endl;
    return 0;
}

发表于 2020-06-15 14:58:39 回复(0)
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int k = Integer.parseInt(line[2]);
        // 特判
        if (k > combination(n, n + m, k)) {
            System.out.print(-1 + "");
            return;
        }
        StringBuilder sb = new StringBuilder();
        while (n > 0 && m > 0) {
            // 开头为 a 的组合数
            long c = combination(n - 1, n + m - 1, k);
            if (k > c) { // 大于则以 z 开头
                sb.append("z");
                k -= c;
                m--;
            } else { // 小于则以 a 开头
                sb.append("a"); 
                n--;
            }
        }
        // 结尾处理
        if (n > 0) {
            while (n > 0) {
                sb.append("a"); 
                n--;
            }
        } else {
            while (m > 0) {
                sb.append("z");
                m--;
            }
        }
        System.out.print(sb);
    }
    
    public static long combination(int n, int m, int k) {
        long c = 1;
        for (int i = 0; i < n; i++) {
            c *= m - i;
            c /= i + 1;
            if (c > k) break;
        }
        return c;
    }
}
java
一开始用动态规划求组合数,但是处理溢出实在太麻烦了。
发表于 2020-05-14 01:34:06 回复(0)
AC=20%,递归解法,求大佬指导
#include <iostream>
(720)#include <vector>
#include <algorithm>

using namespace std;

bool isSwap(char *from, char * to) {
    char * p;
    for (p = from; p < to; p++)
    {
        if (*p == *to)
        {
            return false;
        }
    }
    return true;
}

void helper(vector<char> & vec, int from, int to, int &k) {
    if (to <= 1) {
        return;
    }
    if (from == to) {
        if (k-- == 1) {
            for (int i=0; i <= to; i++) {
                cout << vec[i];
            }
            cout << endl;
        }
    }
    else
    {
        for (int j = from; j <= to; j++) {
            if (isSwap(&vec[from], &vec[j])) {
                swap(vec[j], vec[from]);
                helper(vec, from + 1, to, k);
                swap(vec[j], vec[from]);
            }
        }
    }
}

int main() {
    int n, m, k;
    cin>>n>>m>>k;
    vector<char> vec;
    while(n--){
        vec.push_back('a');
    }
    while(m--){
        vec.push_back('z');
    }
    helper(vec, 0, vec.size()-1, k);
    return 0;
}


发表于 2020-04-11 22:48:21 回复(0)
参考 GeeksforGeeks nCr写法:
#include <iostream>
#include <string>
using namespace std;

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
	unsigned long long temp;
	while (b) {
		temp = a;
		a = b;
		b = temp % b;
	}
	return a;
}

unsigned long long nCr(int n, int r)
{
	if (n - r < r) r = n - r; // nCr(n, r) == nCr(n, n - r), choose smaller r

	unsigned long long a = 1, b = 1, m;

	while (r) {
		// multiply
		a *= n;
		b *= r;
		// divide
		m = gcd(a, b);
		a /= m;
		b /= m;
		//
		--n;
		--r;
	}
	return a;
}

bool getWord(int n, int m, unsigned int k, string& result)
{
	if (n < 0 || m < 0 || k <= 0 || k > nCr(n + m, n)) return false;

	while (n && m) {
		unsigned long long startByA = nCr(n + m - 1, n - 1);
		if (k <= startByA) { // if 'a'
			result.push_back('a');
			--n;
		}
		else { // if 'z'
			result.push_back('z');
			--m;
			k -= startByA;
		}
	}

	// push remaining letters
	while (n--) result.push_back('a');
	while (m--) result.push_back('z');

	return true;
}

int main()
{
    // input
	int n, m;
	unsigned int k;
	cin >> n >> m >> k;

    // solve
	string result;
	bool success = getWord(n, m, k, result);

    // print
	if (success) cout << result << endl;
	else cout << -1 << endl;
    
    return 0;
}


编辑于 2020-03-26 16:54:51 回复(0)