OJ题情况处理步骤C++

情况处理步骤目录

• Dev-C++调试经验
  • 环境配置
  • Debug
• `cin`和`cout`输入输出
  • 输出字符宽度
  • 不同类型数字的格式化`setw()`
    • 输出字段填充字符`setfill()`
  • 输入时空格也要读取的情况`getline()`
• 字符串string
  • 输入输出
  • 字符串遍历
  • 字符转换
    • 字符转换为对应进制的数字值
    • 数值类型转换为字符串`to_string()`
    • 字母大小写转换
      • 容器元素转换操作`transform()`
  • 查找字符串特定元素`find()`
    • 查找指定字符集合在字符串的位置系列`find_······_of()`
  • 提取字符串特定元素`substr()`
  • 字符串替换`replace()`
  • 字符串转换数值类型函数`std::sto*`
  • 删除容器（字符串）中满足条件的元素`erase()`和`remove()`
• 算法函数`#include<algorithm>`
  • 将所有特定值替换另一个值`replace()`
• 动态数组vector
  • 分配固定空间
  • `vector<int> arr[100]`和`vector<int> arr(100)`的区别
• STL容器
  • 哈希表`unordered_set`
• 排序类
  • 快速排序：`sort()`
  • 优先队列：
• 数学函数`#include<cmath>`
• 数学基础
  • 高精度除法
  • 矩阵乘法
  • 欧拉函数
    • 1. 欧拉函数定义在整数上，不能先取模
• 一些函数或代码组合写法
  • 代码便捷写法
• 替换字符串里面所有特定子串`find()`+`replace()`
• 刷题心得
• 未完持续...

Dev-C++调试经验

环境配置

1. 视图栏下的项目管理和状态条打开
2. 工具->编译选项
   • ->编译器配置为TDM-GCC 4.9.2 64-bit Debug
   • ->代码生成->优化级别（-Ox)为Debug(g)
   • ->语言标准(-std)为ISO C++11
   • ->连接器->产生调试信息为Yes

Debug

• 一定要新建项目->选Console Application
• 先编译再调试
• 在步骤1，2做好了之后调试若出现点击下一步无效可能是以下原因之一（目前遇到并解决的）：
  ①黑框（控制台）等待输入数据，输入所需数据并按回车，调试才会继续
  ②若添加查看容器时，调试器试图去解析和显示这个容器的全部内部复杂结构（包括内存分配器、迭代器、容量、大小等信息），而不是直观地只显示你存放的数据 。这个解析过程在老旧的调试器中很容易陷入低效循环或直接卡死，导致你点击“下一步”无反应。
  ②的解决方案：
  1. 需要观察 ch 的地方，临时写几行代码，将其内容复制到一个普通数组中，然后观察这个数组
  2. 在一些循环或操作容器的代码下面直接临时输出cout容器的值

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()

intmain(){int num =123;// 右对齐（默认） cout <<"右对齐: |"<<setw(5)<< num <<"|"<< endl;// 输出：| 123|// 左对齐 cout <<"左对齐: |"<< left <<setw(5)<< num <<"|"<< endl;// 输出：|123 |// 内部填充（中间对齐） cout <<"内部对齐: |"<< internal <<setw(5)<< num <<"|"<< endl;// 输出：| 123|return0;}

不同类型数字的格式化setw()

注意： 格式化浮点数时宽度包含小数点"."

#include<iostream>#include<iomanip>usingnamespace std;intmain(){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+01return0;}

如果不熟悉或者忘记了就用传统C风格

intmain(){int num =123;// 使用printfprintf("|%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|return0;}

输出字段填充字符setfill()

头文件:#include<iomanip>
函数：setfill()

它的核心作用是与 setw() 配合使用：当输出的数据宽度不足 setw() 指定的宽度时，会用 setfill() 设置的字符填充空白部分。

#include<iomanip>// 必须包含此头文件intmain(){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-------- (右侧填充)return0;}

注意：

• 作用持久性：一旦设置 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()

intmain(){ string line;// 从标准输入读取一行getline(cin, line); cout << line << endl; cout <<"字符串长度: "<< line.length()<< endl;return0;}

注意：cin >> 后接 getline() 会立即返回空字符串，需要在 cin >> 后清除缓冲区cin.ignore()

cout <<"输入年龄: "; cin >> age;// 清除缓冲区中的换行符 cin.ignore(numeric_limits<streamsize>::max(),'\n');// 或者简单点：cin.ignore(); cout <<"输入姓名: ";getline(cin, name);// 现在会正常等待输入

字符串string

输入输出

字符串声明输入输出：

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

字符转换

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

intcharToValue(char ch){if(ch >='0'&& ch <='9'){return ch -'0';}elseif(ch >='A'&& ch <='F'){return ch -'A'+10;}elseif(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
基本用法：

intmain(){// 整数转字符串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;return0;}

字母大小写转换

头文件:#include<cctype>
函数：toupper(),tolower()

方式1： 使用C++11范围for循环

intmain(){ string str1 ="Hello World";// 转换为大写for(char&c : str1)c =toupper(c);// 转换为小写 string str2 ="HELLO WORLD";for(char&c : str2)c =tolower(c);return0;}

方式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(输入开始, 输入结束, 输出开始, 转换函数);

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

查找字符串特定元素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() 等函数配合使用

提取字符串特定元素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);

字符串替换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*

基本语法：

longlongstoll(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){longlong a =stoll(fraction.substr(0, pos));// 分子longlong 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}

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

两者的关键区别

算法函数#include<algorithm>

将所有特定值替换另一个值replace()

头文件:#include<algorithm>
函数：replace()
替换容器中所有等于某个值的元素为另一个值。
语法：

voidreplace(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

分配固定空间

创建包含10个整数的vector，所有元素初始化为0

#include<iostream>#include<vector>usingnamespace std;intmain(){// 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：可以传递引用，保留所有信息return0;}

如果对vector<int> vec(10);使用函数push_back(),那么vec会有11个元素

intmain(){// 创建一个包含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;// 11return0;}

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

STL容器

哈希表unordered_set

链接: C++ STL容器：unordered_set

排序类

快速排序：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>());

优先队列：

//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. 初始化

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>usingnamespace std;structDivisionResult{ 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;}intmain(){ string dividend ="123456";int divisor =789; DivisionResult* result=divide(dividend, divisor); cout<<"商: "<<result->quotient<<endl; cout<<"余数: "<<result->remainder<<endl;delete result;return0;}

矩阵乘法

定义：

矩阵乘法需要满足第一个矩阵的列数 = 第二个矩阵的行数。如果矩阵 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 C_{ij} = \sum_{k=1}^{n} A_{ik} \times B_{kj} Cij​=∑k=1n​Aik​×Bkj​

其中：

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

示例：

A =[123] B =[78][456][910][1112] 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 =[5864][139154]

代码示例： 已知矩阵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=p₁^k1✖p₂^k2✖ …✖p_n^km,p_i均为质数,k_i是其幂次
由此可推出欧拉函数的求法:Euler(n)=n/p₁✖(p₁-1)/p₂✖(p₂-1)/…/p_n✖(p_n-1)

模板如下：

longlongeuler_phi(ll n){longlong res = n;// 初始结果为 n// 试除质因数，i 从 2 到 sqrt(n)for(longlong 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. 欧拉函数定义在整数上，不能先取模

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

• a=2, b=3，则 a^b=8，( φ \varphi φ(8)=4。
• 若 MOD=5，(8 m o d \bmod mod 5 = 3)，( φ \varphi φ(3)=2)，显然 (4 ≠ \neq = 2)。

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

一些函数或代码组合写法

代码便捷写法

输入操作可以写成一行：

//输入：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;//0123456789int i=10;if(i==10)cout<<i<<endl;//10while(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

刷题心得

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 & 只是传递一个引用（相当于一个指针），所以对于大对象，性能差距巨大。

未完持续…