Dev-C++调试及编码效率经验
1.环境配置
- 视图栏下的项目管理和状态条打开
- 工具->编译选项
- ->编译器配置为
TDM-GCC 4.9.2 64-bit Debug - ->代码生成->优化级别(-Ox)为
Debug(g) - ->语言标准 (-std) 为
ISO C++11 - ->连接器->产生调试信息为
Yes
- ->编译器配置为
- 如果不想像第 2 条一样手动找,可以在编译时加入一下命令:
本文介绍了 C++ 在 OJ 题目中的环境配置(Dev-C++)、输入输出优化(cin/cout/setw)、字符串操作(string/find/substr)、STL 容器(vector/unordered_set)、排序算法(sort/priority_queue)及数学函数应用。包含高精度除法、矩阵乘法、欧拉函数等基础算法实现,并总结了刷题时的代码编写习惯与注意事项。
TDM-GCC 4.9.2 64-bit DebugDebug(g)ISO C++11Yes-g -Wall -O2 -std=c++11
Console Applicationch 的地方,临时写几行代码,将其内容复制到一个普通数组中,然后观察这个数组cout 容器的值实用的'快手'快捷键清单,能极大提升编码效率。
代码移动与缩进
| 你要做的操作 | 神奇快捷键 | 小贴士 |
|---|---|---|
| 整段代码向左移 | Shift + Tab | 选中代码,按一下就左移一格(一个 Tab 缩进)。 |
| 整段代码向右移 | Tab | 同样是选中后操作,和左移是好搭档。 |
| 单行或选中行上移/下移 | Ctrl + Shift + ↑/↓ | 移动单行无需选中,光标放在该行即可;移动多行则需要先选中。 |
| 让代码格式变整齐 | Ctrl + Shift + A | 一键自动缩进对齐 |
高效行操作
| 你要做的操作 | 神奇快捷键 | 小贴士 |
|---|---|---|
| 快速删除一整行 | Ctrl + D | 不用再从头拖到尾按删除键了,光标放在要删的行上直接按就行。 |
| 快速复制并粘贴一行 | Ctrl + E | 会立刻在下方复制出一模一样的一行 |
编辑与辅助
| 你要做的操作 | 神奇快捷键 | 小贴士 |
|---|---|---|
| 注释/取消注释一行或多行 | Ctrl + / | 调试代码时临时屏蔽某段代码,这个功能非常常用。 |
| 触发代码补全 | 默认 Ctrl + 空格 | 可以帮你自动补全函数名、变量名。如果和输入法切换冲突,可以去 工具 -> 快捷键选项 里修改成别的键,比如 Ctrl+Enter。 |
你可以在 Dev-C++ 的菜单栏点击 '工具' -> '快捷键选项',查看或自定义所有快捷键,打造一套完全属于你自己的快捷操作习惯。
vector<char> ch={'G','g','P','p','L','l','T','t'};//添加查看 ch 后点击下一步无反应// 在代码中临时添加 char debug_ch[8]; std::copy(ch.begin(), ch.end(), debug_ch);// 现在在调试器中观察 debug_ch 即可
cin和cout输入输出注意:
cin的>>默认按十进制解析数字字符串,它会自动忽略前导零。
scanf的%d会按十进制解析数字,并自动忽略前导零。
头文件:#include<iomanip>
函数:setw()
int main() {
int num = 123;
// 右对齐(默认)
cout << "右对齐:|" << setw(5) << num << "|" << endl;
// 输出:| 123|
// 左对齐
cout << "左对齐:|" << left << setw(5) << num << "|" << endl;
// 输出:|123 |
// 内部填充(中间对齐)
cout << "内部对齐:|" << internal << setw(5) << num << "|" << endl;
// 输出:| 123|
return 0;
}
setw()注意: 格式化浮点数时宽度包含小数点".`"
#include<iostream>
#include<iomanip>
using namespace std;
int main() {
int integer = 123;
double decimal = 12.3456;
// 整数
cout << "整数:" << setw(5) << integer << endl;
// 输出: 123
// 浮点数
cout << "浮点数:" << setw(8) << decimal << endl;
// 输出: 12.3456
// 浮点数 + 设置小数位数
cout << fixed << setprecision(2);
// 固定小数点,保留 2 位
cout << "浮点数 (2 位):" << setw(8) << decimal << endl;
// 输出: 12.35
// 科学计数法
cout << scientific << setprecision(3);
cout << "科学计数:" << setw(12) << decimal << endl;
// 输出:1.235e+01
return 0;
}
如果不熟悉或者忘记了就用传统 C 风格
int main() {
int num = 123;
// 使用 printf
printf("|%5d|\n", num);
// 右对齐,宽度 5
// 输出:| 123|
printf("|%-5d|\n", num);
// 左对齐,宽度 5
// 输出:|123 |
printf("|%05d|\n", num);
// 用 0 填充,宽度 5
// 输出:|00123|
double d = 12.345;
printf("|%8.2f|\n", d);
// 宽度 8,保留 2 位小数
// 输出:| 12.35|
return 0;
}
setfill()头文件:#include<iomanip>
函数:setfill()
它的核心作用是与 setw() 配合使用:当输出的数据宽度不足 setw() 指定的宽度时,会用 setfill() 设置的字符填充空白部分。
#include<iomanip>// 必须包含此头文件
int main() {
int num = 42;
// 示例 1:用 '*' 填充,宽度为 10,默认右对齐
cout << setfill('*') << setw(10) << num << endl;
// 输出:********42 (左侧填充了 8 个*,总宽度 10)
// 示例 2:用 '0' 填充数字(非常常见)
cout << setfill('0') << setw(5) << num << endl;
// 输出:00042
//默认右对齐,以下是左对齐
cout << setfill('-') << left << setw(10) << num << endl;
// 输出:42-------- (右侧填充)
return 0;
}
注意:
setfill(),它对后续所有输出持续生效,直到再次更改。setfill() 设置在循环里面了而恰好循环没有执行就相当于没有设置了cout << setfill('*') << setw(5) << 1 << endl; // ****1
cout << setw(5) << 2 << endl; // ****2 (仍使用*填充)
cout << setw(5) << 2 << setw(5) << 1 << endl; // ****2****1 (仍使用*填充)
cout << setfill(' ') << setw(5) << 3 << endl; // " 3" (重置为空格)
getline()cin在输入时是不会读取空格和换行符的,getline( 输入流(如 cin),存储读取内容的字符串 str,分隔符(默认为换行符 '\n')) 是 C++ 中用于从输入流读取一行字符串的函数,它会读取包括空格在内的所有字符,直到遇到分隔符后停止读取(默认为换行符)。
头文件:#include<string>
函数:getline()
int main() {
string line;
// 从标准输入读取一行
getline(cin, line);
cout << line << endl;
cout << "字符串长度:" << line.length() << endl;
return 0;
}
注意:cin >> 后接 getline() 会立即返回空字符串,需要在 cin >> 后清除缓冲区 cin.ignore()
cout << "输入年龄:"; cin >> age;
// 清除缓冲区中的换行符
cin.ignore(numeric_limits<streamsize>::max(), '\n');
// 或者简单点:cin.ignore();
cout << "输入姓名:";
getline(cin, name);
// 现在会正常等待输入
字符串声明输入输出:
string ch; cin>>ch; cout<<ch;
优先用 cin和 cout,因为用 scanf和 printf太麻烦了,除非大量级别的输入输出才用 scanf和 printf
//语法
for(元素类型 变量名 : 容器/数组/字符串){
// 循环体
}
//举例
string N;
for(char ch : N){
// 对每个字符执行操作
}
含义:依次将字符串 N 中的每个字符赋值给变量 ch,然后执行循环体。
等效传统写法:
// 传统 for 循环(使用下标)
string N;
//下标 0 开始
for(int i = 0; i < N.length(); i++){
char ch = N[i];
// 循环体
}
// 或者使用迭代器
for(string::iterator it = N.begin(); it != N.end();++it){
char ch = *it;
// 循环体
}
其他场景应用:
int arr[]={1,2,3,4,5};
for(int num : arr){
cout << num << " ";
}
// 输出:1 2 3 4 5
#include<vector>
vector<int> vec ={10,20,30};
for(int val : vec){
cout << val << " ";
}
// 输出:10 20 30
int charToValue(char ch){
if(ch >= '0'&& ch <= '9'){
return ch - '0';
}
else if(ch >= 'A'&& ch <= 'F'){
return ch - 'A'+10;
}
else if(ch >= 'a'&& ch <= 'f'){
return ch - 'a'+10;
}
return -1;// 无效字符
}
to_string()头文件:#include<string>
函数:to_string()
支持的数据类型:int,long,long long,unsigned,unsigned long,unsigned long long,float,double,long double
基本用法:
int main(){
// 整数转字符串
int num1 = 123;
string str1 = to_string(num1); // "123"
// 浮点数转字符串
double num2 = 45.678;
string str2 = to_string(num2); // "45.678000"
// 负数和零
int num3 = -100;
string str3 = to_string(num3); // "-100"
string str4 = to_string(0); // "0"
// 可以用于输出
cout << "Number: " << to_string(123) << endl;
return 0;
}
头文件:#include<cctype>
函数:toupper(),tolower()
方式 1: 使用 C++11范围 for循环
int main(){
string str1 = "Hello World";
// 转换为大写
for(char&c : str1)
c = toupper(c);
// 转换为小写
string str2 = "HELLO WORLD";
for(char&c : str2)
c = tolower(c);
return 0;
}
方式 2: 使用 transform + toupper/tolower
// 转换为大写
transform(str.begin(), str.end(), str.begin(), ::toupper);
// 转换为小写
transform(str.begin(), str.end(), str.begin(), ::tolower);
注意:
C++中有两个版本的 toupper/tolower函数:
int toupper(int c)std命名空间中,有多个重载版本为了避免歧义,使用 ::toupper明确指定使用全局命名空间中的 C 标准库版本。
transform()头文件:#include<algorithm>
函数:transform()
基本语法:
transform(first1,last1,d_first,unary_op);
| 参数 | 描述 |
|---|---|
first1, last1 | 输入序列的起始和结束迭代器(左闭右开区间 [first1, last1)) |
d_first | 输出序列的起始迭代器 |
unary_op | 一元操作函数,接受一个参数并返回转换后的值 |
使用模式:
transform(输入开始,输入结束,输出开始,转换函数);
以上是一元操作,二元操作以后遇到再作补充
find()头文件:#include<string>
函数:find()
基本语法:
size_t find(char c, size_t pos = 0)const;
c:要查找的字符 (也可以是字符串或 string对象)pos:开始查找的位置(默认从 0 开始)string::npossize_t(无符号整数类型)string::npos(通常定义为 -1 或最大可能值)| 方法 | 功能 | 返回值 | 示例 |
|---|---|---|---|
find() | 查找字符/子串第一次出现 | 位置或 npos | s.find('a') |
rfind() | 查找字符/子串最后一次出现 | 位置或 npos | s.rfind('a') |
find_······_of()相关函数的对比
| 函数 | 功能 | 示例 |
|---|---|---|
find_first_not_of() | 查找第一个不在指定集合中的字符 | "abc123".find_first_not_of("abc") 返回 3(字符'1') |
find_first_of() | 查找第一个在指定集合中的字符 | "abc123".find_first_of("123") 返回 3(字符'1') |
find_last_not_of() | 从后往前查找第一个不在指定集合中的字符 | "abc ".find_last_not_of(" ") 返回 2(字符'c') |
find_last_of() | 从后往前查找第一个在指定集合中的字符 | "abc123".find_last_of("abc") 返回 2(字符'c') |
string str = "abc123def";
cout << "字符串:\"" << str << "\"" << endl;
cout << "find_first_not_of(\"abc\"): " << str.find_first_not_of("abc") << endl; // 3
cout << "find_first_of(\"123\"): " << str.find_first_of("123") << endl; // 3
cout << "find_last_not_of(\"def\"): " << str.find_last_not_of("def") << endl; // 5
cout << "find_last_of(\"123\"): " << str.find_last_of("123") << endl; // 5
用途:
①去除前导/尾随特定字符
②检查字符串是否符合特定格式
③提取有效数据部分
④跳过不需要的字符
关键:
①返回第一个不在指定集合中的字符位置
②找不到时返回 string::npos
③常与 substr()、erase() 等函数配合使用
substr()头文件:#include<string>
函数:substr()
基本语法:
string substr(size_t pos = 0, size_t len = npos)const;
pos:子串的起始位置(从 0 开始计数),默认为 0len:要提取的字符数,默认为 string::npos(提取到字符串末尾)string 对象,包含提取的子串重要提示:
pos 参数是否有效,避免 out_of_range 异常find() 配合使用时,注意 find() 返回 npos 的情况string s = "Hello";
// 易错 1:忘记检查 find 的返回值
size_t pos = s.find('z');
string sub = s.substr(pos); // 如果 pos == npos,会抛出异常
// 正确做法
pos = s.find('z');
if(pos != string::npos){
sub = s.substr(pos);
}
// 易错 2:混淆长度和结束位置
string s2 = "Hello, world!";
size_t commaPos = s2.find(',');
// 错误:提取从逗号到位置 5(可能不是想要的结果)
string wrong = s2.substr(commaPos, 5);
// 正确:如果想提取 5 个字符,使用长度
string correct = s2.substr(commaPos + 1, 5);
replace()将字符串中指定位置和长度的子串替换为新的字符串。
头文件:#include<string>
函数:replace()*
语法:
str.replace(开始位置,长度(包含开始位置),代替换的字符串)
string str = "Hello World";
str.replace(6, 5, "C++"); // 从位置 6 开始,替换 5 个字符
cout << str; // 输出:Hello C++
std::sto*用于将字符串转换为各种数值类型
头文件:#include<string>
函数:std::sto*
| 函数 | 转换类型 | 头文件 | 异常 |
|---|---|---|---|
std::stoi | int | <string> | invalid_argument, out_of_range |
std::stol | long | <string> | invalid_argument, out_of_range |
std::stoll | long long | <string> | invalid_argument, out_of_range |
std::stoul | unsigned long | <string> | invalid_argument, out_of_range |
std::stoull | unsigned long long | <string> | invalid_argument, out_of_range |
std::stof | float | <string> | invalid_argument, out_of_range |
std::stod | double | <string> | invalid_argument, out_of_range |
std::stold | long double | <string> | invalid_argument, out_of_range |
基本语法:
long long stoll(const string& str, size_t* idx = 0, int base = 10);
// 推荐用法:在分数解析中使用 stoll
string fraction = "15/8";
size_t pos = fraction.find('/');
if(slashPos != string::npos){
long long a = stoll(fraction.substr(0, pos)); // 分子
long long b = stoll(fraction.substr(pos + 1)); // 分母
}
erase()和remove()使用 erase-remove 惯用法来删除容器中满足条件的元素,而不是在循环中逐个删除
string str;
// 错误示例:循环中多次调用 erase() - O(n²)
for(size_t i = 0; i < str.length();){
if(str[i] == ' '){
str.erase(i, 1); // 每次 erase 都可能导致元素移动
}else{
i++;
}
}
// 正确示例:使用 erase-remove 惯用法 - O(n)
str.erase(remove(str.begin(), str.end(), ' '), str.end());
头文件:#include<string>
函数:erase()
使用该函数写入参数有两个版本,一种是从某位置开始删除若干个字符,一种是指向要删除字符的常量迭代器
版本 1:erase(pos, count)
string str = "Hello World";
// 删除从位置 5 开始的 1 个字符
str.erase(5, 1); // "HelloWorld"
// 删除从位置 0 开始的所有字符
str.erase(0); // 清空字符串
// 只指定开始位置,删除到末尾
str.erase(5); // 删除从位置 5 到结尾
pos:要删除的第一个字符的位置(索引从 0 开始)count:要删除的字符数量(默认 npos,表示删除到字符串末尾)版本 2:erase(position)
string str = "Hello World";
// 删除迭代器指向的字符
auto it = str.begin() + 3; // 指向第 3 个字符(索引从 0 开始)
auto new_it = str.erase(it); // 删除'l',返回指向下一个字符的迭代器
// 此时 str = "Helo World"
// 删除一个范围 [first, last)
auto first = str.begin() + 2; // 指向第 2 个字符 'l'
auto last = str.begin() + 5; // 指向第 5 个字符 ' '
auto new_it = str.erase(first, last); // 删除 "llo"
// 此时 str = "He World"
position:指向要删除字符的常量迭代器first:指向要删除范围起始位置的常量迭代器last:指向要删除范围结束位置之后的常量迭代器头文件:#include<algorithm>
函数:remove()
remove(first,last value)
vector<int> vec = {1,2,3,2,4,2,5};
// 移除所有值为 2 的元素
auto new_end = std::remove(vec.begin(), vec.end(), 2);
// 此时 vec = {1, 3, 4, 5, 4, 2, 5} (逻辑上只有前 4 个有效)
// 实际删除尾部无效元素
vec.erase(new_end, vec.end());
// 此时 vec = {1, 3, 4, 5}
两者的关键区别
| 特性 | erase() | remove() |
|---|---|---|
| 所属 | 容器成员函数 | 算法函数 |
| 是否改变容器大小 | 是 | 否 |
| 实际删除元素 | 是 | 否(仅重新排列) |
| 使用场景 | 直接删除指定位置/范围的元素 | 配合 erase() 删除特定值的元素 |
#include<algorithm>replace()头文件:#include<algorithm>
函数:replace()
替换容器中所有等于某个值的元素为另一个值。
语法:
void replace(ForwardIt first, ForwardIt last,
const T& old_value,
const T& new_value);
[first,last)old_value,new_value:[first,last)范围内所有为 old_value的值都替换为 new_value// 1. 替换 vector 中的值
vector<int> nums = {1,2,3,2,4,2,5};
replace(nums.begin(), nums.end(), 2, 99); // 1 99 3 99 4 99 5
// 2. 替换 string 中的字符
string str = "hello world";
replace(str.begin(), str.end(), 'l', 'L'); // heLLo worLd
// 3. 替换数组中的值
int arr[] = {1,0,1,0,1,0};
int n = sizeof(arr)/sizeof(arr[0]);
replace(arr, arr + n, 0, -1); // 1 -1 1 -1 1 -1
}
创建包含 10 个整数的 vector,所有元素初始化为 0
#include<iostream>
#include<vector>
using namespace std;
int main(){
// 1. 访问越界检查
int arr[10];
// arr[10] = 5; // 可能不会立即报错,但存在风险
vector<int> vec(10);
// vec[10] = 5; // 同样不会报错,但存在风险
// vec.at(10) = 5; // 会抛出 std::out_of_range 异常
// 2. 内存管理
// 传统数组:需要手动管理(如果动态分配)
// vector:自动管理内存
// 3. 大小可变
// 传统数组:大小固定
// vector:大小可以动态改变
vector<int> v(10);
cout << "初始大小:" << v.size() << endl; // 10
// 调整为 20 个元素
v.resize(20);
cout << "调整后大小:" << v.size() << endl; // 20
// 4. 作为函数参数传递
// 传统数组:传递时会退化为指针,丢失大小信息
// vector:可以传递引用,保留所有信息
return 0;
}
如果对 vector<int> vec(10);使用函数 push_back(),那么 vec会有 11 个元素
int main(){
// 创建一个包含 10 个 int 的 vector,全部初始化为 0
vector<int> vec(10);
// 像传统数组一样访问
vec[0] = 10;
vec[1] = 20;
// 使用 push_back 添加第 11 个元素
vec.push_back(30);
// 添加在第 10 个位置(索引 10)
cout << "arr[0] = " << arr[0] << endl; // 10
cout << "arr[1] = " << arr[1] << endl; // 20
cout << "arr[10] = " << arr[10] << endl; // 30(新增的)
cout << "vector 大小:" << arr.size() << endl; // 11
return 0;
}
vector<int> arr[100]和vector<int> arr(100)的区别| 特性 | vector<int> arr[100] | vector<int> arr(100) |
|---|---|---|
| 类型 | 数组(包含 100 个 vector) | 单个 vector(包含 100 个 int) |
| 内存布局 | 100 个独立的 vector 对象 | 1 个 vector 对象,管理 100 个 int |
| 初始状态 | 100 个空 vector | 100 个 int,默认值为 0 |
| 添加元素 | arr[i].push_back(x) 向第 i 个 vector 添加 | arr.push_back(x) 向 vector 末尾添加 |
| 访问元素 | arr[i][j] 访问第 i 个 vector 的第 j 个元素 | arr[j] 访问第 j 个 int 元素 |
| 大小 | 数组大小固定为 100 | vector 大小可变 |
unordered_setsort()头文件:#include<algorithm>
基本语法:
sort(首元素地址 (必填),尾元素地址的下一个地址 (必填),比较函数 (非必填));
时间复杂度:
平均情况:O(N log N) 次比较
最坏情况:O(N log N) 次比较(C++11 起)
对于一个 vector数组进行排序
//升序:sort(v.begin(), v.end(),less<int>());
//降序:sort(v.begin(), v.end(),greater<int>());
//less<int>表示数字大的优先级越大,大顶堆
priority_queue<int> q;
priority_queue<int, vector<int>, less<int>> q;
//greater<int>表示数字小的优先级越大,小顶堆
priority_queue<int, vector<int>, greater<int>>q;
priority_queue 的记忆技巧:
比较器返回 true 表示:第一个参数应该排在第二个参数后面
所以:
less<T>:a < b 为 true,表示 a 优先级低于 b,b 应该在前 -> 大顶堆greater<T>:a > b 为 true,表示 a 优先级低于 b,b 应该在前 -> 小顶堆sort 的记忆技巧:
比较器返回 true 表示:第一个参数应该排在第二个参数前面
所以:
less<T>:a < b 为 true,表示 a 应该在前 -> 升序greater<T>:a > b 为 true,表示 a 应该在前 -> 降序vector<int> num = {5,2,8,1,9};
// 降序排序
sort(num.begin(), num.end(), greater<int>());
| 场景 | 需要什么 | 示例 | 为什么 |
|---|---|---|---|
priority_queue 的声明 | 类型 (Type) | greater<int> | 模板参数列表 <..., ..., 比较器类型> 需要的是一个类型名,来告诉编译器使用哪种比较规则。 |
sort 函数的调用 | 对象 (Instance) | greater<int>() | 函数参数需要一个可调用的对象(函数、函数对象、lambda 等),greater<int>() 是构造一个匿名对象。 |
priority_queue 的 greater<int> 是'蓝图纸',告诉编译器怎么造工具;sort 的 greater<int>() 是'造好的工具',直接递给函数使用。
记住这个核心区别:在模板参数列表(尖括号<>里)你要的是类型;在函数参数列表(圆括号()里)你要的是对象实例。
#include<cmath>abs():abs(value)获取 value的绝对值。ceil():ceil(value)获取大于等于 value的最小整数。floor():floor(value)获取小于等于 value的最大整数。sqrt():sqrt(value)获取 value的平方根。pow():pow(base, exponent)获取 base的 exponent次幂。pow()函数强调一下使用时要注意的细节:
pow()函数返回的是 double类型,对于某些整数计算结果,可能会有微小的浮点误差cout << pow(2.1, 30) << endl; // 4.64065e+009
cout << fixed << pow(2.1, 30) << endl; // 4640650289.117170
cout << fixed << round(pow(2.1, 30)) << endl; // 4640650289.000000
cout << fixed << setprecision(0) << pow(2.1, 30) << endl; // 4640650289
对于纯输出,可以用 fixed和 setprecision(0)组合,只影响显示格式,会在显示时进行四舍五入,但实际数值不变。
在程序进行数据操作时,用 round()函数:实际进行四舍五入计算,返回新的值。
在进行 2的整数次幂时,用位运算 <<
cout << (1 << 2) << endl; // 2 的 2 次方
概念: 高精度除法是处理大整数(超过标准数据类型范围)的除法运算。通常使用字符串表示大整数,模拟手算除法的过程。
模拟手算除法过程:
string quotient = ""; // 商(字符串形式)
int remainder = 0; // 当前余数
对于被除数中的每一个字符 digit_char:
1. 将当前余数乘以 10+
当前位的数字:remainder = remainder * 10+(digit_char - '0')
2. 计算当前位的商:current_quotient = remainder / divisor
3. 更新余数:remainder = remainder % divisor
4. 将当前位的商转换为字符,添加到 quotient 末尾
// 删除前导零,但要保留至少一个字符
quotient.erase(0, quotient.find_first_not_of('0'));
if(quotient.empty()) quotient = "0";
123456 ÷ 789过程:被除数:"123456"
除数:789
处理过程:
第 1 位 '1': 余数 = 0×10+1=1
商位 = 1 ÷ 789=0
新余数 = 1%789=1
商 ="0"
第 2 位 '2': 余数 = 1×10+2=12
商位 = 12 ÷ 789=0
新余数 = 12%789=12
商 ="00"
第 3 位 '3': 余数 = 12×10+3=123
商位 = 123 ÷ 789=0
新余数 = 123%789=123
商 ="000"
第 4 位 '4': 余数 = 123×10+4=1234
商位 = 1234 ÷ 789=1
新余数 = 1234%789=1234-789=445
商 ="0001"
第 5 位 '5': 余数 = 445×10+5=4455
商位 = 4455 ÷ 789=5(因为 789×5=3945,789×6=4734>4455)
新余数 = 4455-3945=510
商 ="00015"
第 6 位 '6': 余数 = 510×10+6=5106
商位 = 5106 ÷ 789=6(因为 789×6=4734,789×7=5523>5106)
新余数 = 5106-4734=372
商 ="000156"
去掉前导零:商 ="156",余数 = 372
验证:789 × 156+372=123084+372=123456
代码模板:
#include<iostream>
#include<string>
using namespace std;
struct DivisionResult{
string quotient; //商
int remainder; //余数
};
DivisionResult* divide(string dividend, int divisor){
DivisionResult* node = new DivisionResult{"", 0};
// 逐位处理被除数
for(char ch : dividend){
node->remainder = node->remainder * 10+(ch - '0');
node->quotient.push_back(node->remainder / divisor +'0');
node->remainder %= divisor;
}
// 去除前导零
node->quotient.erase(0, node->quotient.find_first_not_of('0'));
if(node->quotient.empty()) node->quotient = "0";
return node;
}
int main(){
string dividend = "123456";
int divisor = 789;
DivisionResult* result = divide(dividend, divisor);
cout << "商:" << result->quotient << endl;
cout << "余数:" << result->remainder << endl;
delete result;
return 0;
}
定义:
矩阵乘法需要满足第一个矩阵的列数 = 第二个矩阵的行数。如果矩阵
A是m×n的,矩阵B是n×p的,那么它们的乘积C = AB是一个m×p的矩阵。
元素计算公式
对于结果矩阵 C 中的第 i 行第 j 列元素:
C i j = ∑ k = 1 n A i k × B k j
其中:
示例:
A =[1 2 3]
B =[7 8]
[4 5 6][9 10]
[11 12]
C[0][0]=1×7+2×9+3×11=7+18+33=58
C[0][1]=1×8+2×10+3×12=8+20+36=64
C[1][0]=4×7+5×9+6×11=28+45+66=139
C[1][1]=4×8+5×10+6×12=32+50+72=154
结果:C =[58 64]
[139 154]
代码示例: 已知矩阵 A,矩阵 B,求矩阵 C=AB
int mA, nA, //矩阵 A m 行,n 列
int nB, pB; //矩阵 B n 行,p 列
vector<vector<int>> a(mA, vector<int>(nA));
vector<vector<int>> b(nB, vector<int>(pB));
vector<vector<int>> c(mA, vector<int>(pB)); //矩阵 C m 行,p 列
for(int i=0;i<m;i++){
for(int j=0;j<p;j++){
for(int k=0;k<n;k++){
c[i][j]+=a[i][k]*b[k][j];
}
}
}
欧拉函数 Euler(n):表示不大于 n 且与 n 互质的正整数的个数,Euler(1)=1
由唯一分解定理,n=p1k1✖p2k2✖ …✖pnkm,pi均为质数,ki是其幂次
由此可推出欧拉函数的求法:Euler(n)=n/p1✖(p1-1)/p2✖(p2-1)/…/pn✖(pn-1)
模板如下:
long long euler_phi(ll n){
long long res = n; // 初始结果为 n
// 试除质因数,i 从 2 到 sqrt(n)
for(long long i = 2; i * i <= n;++i){
if(n % i == 0){
// i 是 n 的一个质因子
while(n % i == 0) n /= i; // 除掉所有因子 i
res -= res / i; // 应用公式:res = res * (1 - 1/i)
}
}
// 如果 n 最后剩下 >1,说明它是一个质因子
if(n > 1)
res -= res / n;
return res;
}
注意:
欧拉函数 ( φ(n)的值由 (n) 的质因数分解决定。
如果先把 (ab) 对 MOD 取模得到 M,那么 M 的质因数分解与 (ab) 的质因数分解通常没有直接关系。
例如:
因此,先取模再求欧拉函数得不到正确结果。
在完全 (m) 叉树中,若某结点的编号为 x,则:它的第一个子结点编号为
(x-1)*m + 2。它的最后一个子结点编号为x*m + 1。
推导:根结点 1 的子结点为 2 ~ m+1,符合公式。对于任意结点,它之前的 x-1 个结点每个都有 m 个子结点,所以它的第一个子结点为 (x-1)*m + 2,最后一个子结点在此基础上加 m-1,即 x*m + 1。
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
int T; cin >> T;
while(T--){
ll n, m, k; cin >> n >> m >> k;
ll left = k, right = k;
ll ans = 1;
while(true){
left = (left - 1) * m + 2;
right = right * m + 1;
if(left > n) break;
if(right > n){
right = n;
ans += right - left + 1;
break;
}
ans += right - left + 1;
}
cout << ans << '\n';
}
return 0;
}
输入操作可以写成一行:
//输入:1
// What Is this prime? I,don't know
int n;
string s;
cin >> n;
cin.ignore();
getline(cin, s);
cout << s << endl;
for()、if()循环和 while()循环内部如果只有一行时代码可以写成一行:
for(int i=0;i<10;i++)
cout << i; // 0123456789
int i=10;
if(i==10)
cout << i << endl; // 10
while(i--)
cout << i; // 9876543210
//终极写法,不建议,除非很熟
int i=3;
while(i--)
for(int i=0;i<3;i++)
if(i<3)
cout << i; // 012012
用三元操作符:
()?():()
int i=1;
i ? cout << "i 为真" << endl : cout << "i 为假" << endl; // i 为真
find()+replace()string str = "hello world, ll is not ll";
size_t pos = 0;
while((pos = str.find("ll", pos)) != string::npos){
str.replace(pos, 2, "LL");
pos += 2; // 跳过已替换的部分
}
cout << str << endl; // 输出:heLLo world, LL is not LL
n在<=20时才可以创建,需要内存约 20MB,如果大于该层数,优先考虑数学计算而非实际构建数据结构。getline()吞掉一整行。pos要更新为第一个子串末尾的下一个位置),重叠等情况(重叠情况例如s1="aa",在字符串"aaa"中,从 pos=0开始查找,下一次应该从 pos=1开始,而不是 pos=2,否则会错过可能的匹配)。vector时会拷贝整个数组,效率极低,平时建议用全局数组或引用传递const修饰后,表明函数不会修改原对象,同时还能接受临时对象(如字面量或表达式结果)作为参数。传值要复制整个数据结构,而 const & 只是传递一个引用(相当于一个指针),所以对于大对象,性能差距巨大。
微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online