C++ OJ 题目处理步骤与常用技巧

编辑与辅助

你可以在 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会按十进制解析数字，并自动忽略前导零。

1.输出字符宽度

头文件:#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;
}

2.不同类型数字的格式化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" (重置为空格)

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

1.输入输出

字符串声明输入输出：

string ch; cin>>ch; cout<<ch;

优先用 cin和 cout，因为用 scanf和 printf太麻烦了，除非大量级别的输入输出才用 scanf和 printf

2.字符串遍历

//语法
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

3.字符转换

字符转换为对应进制的数字值

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函数：

1. **C 标准库版本：**在全局命名空间中，定义为 int toupper(int c)
2. **C++模板版本：**在 std命名空间中，有多个重载版本

为了避免歧义，使用 ::toupper明确指定使用全局命名空间中的 C 标准库版本。

容器元素转换操作transform()

头文件:#include<algorithm>
函数：transform()
基本语法：

transform(first1,last1,d_first,unary_op);

使用模式：

transform(输入开始，输入结束，输出开始，转换函数);

以上是一元操作，二元操作以后遇到再作补充

4.查找字符串特定元素find()

头文件:#include<string>
函数：find()
基本语法：

size_t find(char c, size_t pos = 0)const;

• c：要查找的字符 (也可以是字符串或 string对象)
• pos：开始查找的位置（默认从 0 开始）
• 返回值：找到的位置（从 0 开始计数），如果未找到则返回 string::npos
• 返回类型是 size_t（无符号整数类型）
• 如果未找到，返回特殊常量 string::npos（通常定义为 -1 或最大可能值）

查找指定字符集合在字符串的位置系列find_······_of()

相关函数的对比

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() 等函数配合使用

5.提取字符串特定元素substr()

头文件:#include<string>
函数：substr()
基本语法：

string substr(size_t pos = 0, size_t len = npos)const;

• pos：子串的起始位置（从 0 开始计数），默认为 0
• len：要提取的字符数，默认为 string::npos（提取到字符串末尾）
• 返回值：一个新的 string 对象，包含提取的子串

重要提示：

1. 总是检查 pos 参数是否有效，避免 out_of_range 异常
2. 与 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);

6.字符串替换replace()

将字符串中指定位置和长度的子串替换为新的字符串。
头文件:#include<string>
函数：replace()*
语法：

str.replace(开始位置，长度（包含开始位置），代替换的字符串)

string str = "Hello World";
str.replace(6, 5, "C++"); // 从位置 6 开始，替换 5 个字符
cout << str; // 输出：Hello C++

7.字符串转换数值类型函数std::sto*

用于将字符串转换为各种数值类型
头文件:#include<string>
函数：std::sto*

基本语法：

long long stoll(const string& str, size_t* idx = 0, int base = 10);

• str：要转换的字符串
• idx：可选参数，指向 size_t 类型的指针，用于存储第一个未转换字符的位置索引
• base：可选参数，数值基数（进制），默认为 10（十进制）
• 返回值：转换后的 long long 整数

// 推荐用法：在分数解析中使用 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)); // 分母
}

8.删除容器（字符串）中满足条件的元素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}

• first, last：定义要处理的元素范围的迭代器
• value：要移除的元素值
• 返回值：指向新的逻辑末尾的迭代器，指向最后一个有效元素的下一个位置
• 功能：重新排列元素，将不需要删除的元素移到前面
• 关键特点：
  • 不删除元素：只是将不匹配的元素移到前面
  • 不改变容器大小：容器末尾的原始元素仍然存在

两者的关键区别

算法函数#include<algorithm>

1.将所有特定值替换另一个值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
}

动态数组 vector

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;
}

2.vector<int> arr[100]和vector<int> arr(100)的区别

STL 容器

1.哈希表unordered_set

排序类

1.快速排序：sort()

头文件：#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>());

2.优先队列：

//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 的 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 次方

数学基础

1.高精度除法

概念： 高精度除法是处理大整数（超过标准数据类型范围）的除法运算。通常使用字符串表示大整数，模拟手算除法的过程。

模拟手算除法过程：

1. 初始化

string quotient = ""; // 商（字符串形式）
int remainder = 0; // 当前余数

2. 从被除数的最高位（最左端字符）开始，逐位处理到最低位

对于被除数中的每一个字符 digit_char：
1. 将当前余数乘以 10+
当前位的数字：remainder = remainder * 10+(digit_char - '0')
2. 计算当前位的商：current_quotient = remainder / divisor
3. 更新余数：remainder = remainder % divisor
4. 将当前位的商转换为字符，添加到 quotient 末尾

3. 计算完成后，商可能有多余的前导零，去掉

// 删除前导零，但要保留至少一个字符
quotient.erase(0, quotient.find_first_not_of('0'));
if(quotient.empty()) quotient = "0";

4. 文字演示计算 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;
}

2.矩阵乘法

定义：

矩阵乘法需要满足第一个矩阵的列数 = 第二个矩阵的行数。如果矩阵 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

其中：

• i = 1, 2, …, m（行数）
• j = 1, 2, …, p（列数）
• k = 1, 2, …, n（求和变量）

示例：

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];
        }
    }
}

3.欧拉函数

欧拉函数 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;
}

注意：

1. 欧拉函数定义在整数上，不能先取模

欧拉函数 ( φ(n)的值由 (n) 的质因数分解决定。
如果先把 (ab) 对 MOD 取模得到 M，那么 M 的质因数分解与 (ab) 的质因数分解通常没有直接关系。
例如：

• a=2, b=3，则 ab=8，φ(8)=4。
• 若 MOD=5，(8 mod 5 = 3)，φ(3)=2)，显然 (4 ≠ 2)。

因此，先取模再求欧拉函数得不到正确结果。

树类

1.完全 m 叉树子树结点数求解

1. 问题描述
   给定一棵包含 n 个结点的完全 m 叉树，结点按层序遍历编号（根为 1，从左到右）。
   有 T 组询问，每组给定 n, m, k，求以编号 k 的结点为根的子树所包含的结点总数（包括结点 k 本身）。
2. 解题思路
   完全 m 叉树的编号规律

在完全 (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.代码便捷写法

输入操作可以写成一行：

//输入：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 为真

2.替换字符串里面所有特定子串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

刷题心得

1. 当遇到会连续反复替换的情况，前面替换结果可能会影响后面替换判断，不一定设置标记数组才可以解决这个问题。尝试使用假串来替换也是个不错的选择。
2. 构建二叉树，要根据题目给的数据范围来决定，层数 n在<=20时才可以创建，需要内存约 20MB，如果大于该层数，优先考虑数学计算而非实际构建数据结构。
3. 在 break 跳出循环语句输出答案的时候注意本环节还有没有待输入的。如果还有，就要把本环节的输入吞掉，一般用 getline()吞掉一整行。
4. 查找多个字符子串要注意，子串之间可能相互包含（看题目，如果不能包含找第二个的时候 pos要更新为第一个子串末尾的下一个位置），重叠等情况（重叠情况例如s1="aa"，在字符串"aaa"中，从 pos=0开始查找，下一次应该从 pos=1开始，而不是 pos=2，否则会错过可能的匹配）。
5. 所有直觉规律皆不可取，除非有数学支撑，因为在多种题目约束下最优解可能违反这个直觉规律。
6. 要有从中间向两边扩散的思想，不能只会枚举枚举两个区间
7. 函数传递动态数组vector时会拷贝整个数组，效率极低，平时建议用全局数组或引用传递
8. 引用传递：函数接收的是实参的别名，本质上传递的是地址（类似指针），不涉及任何元素复制无论容器多大，传引用都只需传递一个地址，时间开销极小（常数时间）。加上 const修饰后，表明函数不会修改原对象，同时还能接受临时对象（如字面量或表达式结果）作为参数。传值要复制整个数据结构，而 const & 只是传递一个引用（相当于一个指针），所以对于大对象，性能差距巨大。