解题思路

这是一道从结果反推构造的题目。我们需要从目标数量的'a'开始，反向思考如何构造原始字符串。 关键思路：

  1. 从高位字母开始构造，每个字母可以分裂成两个小一位的字母
  2. 需要找到最小的字母位置k，使得2^k ≥ x
  3. 从k位置开始，逐步处理剩余数量，必要时添加较小位置的字母

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    long long x;
    cin >> x;
    
    string ans;
    // 找到最高位
    int k = 0;
    long long pow2 = 1;
    while(pow2 < x) {
        k++;
        pow2 *= 2;
    }
    
    // 从高位往低位构造
    while(x > 0) {
        while(k >= 0 && (1LL << k) > x) {
            k--;
        }
        if(k < 0) break;
        ans += (char)('a' + k);
        x -= (1LL << k);
    }
    
    if(x == 0) cout << ans << endl;
    else cout << -1 << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        
        StringBuilder ans = new StringBuilder();
        // 找到最高位
        int k = 0;
        long pow2 = 1;
        while(pow2 < x) {
            k++;
            pow2 *= 2;
        }
        
        // 从高位往低位构造
        while(x > 0) {
            while(k >= 0 && (1L << k) > x) {
                k--;
            }
            if(k < 0) break;
            ans.append((char)('a' + k));
            x -= (1L << k);
        }
        
        System.out.println(x == 0 ? ans.toString() : -1);
    }
}

x = int(input())

ans = []
# 找到最高位
k = 0
pow2 = 1
while pow2 < x:
    k += 1
    pow2 *= 2

# 从高位往低位构造
while x > 0:
    while k >= 0 and (1 << k) > x:
        k -= 1
    if k < 0:
        break
    ans.append(chr(ord('a') + k))
    x -= (1 << k)

print(''.join(ans) if x == 0 else -1)

算法及复杂度

  • 算法：贪心构造。从最高位开始，逐步构造字符串。
  • 时间复杂度： ，主要是找到最高位和构造过程。
  • 空间复杂度： ，需要存储构造的字符串。