小技巧和易错点1

【动态规划】 动态规划是一种解决复杂问题的有效算法，它通过将大问题分解为小问题，然后逐个解决这些小问题来找到全局最优解。在动态规划中，我们通常使用一个数组`dp`来存储子问题的解。描述中提到的一个重要易错点是，在计算动态规划状态时，如果一个状态`dp[n]`已经被计算过，当你需要计算`dp[p+1]`时，不能直接使用`dp[n]`的结果，因为`dp[n]`代表的是1到n的值，而我们需要的是2到n+1的值。因此，必须确保在处理数组时正确地更新和使用动态规划的状态。 【指针操作】 指针是C/C++中非常关键的概念。`int *p = &a`表示`p`指向变量`a`的地址。对`p`赋值相当于改变`a`的值，而对`*p`赋值则意味着改变`p`所指向的位置的值。这一点在内存管理和函数参数传递中尤其重要。 【大数处理】 在处理大数时，应避免溢出。平均数计算应先除后加，防止中间结果过大。如果数值可能超出`int`的范围，应使用`long long int`类型。另外，求大数的模运算可以先对每个数分别求模再相乘，减少计算量。 【字符串处理】 字符串在C语言中分为`char[]`和`std::string`两种类型。`cstring`库中的函数主要适用于`char[]`，而`std::string`具有更丰富的操作方法。字符'0'可以打印，但数字0不行，字符串输出到'0'时会自动结束。`string`可以进行直接连接操作，而`char[]`则需要使用`strcpy`和`strcmp`。 【运算优先级和位操作】 在编程中，运算符的优先级很重要。例如，`i++`先执行操作，然后自增，而`++i`则是先自增再执行操作。位操作如位移`<<`和`>>`用于快速的乘除2，位异或`^`可用于计算二进制数的补码。 【递归与复杂度】 递归算法常常用来解决问题的子结构。递归的时间复杂度可以通过分析递归树或者观察状态的计算次数来确定。例如，一个状态到下一个状态加上中间的代价就构成了递归的基本操作。 【快速幂】 快速幂算法是一种高效的计算幂次的算法，通过每次将指数减半并平方底数，可以显著减少计算次数。在处理大数乘法时尤其有用，避免了重复的乘法操作。 【其他技巧】 - 计算对数时，默认是自然对数`ln`，若需要以10为底，应使用`log10`。 - `#include "xxx.h"`用于包含头文件，其中的内容会被复制到当前文件。 - `extern`关键字用于声明在其他文件中定义的变量。 - 上取整可以用`(a+b-1)/b`来实现。 - 广度优先搜索(BFS)通常用于寻找最短路径或最小步骤，利用队列进行操作。 - 大数求余运算可以通过先求模再相乘来减少计算量。 - 位操作可以用于高效地获取大数的特定部分。 以上知识点涵盖了动态规划、指针、大数处理、字符串操作、递归、复杂度分析、快速幂等核心概念，它们都是编程中常见的问题和技巧。理解并熟练运用这些知识点，对于提升编程能力非常有帮助。