字符串与进制转换课堂笔记

一、这两天的核心内容

这组题目主要围绕两类基础能力展开：

1. 字符串处理：把数字当作字符串读入、逐字符判断、字符与数值互相转换。
2. 进制转换：先把任意进制转换成十进制，再把十进制转换成目标进制。

这两个内容经常一起出现。例如 FF 不是普通的十进制整数，必须先按字符串逐位读取；而进制转换的结果也可能包含 A~Z 或 a~z。

---

二、字符串基础

1. 为什么进制数要用 string 读入

当一个数可能包含字母时，不能使用 int 或 long long 直接读入：

string s;
cin>>s;

例如：

FF
101101
1A3

2. 字符和数值的转换

数字字符转数值：

int x=s[i]-'0';

大写字母转数值：

int x=s[i]-'A'+10;

小写字母转数值：

int x=s[i]-'a'+10;

数值转字符：

if(x<=9) c=char(x+'0');
else c=char(x-10+'A');

3. 字符串下标

字符串下标从 0 开始：

string s;
cin>>s;
for(int i=0;i<s.size();i++){
    cout<<s[i];
}

如果需要从个位开始处理，通常从字符串末尾向前枚举：

for(int i=s.size()-1;i>=0;i--){
    //s[i]是从低位到高位处理的
}

4. 字符串处理的注意点

• s.size() 的类型是无符号整数，倒序循环时建议写成 int i=s.size()-1，并保证字符串非空。
• 进制题中要同时考虑数字字符和字母字符。
• 输出进制数时要明确题目要求大写还是小写。
• 0 的特殊情况不能直接套“短除法”，因为 while(x>0) 不会执行。

---

三、进制转换

1. 任意进制转十进制

设数字为 d[k-1]...d[1]d[0]，进制为 jz，则：

d[k-1] * jz^(k-1) + ... + d[1] * jz + d[0]

从右往左处理，维护当前位权 t：

int ans=0,t=1;
for(int i=s.size()-1;i>=0;i--){
    ans+=num(s[i])*t;
    t*=jz;
}

例如 1101 转十进制：

1*2^3+1*2^2+0*2^1+1*2^0=13

2. 十进制转任意进制

使用短除法：

1. 不断除以目标进制。
2. 每次记录余数。
3. 余数的顺序是从低位到高位，所以最后要反转。

string ans;
while(x>0){
    int ys=x%jz;
    ans=对应字符+ans;
    x/=jz;
}

当 x==0 时，答案应为字符串 "0"。

3. 两种进制之间转换

最稳妥的做法是分成两步：

a进制字符串 -> 十进制整数 -> b进制字符串

题目数据保证十进制值不超过 1e9 时，可以使用 long long 保存中间结果。

4. 进制字符表

本组题目使用的字符规则：

数值	大写表示	小写表示
0~9	0~9
10~35	A~Z	a~z

写函数时，输入和输出的大小写要按照题目要求处理。5657 AtoB 要求使用小写字母；其他几题主要使用大写字母。

---

四、通用模板

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;

int toten(string s,int jz){
    int ans=0,t=1,sz;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]>='0'&&s[i]<='9') sz=s[i]-'0';
        else if(s[i]>='A'&&s[i]<='Z') sz=s[i]-'A'+10;
        else sz=s[i]-'a'+10;
        ans+=sz*t;
        t*=jz;
    }
    return ans;
}

string tento(int x,int jz){
    if(x==0) return "0";
    string ans;
    while(x>0){
        int ys=x%jz;
        if(ys<=9) ans=char(ys+'0')+ans;
        else ans=char(ys-10+'A')+ans;
        x/=jz;
    }
    return ans;
}

复杂度：设字符串长度为 L，两次转换都是 O(L)，额外空间为 O(L)。

---

五、五道题目整理

5649. 小张的进制转换

题意概括

给出 k 组无符号整数 n 和进制 b，输出 n 在 b 进制下的表示。进制为 16 时，结果前面要加 0X，字母使用大写。

题目分析

每一组数据独立处理，直接使用短除法。

• n==0 时直接输出 0。
• 余数 0~9 输出数字字符。
• 余数 10~15 输出 A~F。
• 当 b==16 时，在结果前加上 0X。

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int k,n,b;

string change(int x,int jz){
    if(x==0) return "0";
    string ans;
    while(x>0){
        int ys=x%jz;
        if(ys<=9) ans=char(ys+'0')+ans;
        else ans=char(ys-10+'A')+ans;
        x/=jz;
    }
    return ans;
}

int main(){
    cin>>k;
    while(k--){
        cin>>n>>b;
        string ans=change(n,b);
        if(b==16) cout<<"0X";
        cout<<ans<<endl;
    }
    return 0;
}

关键点：这道题只有十进制转其他进制，不需要先调用 toten。

---

5651. 第几个数

题意概括

由数字 0,3,5,8 组成的所有数字按数值从小到大排列，给出其中一个数字，求它在序列中的序号，序号从 1 开始。

例如：

0, 3, 5, 8, 30, 33, 35, 38, ...

题目分析

数字长度越长，数值一定越大，所以先统计比它短的所有数字：

4^1+4^2+...+4^(len-1)

同长度的数字可以看成四进制数：

0 -> 0
3 -> 1
5 -> 2
8 -> 3

长度大于 1 时，第一位不能为 0，所以第一位的编号要减去 1。最后再加 1，得到从 1 开始的序号。

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
string s;

int get(char c){
    if(c=='0') return 0;
    if(c=='3') return 1;
    if(c=='5') return 2;
    return 3;
}

int main(){
    cin>>s;
    int len=s.size();
    long long ans=0,p=1;
    for(int i=1;i<len;i++){
        p*=4;
        ans+=p;
    }
    if(len==1&&s[0]=='0'){
        cout<<1;
        return 0;
    }
    long long rank=0;
    for(int i=0;i<len;i++){
        int x=get(s[i]);
        if(i==0&&len>1) x--;
        rank=rank*4+x;
    }
    cout<<ans+rank+1;
    return 0;
}

关键点：不要真的枚举所有数字，长度最多 10，使用四进制编号可以直接计算答案。

---

5652. 任意进制转任意进制

题意概括

输入原进制 n、一个 n 进制数、目标进制 m，将这个数转换成 m 进制。进制范围为 2~36，字母使用大写。

题目分析

分两步完成：

1. 从右向左，把原进制字符串转换成十进制。
2. 用短除法，把十进制转换成目标进制。

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
string s;

int toten(string s,int jz){
    int ans=0,t=1,sz;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]>='0'&&s[i]<='9') sz=s[i]-'0';
        else sz=s[i]-'A'+10;
        ans+=sz*t;
        t*=jz;
    }
    return ans;
}

string tento(int x,int jz){
    if(x==0) return "0";
    string ans;
    while(x>0){
        int ys=x%jz;
        if(ys<=9) ans=char(ys+'0')+ans;
        else ans=char(ys-10+'A')+ans;
        x/=jz;
    }
    return ans;
}

int main(){
    cin>>n>>s>>m;
    int x=toten(s,n);
    cout<<tento(x,m);
    return 0;
}

关键点：本题输入是三行，但使用 cin 时空格和换行都可以直接读取，不需要额外处理。

---

5656. 进制转换

题意概括

给出十进制数 X 和目标进制 M，输出 X 的 M 进制表示。M<=16，超过 9 的数位使用大写字母 A~F。

题目分析

这道题是最基础的十进制转进制：重复做除法和取余，最后把余数逆序输出。X=0 时要单独输出 0。

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int x,m;

string change(int x,int jz){
    if(x==0) return "0";
    string ans;
    while(x>0){
        int ys=x%jz;
        if(ys<=9) ans=char(ys+'0')+ans;
        else ans=char(ys-10+'A')+ans;
        x/=jz;
    }
    return ans;
}

int main(){
    cin>>x>>m;
    cout<<change(x,m);
    return 0;
}

---

5657. AtoB

题意概括

给出一个 a 进制数 c，把它转换成 b 进制并输出。输入数字可能含有字母，因此必须用字符串读入。大于 9 的数位使用小写字母：a 表示 10，b 表示 11，一直到 z 表示 35。输出格式为：

(answer)b

题目分析

仍然采用“先转十进制，再转目标进制”的两步法，但这里要注意：

• 输入字母是小写。
• 输出字母也必须是小写。
• 输出结果后面还要拼接目标进制 b。
• 题目保证十进制值可以使用 long long 保存。

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
string s;
int a,b;

int toten(string s,int jz){
    int ans=0,t=1,sz;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]>='0'&&s[i]<='9') sz=s[i]-'0';
        else sz=s[i]-'a'+10;
        ans+=sz*t;
        t*=jz;
    }
    return ans;
}

string tento(int x,int jz){
    if(x==0) return "0";
    string ans;
    while(x>0){
        int ys=x%jz;
        if(ys<=9) ans=char(ys+'0')+ans;
        else ans=char(ys-10+'a')+ans;
        x/=jz;
    }
    return ans;
}

int main(){
    cin>>s>>a>>b;
    int x=toten(s,a);
    cout<<"("<<tento(x,b)<<")"<<b;
    return 0;
}

---

六、统一易错点

1. 把含字母的进制数用整数读入：必须使用 string。
2. 短除法余数顺序写反：余数要插入到字符串前面，或者最后 reverse。
3. 忘记处理 x==0：结果应该是 "0"。
4. 大小写写错：5657 是小写字母，其余题目按题面使用大写。
5. 5657 输出格式漏括号或目标进制：必须输出 (answer)b。
6. 5651 直接暴力生成序列：应该使用长度统计和四进制编号。
7. 进制转换中位权溢出：数据较大时使用 long long 更稳妥。

---

七、课堂总结

遇到进制题，先判断题目属于哪一种：

十进制 -> 其他进制：短除法
其他进制 -> 十进制：按位权展开
任意进制 -> 任意进制：先转十进制，再转目标进制

遇到字符串题，先判断每个字符代表的数值，再根据题目要求决定使用大写还是小写输出。只要把“字符”和“数值”之间的转换写成清楚的小函数，代码就会更短、更不容易出错。