CCF算法笔记

本篇笔记是本人复习CCF-CSP考试的过程中编写的，方便复习与巩固。

C/C++算法

C++string判断大小写以及数字

可以使用C++中的isupper()、islower()和isdigit()函数来判断字符串中的大小写字母和数字。

可以使用isalpha()函数判断是否为字母。

isalpha()、isupper()、islower()和isdigit()函数的返回值都是bool型。

C++ erase()函数

erase()函数可以用于以下类型的容器：string、vector、list、deque、set、map等。

std::vector 的 erase 函数可以用来从向量中删除一个或多个元素。该函数有两种重载形式：

1. 通过位置删除元素

   iterator erase (const_iterator position);
   iterator erase (const_iterator first, const_iterator last);

   第一种形式用于删除一个单独的元素，该元素由迭代器 position 指定。这将使其后面的所有元素向前移动一个位置，并且向量的大小会减小1。

   第二种形式用于删除一系列连续的元素，这些元素被迭代器对 [first, last) 区间指定。这将使所有在删除范围之后的元素向前移动，并且向量的大小会减小删除的元素数量。

2. 通过值删除元素

   iterator erase (const T& value);

   这个版本的 erase 用于删除向量中的所有等于给定值 value 的元素。它返回一个迭代器，指向被删除元素的下一个位置。

需要注意的是，这些函数只适用于可变的（即非常量）向量。

C++ unique()函数

C++ STL中的unique()函数是一个常用的算法，用于删除容器中相邻的重复元素。它接受两个迭代器表示容器范围，并返回一个指向新末尾的迭代器（也就是最后一个不重复元素的下一个位置），该迭代器之前的所有元素都是唯一的。

unique()函数的语法如下：

template <class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last);

template <class ForwardIt, class BinaryPredicate>
ForwardIt unique(ForwardIt first, ForwardIt last, BinaryPredicate p);

其中，参数first和last指定了要处理的容器中的元素范围；p是一个可选的二元谓词，用于比较两个元素是否相等。如果省略了第二个参数，则默认使用operator==进行比较。

unique()函数的基本思想是：遍历容器中的每一个元素，将它与前一个元素进行比较。如果它们相等，就将后一个元素删除，并继续往后比较，直到找到不相等的元素为止。这样遍历整个容器，最后得到的就是一个没有相邻重复元素的新容器。

C++ equel_range()函数

equel_range() 函数定义在<algorithm>头文件中，用于在指定范围内查找等于目标值的所有元素。

返回值

该函数会返回一个 pair 类型值，其包含 2 个正向迭代器。

当查找成功时：

1. 第 1 个迭代器指向的是 [first, last) 区域中第一个等于 val 的元素；

2. 第 2 个迭代器指向的是 [first, last) 区域中第一个大于 val 的元素。

反之如果查找失败，则这 2 个迭代器要么都指向大于 val 的第一个元素（如果有），要么都和 last 迭代器指向相同。

特点

1. map、multimap、unordered_map的equel_range()都是查找的key，或者说是.first;

注：

• equal_range.first和lower_bound返回值是一样的，都是指向第一个相等元素（可以这样认为）的迭代器，无论最后找到或者找不到匹配的关键字，它们都相等。
• 同理，equal_range.second和upper_bound的返回值一样，都是指向最后一个相等元素的后一个元素的迭代器，如果找不到关键字，那么将会得到一个安全的关键字插入位置。

C++迭代器（STL迭代器）iterator

定义

迭代器按照定义方式分成以下四种。

\1) 正向迭代器，定义方法如下：

容器类名::iterator 迭代器名;

\2) 常量正向迭代器，定义方法如下：

容器类名::const_iterator 迭代器名;

\3) 反向迭代器，定义方法如下：

容器类名::reverse_iterator 迭代器名;

\4) 常量反向迭代器，定义方法如下：

容器类名::const_reverse_iterator 迭代器名;

用法

通过迭代器可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。

迭代器都可以进行++操作。反向迭代器和正向迭代器的区别在于：

• 对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素；

• 而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v;  //v是存放int类型变量的可变长数组，开始时没有元素
    for (int n = 0; n<5; ++n)
        v.push_back(n);  //push_back成员函数在vector容器尾部添加一个元素
    vector<int>::iterator i;  //定义正向迭代器
    for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍历容器——end成员函数返回的不是指向最后一个元素的迭代器，而是指向最后一个元素后面的位置的迭代器
        cout << *i << " ";  //*i 就是迭代器i指向的元素
        *i *= 2;  //每个元素变为原来的2倍
    }
    cout << endl;
    //用反向迭代器遍历容器
    for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
        cout << *j << " ";
    return 0;
}
//rbegin成员函数返回指向容器中最后一个元素的迭代器，rend成员函数返回指向容器中第一个元素前面的位置的迭代器

输出结果：

程序的输出结果是：
0 1 2 3 4
8 6 4 2 0

C++begin()和end()容器⭐️

参考：C++ STL begin()和end()函数用法 (biancheng.net)

begin()和end()容器：

1. 可以对向量、集合、map……等有用；

2. 也对数组有相同的作用；

   • 将指定数组传给 begin() 函数，其会返回一个指向该数组首个元素的指针；将指定数组传给 end() 函数，其会返回一个指向数组中最后一个元素之后位置的指针。

C++set容器

set.count(type target)

计算目标值的个数

C++数组

定义数组作形参的函数

静态数组作参数：

//第一种——对数组的引用
double convert_matrix(double (&M)[8][8],int i,int j){
	//函数体
}
//第二种——数组传值
double convert_matrix(double M[][8],int i,int j){
	//函数体
}
//第三种——数组传值
double convert_matrix(double M[8][8],int i,int j){
	//函数体
}

动态数组作参数：

#include<bits/stdc++.h>
using namespace std;

int N;
int counts = 0;// 计数

int N_queens(int i, vector<vector<int>>&M, int col[], int L[], int R[]){// 动态数组作参数
    // 实现代码
	return counts;
}

int main() {
	cin>>N;
	vector<vector<int>>M(N, vector<int>(N, 0));// 采用int M[N][N]，不方便给函数传参，这里要用vector动态数组 
	int col[N]={0}, L[2*N]={0}, R[2*N]={0};// 1则表明存储皇后 
	int n = N_queens(0, M, col, L, R);
	cout<<n;// 可行解数量 
	return 0;
}

C++获取数组长度（元素个数）

在 C++ 中，可以通过以下两种方式来获取数组的长度：

1. 使用 sizeof 操作符

使用 sizeof 操作符可以返回数组所占用的总字节数，除以每个元素所占用的字节数即可得到数组的长度。例如：

int arr[] = {1, 2, 3, 4, 5};
int len = sizeof(arr) / sizeof(arr[0]);

其中，sizeof(arr) 返回整个数组占用的字节数，sizeof(arr[0]) 返回数组中第一个元素所占用的字节数。因此，sizeof(arr) / sizeof(arr[0]) 即为数组的长度。

2. 使用模板函数

C++11 引入了 std::extent 模板函数，可以直接获取数组的长度。例如：

int arr[] = {1, 2, 3, 4, 5};
int len = std::extent<decltype(arr)>::value;

其中，decltype(arr) 返回数组类型，std::extent<decltype(arr)>::value 返回数组的长度。

数学算法

向量的内积和叉乘

内积

叉乘

欧几里得算法

gcd(a,b) = gcd(b,a mod b)

形象记忆：

a % b = c
	b % c = d
		c % d = e
			d % e = f
				......

欧几里得算法拓展：

参考：(77条消息) 扩展欧几里得算法超详解_Aloof__的博客-CSDN博客_扩展欧几里得原理

给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)

1=(-7)*47+(11)*30


gcd(a,b)可以表示为a,b的整洗数线性组合，例如：gcd(6,14)=2,而2=(-2)*6+1*14.

绝对值函数abs()

实例：

#include <iostream>
#include<cmath>//C语言是math.h
 
using namespace std;
void main(void)
{
	int a=1,b=10;
	float c=1,d=10;
	double e=1,f=10;
 
	cout<<"b-a="<<abs(b-a)<<endl;
	cout<<"c-d="<<abs(c-d)<<endl;
	cout<<"e-f="<<abs(e-f)<<endl;
	cin.get();
}

//输出：
b-a=9
c-d=9
e-f=9

C++实现四舍五入的几种方法

参考：(101条消息) C实现四舍五入的几种方法_c四舍五入_Xaiver_97的博客-CSDN博客

1. 函数round()实现四舍五入

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  double a = 1.4999999;
  double b = 1.5000001;
  double n_a = -1.4999999;    
  double n_b = -1.5000001; 
  cout << round(a) << endl;    // 1
  cout << round(b) << endl;    // 2
  cout << round(n_a) << endl;    // -1
  cout << round(n_b) << endl;    // -2
  return 0;
}

round()函数原理为：x=(int)(x+0.5)公式，故可以自己写出round()函数：

#include<stdio.h>

double round(double x)
{
	return (int)(x+0.5);
}

Fisher-Yates 洗牌算法

可以参考：Fisher-Yates洗牌算法！来自算法理论的创始人！ - 知乎 (zhihu.com)

正向洗牌与反向洗牌算法：

vector<int> shuffle() {
    if (origin.empty()) return {};
    vector<int> shuffled(origin);
    int n = origin.size();
// 可以使用反向或者正向洗牌，效果相同。
// 反向洗牌：
    for (int i = n - 1; i >= 0; --i) {
        swap(shuffled[i], shuffled[rand() % (i + 1)]);
    }
// 正向洗牌：
// for (int i = 0; i < n; ++i) {
// int pos = rand() % (n - i);
// swap(shuffled[i], shuffled[i+pos]);
// }
	return shuffled;
}

Knuth-Morris-Pratt（KMP）算法

参考：KMP算法 - 维基百科，自由的百科全书 (wikipedia.org)

C++位运算及其应用

C++ 异或运算及其应用

前置知识：

1.一个整数自己跟自己异或，结果为0。//因为异或的法则为，相同为0，不同为1，注意这里所说的都是二进制位。

2.任意一个整数跟0异或，结果为本身。//因为1异或0得1,0异或0,得0，所以1还是1,0还是0，没发生变化。

通过异或运算不用临时变量的情况下进行两个变量的值交换。

示例：

C++编程技巧

关闭C++与C之间标准输入输出之间的同步，提升效率

在C中，ios::sync_with_stdio(false);是一条语句，用于关闭C标准库输入输出与C标准库输入输出之间的同步，从而提高程序的输入输出效率。默认情况下，C++标准库与C标准库之间会进行缓冲区同步，这会导致程序在读入或输出数据时的速度较慢。

当你需要在C中进行大量的输入输出操作时，特别是对时间敏感的代码，使用该语句可以显著提升程序的运行速度。但是要注意的是，在关闭同步后，就不能再同时使用cin和scanf等函数了，因为它们分别属于不同的输入输出流，并且不同输入输出流之间可能会发生数据竞争问题。所以在关闭同步之后，应该只使用C标准库的输入输出函数，比如cout和cin。