c++学习笔记（10）

1.

二分答案是一种常用的算法思想，用于解决一些需要枚举所有可能答案的问题。它的基本思想是将问题的答案范围缩小到一半，然后根据一定的条件判断，再将答案范围缩小到一半，直到找到正确的答案或者确定不存在正确答案为止。

下面以求解一个数的平方根为例，介绍二分答案的实现过程：

1. 首先，我们需要确定答案的范围。对于求解一个数的平方根，我们可以将答案范围设为[0, x]，其中x是待求的数。

2. 然后，我们需要定义一个函数来判断当前的答案是否满足要求。对于求解一个数的平方根，我们可以定义一个函数check(mid)，其中mid表示当前的答案，如果mid的平方小于等于x，则返回true，否则返回false。

3. 接下来，我们需要使用二分答案的思想来不断缩小答案范围。具体地，我们首先取答案范围的中间值mid=(l+r)/2，然后调用check(mid)函数来判断mid是否满足要求。如果满足要求，说明答案在[l, mid]范围内，因此我们将答案范围更新为[l, mid]；否则说明答案在[mid+1, r]范围内，因此我们将答案范围更新为[mid+1, r]。重复这个过程，直到找到正确的答案或者确定不存在正确答案为止。

下面是代码示例：

// 定义了一个findSqrt函数来求解一个数的平方根。
// 该函数接受一个参数x，表示待求的数。
// 在函数内部，使用二分答案的思想来不断缩小答案范围，直到找到正确的答案或者确定不存在正确答案为止。
// 最后，在主函数中读取输入数据并输出结果。#include <iostream>
using namespace std;bool check(double mid, double x) {return mid * mid <= x;
}double findSqrt(double x) {double l = 0, r = x;while (r - l > 1e-6) {double mid = (l + r) / 2;if (check(mid, x)) {l = mid;} else {r = mid;}}return l;
}int main() {double x;cin >> x;cout << findSqrt(x) << endl;return 0;
}

2.

向量数组（vector array）是一种数据结构，用于存储多个向量。在C++中，可以使用std::vector类来实现向量数组。

1. 定义向量数组：

   std::vector<int> arr[N];

   上述代码定义了一个名为arr的向量数组，其中每个元素都是一个整数类型的向量。

2. 添加元素到向量数组中的特定向量：

   arr[index].push_back(value);

   上述代码将值value添加到向量数组中索引为index的向量的末尾。

3. 访问向量数组中的特定向量的元素：

   int value = arr[index][position];

   上述代码获取向量数组中索引为index的向量中位置为position的元素的值，并将其赋给变量value。

4. 遍历向量数组中的向量：

   for (int i = 0; i < N; i++) 
   { for (int j = 0; j < arr[i].size(); j++) { // 处理arr[i][j]的逻辑 } 
   }

   上述代码使用两个嵌套的循环来遍历向量数组中的每个向量及其元素。外层循环控制向量的索引，内层循环控制向量中的元素位置。

5. 获取向量数组的大小：

   int size = arr.size();

   上述代码获取向量数组的大小，即包含的向量的数量。

6. 清空向量数组：

   arr.clear();

   上述代码清空整个向量数组，移除所有向量及其元素。

这些是关于C++中向量数组的基本操作和用法。通过使用向量数组，可以方便地管理和操作一组向量，实现灵活的数据存储和操作。

3.

bitset是C++标准库中的一个容器，用于处理固定大小的位序列。它可以用来存储和操作二进制数据，例如位标志、位掩码等。

1. 包含头文件：

   #include <bitset>

2. 定义bitset对象：

   std::bitset<N> bitset_variable;

   其中N是一个整数，表示bitset的大小，即可以存储的位数。

3. 初始化bitset对象：

   std::bitset<8> b1(0b11001100); // 使用二进制字面值初始化 
   std::bitset<8> b2("11001100"); // 使用字符串初始化

4. 访问bitset的元素：

   int index = 3; 
   bool value = bitset_variable[index]; // 获取索引为index的位的值 
   bitset_variable.set(index, true); // 将索引为index的位设置为true 
   bitset_variable.set(index, false); // 将索引为index的位设置为false

5. 对bitset进行位运算：

   std::bitset<8> b1(0b11001100); 
   std::bitset<8> b2(0b00111100); 
   b1 &= b2; // 按位与运算 
   b1 |= b2; // 按位或运算 
   b1 ^= b2; // 按位异或运算 
   b1 ~= b2; // 按位取反运算

6. 输出bitset的内容：

   std::cout << bitset_variable << std::endl; // 输出bitset的内容

这些是关于C++中bitset的基本操作和用法。通过使用bitset，可以方便地处理位级别的数据，执行位运算和位操作。

4.

拆位思想是一种常用的位运算技巧，它通过将一个整数的二进制表示拆分成多个部分，然后对每个部分进行独立的操作，最后再将结果合并起来。这种思想在处理一些复杂的位运算问题时非常有用。

• 将一个整数的二进制表示拆分成多个部分：

int num = 23; // 二进制表示为 00010111int part1 = (num >> 4) & 0xF; // 右移4位，得到 00000101int part2 = num & 0xF; // 与0xF进行按位与运算，得到 00000111

• 每个部分进行独立的操作：

int result1 = part1 + 1; // 结果为 5int result2 = part2 - 1; // 结果为 7

• 将结果合并起来：

int finalResult = (result1 << 4) | result2; // 左移4位，得到 00010100，与result2进行按位或运算，得到 00010111

在上述代码中，我们首先将整数num的二进制表示拆分成了两个部分part1和part2。然后，我们对每个部分进行了独立的操作，得到了result1和result2。最后，我们将这两个结果合并起来，得到了最终的结果finalResult。

需要注意的是，拆位思想并不是一种通用的算法，而是针对特定的问题而设计的。在使用拆位思想时，需要根据具体的问题来选择合适的拆分方式和操作方法。

5.

unsigned是C++中用于声明无符号整数类型的关键字。它表示一个非负的整数，其取值范围为0到2^n-1，其中n是该类型的位数。

#include <iostream> int main() { unsigned int num = 4294967295; // 最大的无符号整数 std::cout << "The maximum value of an unsigned int is: " << num << std::endl; return 0; 
}

需要注意的是，由于无符号整数没有符号位，因此它们的取值范围比有符号整数更大。但是，如果将无符号整数与有符号整数进行比较或运算，可能会导致意外的结果。因此，在使用无符号整数时，需要特别注意类型转换和溢出问题。

6.

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

以下是深度优先搜索的详细解析和代码示例：

1. 定义一个栈，用于存储待访问的节点。

2. 将起始节点压入栈中。

3. 当栈不为空时，弹出栈顶元素，访问该节点。

4. 将该节点的所有邻接节点压入栈中。

5. 重复步骤3和步骤4，直到栈为空。

以下是深度优先搜索的代码示例：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;// 定义了一个名为dfs的函数，用于实现深度优先搜索。
// 该函数接受三个参数：当前节点、图的邻接表表示和访问标记数组。
// 使用一个栈来存储待访问的节点，并将起始节点压入栈中。
// 然后，循环地弹出栈顶元素，访问该节点，并将其所有邻接节点压入栈中。
// 最后，输出所有被访问过的节点。void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {stack<int> s;s.push(node);while (!s.empty()) {int v = s.top();s.pop();if (!visited[v]) {cout << v << " ";visited[v] = true;for (int i = 0; i < graph[v].size(); i++) {if (!visited[graph[v][i]]) {s.push(graph[v][i]);}}}}
}int main() {vector<vector<int>> graph = {{1, 2}, {0, 3}, {0, 3, 4}, {1, 2}, {2}};vector<bool> visited(graph.size(), false);dfs(0, graph, visited);return 0;
}

7.

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在实际应用中，我们常常需要对搜索过程进行剪枝，以减少搜索空间和提高效率。剪枝是指在搜索过程中，对于一些不可能产生最优解的分支，直接放弃搜索，从而减少搜索空间。

以下是深度优先搜索剪枝的详细解析和代码示例：

1. 定义一个栈，用于存储待访问的节点。

2. 将起始节点压入栈中。

3. 当栈不为空时，弹出栈顶元素，访问该节点。

4. 判断该节点是否满足剪枝条件，如果满足，则跳过该节点，否则继续搜索。

5. 将该节点的所有邻接节点压入栈中。

6. 重复步骤3和步骤4，直到栈为空。

代码示例：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;bool isPruned(int node) {// 剪枝条件判断return false;
}void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {stack<int> s;s.push(node);while (!s.empty()) {int v = s.top();s.pop();if (!visited[v]) {cout << v << " ";visited[v] = true;for (int i = 0; i < graph[v].size(); i++) { // 判断当前节点是否满足剪枝条件，如果满足，则跳过该节点，否则继续搜索if (!visited[graph[v][i]] && !isPruned(graph[v][i])) {s.push(graph[v][i]);}}}}
}int main() {vector<vector<int>> graph = {{1, 2}, {0, 3}, {0, 3, 4}, {1, 2}, {2}};vector<bool> visited(graph.size(), false);dfs(0, graph, visited);return 0;
}