学习记录：算法与 C++（2024年11月 - 2025年12月)

Note
This study plan was generated with the assistance of ChatGPT. Special thanks to ChatGPT for providing valuable guidance!
For more information, visit OpenAI ChatGPT.

C++ 基础语法

范围for循环

for (auto x:v){cout<<x<<"\n";}

explansion

auto 的作用是让编译器自动推导 x 的类型,使代码更简洁灵活.
以上循环为拷贝操作,若要修改容器元素,需要使用引用&. 如果还想避免意外改动,还可以再加上const

`srting`数据类型

本质容器

获取长度: size()和length()完全等价,看从什么角度看待罢了. 前者容器,后者字符串.
获取首尾字符(char类型): front(), back() (需检查字符串不为空!empty()) or 通过数组索引; removes the last element:pop_back()
string greet="senbai,ciallo~";
string s1=greet.substr(7);//ciallo~
string s2=greet.substr(7,6);//ciallo
greet.pop_back();//senbai,ciallo

转化为字符串: to_string()

在拼接字符串时经常用到,尽管在拼接char和string时会隐式转换为string类型,但其它情况可能会出现意料之外的结果.
范围大小写转换(#include<algorithm><cctype>):
transtorm(str.begin(),str.end(),str.begin(),::toupper);
第三个参数为迭代器(类指针),transform函数被设计为面向范围操作. STL 的函数设计基于迭代器，使操作可扩展和高效.

toupper位于全局命名空间(不在std!!),需要显式地加上作用域解析符 ::,避免冲突发生.

冒泡优化

//improve
bool swapped;
for (int i=0;i<n;i++){
	swapped=false;
	for (int j=0;j<n;j++){
		if(s[j]>s[j+1]) swap(s[j],s[j+1]);
		swapped=true;
	}
	if (!swapped) break;
}

使用 swapped 标志位，检测是否发生了交换。如果某次内循环没有交换，说明数组已经有序，可以提前退出外层循环，避免不必要的操作. 可以看出冒泡的教学意义,但真到要排序的时候,还是用sort函数.

string to int

其他数据类型转化为string类型时可以使用to_string()函数,但字符型转化为整型呢? 利用ASCII 编码 的性质,进行ch - '0'运算时,字符会隐式地被转换为它们对应的 ASCII 值，并进行整数运算。这在处理字符串和数字的混合数据时非常有用.

e.g.将string类型字符串转换为整型十进制数.

//将一个字符串转化为十进制整数
#include <bits/stdc++.h>
using namespace std;
int main() {
    string ch_number="114514";
    int number = 0;
    for (char ch : ch_number) {//在循环中实现累乘
        number = number * 10 + (ch - '0');
    }
    cout<<number;
    return 0;
}

好啦,现在你获得了一个可以用于数学计算的数字!

Math

(较)精确的pi

#include <cmath>
const double pi=acos(-1.0);

十的六次方表示为1e6

STL

set

基于二叉树,适合需要查找,插入和删除操作的场合,均在O(log n)时间内完成.

```



### 格式化输出

保留指定位小数

```c++
#include <iomanip>// std::fixed, std::setprecision
cout<<fixed<<setprecision(n);//保留n位小数.

std::fixed：设置浮点数的表示方式为定点表示（即小数形式，而非科学计数法）.如果没有 std::fixed，std::setprecision 会影响数字的总有效位数.
流操控符的设置会一直影响之后的输出，直到被重新设置或流被刷新。
//使用完后重置格式
cout.unsetf(ios::fixed);

因为setprecision(设置精度)实在是有点难记,还是用printf罢

6.阶乘的各种实现方法

递归:n!=n×(n−1)!

long long factor(int n){
    if (n==0||n==1) return 1;
    return n*factor(n-1);
}

//使用尾递归优化
long long factorialTail(int n, long long result = 1) {
    if (n == 0 || n == 1)
        return result;
    return factorialTail(n - 1, n * result); // 尾递归调用
}

7.获取两个变量中的较小(大)值

三元表达式
for (int i=1;i<=(s1<s2?s1:s2);i++)
min(),max()
for (int i=1;i<=min(s1,s2);i++)

8.快捷头文件

#include <bits/stdc++.h>

包含所有常用的 C++ 标准库头文件，从而不用单独导入每个需要的头文件。

bits/stdc++.h 是 GCC 专用，并不是 C++ 标准的一部分，因此可能无法在非 GCC 编译器（如 MSVC、Clang）上运行。

9.shortening code

//shortening code by Macros
#define ll long long
//or by typedef
typedef long long ll

11.获取保留空格的字符串

getline(cin,name);

小结：
复习并总结控制结构和数组操作，记录遇到的难点。

第 2 周：函数与输入输出优化

结构体

考虑一个问题:求三角形的周长

可以想象dx,dy不容易通过循环得到,从而需要定义很多变量,且调用函数也不方便.最重要的是难以复用.能不能方便地得到它们呢?

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

struct point{
    double x,y;
};
struct Tr{
    point p1,p2,p3;
    double getlen(point& a,point& b){
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    double getresult(){
        return getlen(p1,p2)+getlen(p1,p3)+getlen(p3,p2);
    }

};

int main(){
    Tr tri;
    cin>>tri.p1.x>>tri.p1.y>>tri.p2.x
    >>tri.p2.y>>tri.p3.x>>tri.p3.y;
    
    double result=tri.getresult();
    cout<<fixed<<setprecision(2);
    cout<<result;
    return 0;
}

通过结构体,将三角形及其顶点封装在其中,方便重复调用.STL 中的容器、算法、迭代器等都依赖于这种封装性和可复用性。这种风格不仅能让代码更简洁，还提高了可维护性和扩展性，让代码看起来更模块化、更具可读性。

vector容器预先分配空间

由vector容器的动态增加原理,在处理大量输入时会导致庞大的内存开销.

解决:预先分配空间(Pre-allocating space)

cin>>n;
vector<int> numbers(n);
for (int i=0;i<n;i++) cin>>numbers[i];

Optimize Input/Output for faster I/O

ios::sync_with_stdio(false);
cin.tie(nullptr);// Disable synchronization

FAQ

溢出和精度

棋盘中的矩阵

Fact:对于一个n*m规格的棋盘,其包含的矩阵数量为

$\text{Total Rectangles} = \binom{2n+1}{2} \times \binom{2m+1}{2}$

unsigned long long rectNum(int m,int n){
    return (1ULL*(n+1)*(m+1)*m*n)/4-sqrNum(m,n);
}

Why?

For rectangles, any subgrid defined by two distinct horizontal lines and two distinct vertical lines forms a rectangle.

所以,原问题便转化为组合问题.

1.溢出问题

这里的乘法 (n+1)*(m+1)*m*n 可能会在乘法过程中溢出，因为所有乘法在计算时仍然会使用普通整型规则进行中间计算。因此，即使结果存储在 unsigned long long 中，可能已经溢出了。

solve:使用 1ULL 强制转换为 unsigned long long

In C++, when you multiply two integers, the multiplication happens with the type of the operands. If both operands are int (typically 32 bits), the result will also be treated as an int, even if it’s stored in a larger type later.

Here, 1ULL forces the multiplication to be done in unsigned long long space, avoiding overflow.

It’s a common practice when dealing with large numbers or potential overflow in C++ arithmetic.

(Generated by ChatGPT 4o)

2.在(n+1)*(m+1)*m*n中肯定存在两个偶数项，确保了结果总能被 4 整除,因此，整数除法的精度问题在这里不存在。

结构体还是函数?

结构体（或类）主要用于将多个相关变量组合在一起，表示一个逻辑实体。非常适合以下场景：

多个变量需要频繁一起使用，且这些变量之间有逻辑关系（如 point 包含 x 和 y）。
操作多样化：结构体可以包含成员函数，对数据进行封装和操作。
数据共享与存储：多个实例表示不同的数据组时，如存储多个矩形板的信息。

函数更适合以下情况：

参与计算的变量数量较少，且这些变量没有内在的关联关系（如纯数学计算）。
一次性操作或逻辑简单：函数只做某一特定任务，不需要保存状态。
独立计算逻辑：函数可以被独立调用，不依赖结构体的成员变量。

总之, 变量数量和关联性是决定使用结构体还是函数的重要因素。结构体适合将相关数据和操作封装在一起，函数适合独立、简单的计算逻辑。

std::sort的比较函数

通过比较出生日期对通讯录进行排序

struct date{
    int y,m,d;
};
struct pb{
    char name;
    date bir;
    string num;
};
bool prepare(const pb& a, const pb& b){//const防止意外修改,&避免拷贝
    if (a.bir.y!=b.bir.y){
        return a.bir.y<b.bir.y;
    }
    if (a.bir.m!=b.bir.m){
        return a.bir.m<b.bir.m;
    }
    return a.bir.d<b.bir.d;
}

提问:为什么不是返回a.bir<b.bir?这可以吗?

std::sort 需要一个具体的比较函数来比较两个 pb 结构体的内容。要

简化逻辑,可以在结构体pb中重载 operator<

//修改pb
struct date {
    int y, m, d;
    
    // 重载 operator< 用于比较日期
    bool operator<(const date& other) const {
        if (y != other.y) {
            return y < other.y;
        }
        if (m != other.m) {
            return m < other.m;
        }
        return d < other.d;
    }
};

重载是什么?

C++基础