洛谷B3869题：位权法实现K进制转十进制

一、题目解读

洛谷B3869题目要求将输入的K进制数（2≤K≤16）转换为对应的十进制数值。用户需处理多组数据，每组包含进制K和K进制字符串，输出转换结果。题目考察进制转换的基本原理与算法实现，需确保对字符到数值的映射及权重计算的准确性。

二、解题思路

核心思路为“位权法”，即通过逐位解析K进制数的字符，将其映射为数值（0-15），并结合当前位的权重（k^(length-1-i)）累加求和。关键在于设计字符转换函数（charToValue）与权重计算逻辑，避免复杂幂运算，通过循环迭代实现高效转换。

三、解题步骤

1. 输入处理：循环读取N组数据，每组解析K与num字符串。

2. 字符转换：通过charToValue函数将字符（‘0’-‘9’或‘A’-‘F’）转换为对应数值（0-15），非法字符返回-1（但题目保证不会出现）。

3. 权重计算：从右到左遍历num，每位权重为k^(length-1-i)，通过result *= k + value迭代累加，避免递归或指数计算。

4. 输出结果：每组转换后的十进制数值单独输出。

四、代码与注释

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

// 将字符转换为对应的数值（0-15）
int charToValue(char c) {
    if (c >= '0' && c <= '9') return c - '0'; // 数字字符直接映射
    if (c >= 'A' && c <= 'F') return 10 + (c - 'A'); // 字母字符映射为10-15
    return -1; // 非法字符（题目保证不会出现）
}

// 将K进制字符串转换为十进制数
long long kToDecimal(const string& num, int k) {
    long long result = 0;
    int length = num.length();
    
    for (int i = 0; i < length; ++i) {
        int value = charToValue(num[i]); // 获取当前字符数值
        // 计算当前位的权重：k^(length-1-i)
        result = result * k + value; // 更高效的计算方式（避免幂运算）
    }
    
    return result;
}

int main() {
    ios::sync_with_stdio(false); // 加快输入/输出
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    for (int i = 0; i < N; ++i) {
        int K;
        string num;
        cin >> K >> num;
        
        cout << kToDecimal(num, K) << "\n"; // 输出转换结果
    }
    
    return 0;
}

五、总结

本解法通过位权法实现了K进制到十进制的线性时间转换，关键在于字符映射与权重迭代计算的优化。代码简洁高效，避免了复杂数学库依赖，适用于竞赛及实际开发中的进制转换场景。理解位权法的逻辑对掌握进制转换算法至关重要，建议结合实例调试以加深理解。