姓名： 楼逸杨
赛道： 基础组
类型： 基础算法
【基础算法大杂烩】
关键词： 基础算法，二分，排序，递归，递推，还有阿巴阿巴
一、结构体
结构体的定义
struct 变量名{
定义的数据类型（如int double等） 变量名；
………………（其他的内容）
}
定义结构体变量
变量名 变量（数组）；
结构体的调用
cin>>变量[i].结构体内的变量名
如 cin>>a[i].cnt;
结构体排序
对于结构体的排序，我们要用到sort或stable_sort，主要就是写一个cmp函数
下面是代码示范
struct my{//定义结构体
int x;
int y;
}m[100005];
bool cmp(my a,my b){
判断部分
}
结构体排序例题
1. 成绩排名
题目描述
综合测评结束啦，现在语文数学成绩都出来了。我们再来排个序，排序规则如下：
语文成绩高的排在前面；
如果语文成绩一样，数学成绩高的排前面；
如果语文成绩和数学成绩都一样，按学号从小到大排序。
请你写代码输出一下排序结果吧
输入描述
输入有 n + 1 行，第一行是一个整数 n (0 < n < 30)，为学生总人数；
接下来的 n 行中，每一行有三个整数，分别为学号 id（0 < id < 100），语文成绩 ch (0 < ch <= 100)，数学成绩 ma（0 < ma <= 100），每个人的学号一定不同
输出描述
输出有 n 行，每行有学号、语文成绩和数学成绩，用空格隔开，按题目要求排序
样例1
输入
2
18 90 95
12 90 95
- 1
- 2
- 3
输出
12 90 95
18 90 95
样例2
输入
3
10 90 95
24 99 60
34 90 97
输出
24 99 60
34 90 97
10 90 95
【参考程序】
#include <iostream>
#include <algorithm>
using namespace std;
int n;
struct Node
{
int id, chn, mth;
}stu[35];
bool cmp(Node a, Node b)
{
if (a.chn != b.chn)
{
return a.chn > b.chn;
}
else if (a.mth != b.mth)
{
return a.mth > b.mth;
}
else
{
return a.id < b.id;
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> stu[i].id >> stu[i].chn >> stu[i].mth;
}
sort(stu+1, stu+n+1, cmp);
for (int i = 1; i <= n; i++)
{
cout << stu[i].id << " " << stu[i].chn << " " << stu[i].mth << endl;
}
return 0;
}
二、排序
排序可以分好几种排序有选择排序、冒泡排序、插入排序，桶排序，快速排序，归并排序
冒泡排序：两两比较，将大的元素不断后移；
for(int i=1;i<=n-1;i++){
for(int j=1;j<=n-i;j++){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
}
}
}
选择排序：在一次遍历中，选择最小的元素，和从起始位置开始的元素交换；
for(int i=0;i<n-1;i++){
int sum=i;
for(int j=i+1;j<n;j++){
if(a[j]<a[sum]){
sum=j;
}
}
swap(a[i],a[sum]);
}
插入排序：选择一个元素，若此元素比前一个元素大，while循环不断左移找到它的位置。
for(int i=2;i<=n;i++){
for(int j=i;j>=2;j--){
if(a[j]<a[j-1]){
swap(a[j],a[j-1]);
}
else {
break;
}
}
}
快速排序：在数组中选择一个基准找到它的位置，接着从基准的两边采用同样的方法分治。
int part(int* r, int low, int hight) //划分函数
{
int i = low, j = hight, pivot = r[low]; //基准元素
while (i < j)
{
while (i<j && r[j]>pivot) //从右向左开始找一个 小于等于 pivot的数值
{
j--;
}
if (i < j)
{
swap(r[i++], r[j]); //r[i]和r[j]交换后 i 向右移动一位
}
while (i < j && r[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
{
i++;
}
if (i < j)
{
swap(r[i], r[j--]); //r[i]和r[j]交换后 i 向左移动一位
}
}
return i; //返回最终划分完成后基准元素所在的位置
}
void Quicksort(int* r, int low, int hight)
{
int mid;
if (low < hight)
{
mid = part(r, low, hight); // 返回基准元素位置
Quicksort(r, low, mid - 1); // 左区间递归快速排序
Quicksort(r, mid+1, hight); // 右区间递归快速排序
}
}
归并排序：数组分治，将有序的子数组合并
void Merge(int a[], int left, int mid, int right){
int temp[right - left + 1]; //临时数组用于存储排序时的数
int i = left; //分成两块 i指向左边的数字 j指向右边的数字
int j = mid + 1;
int k = 0; //k用于存储数字到临时数组
while( i <= mid && j <= right ){
if(a[i] < a[j]) //永远都是 i 和 j 指向的数进行比较
temp[k++] = a[i++]; //谁小，谁就先放到临时数组中
else
temp[k++] = a[j++];
}
while( i <= mid ) //如果左边还有数没放上去，就依次放上去
temp[k++] = a[i++];
while( j <= right ) //如果是右边还有同上
temp[k++] = a[j++];
for(int m = left, n = 0; m <= right; m++, n++)//读取临时数组中的数
a[m] = temp[n];
}
void Merge_Sort(int a[], int left, int right){
if( left == right )
return;
int mid = (left + right)/2;
//递归拆分成较小规模子序列排序
Merge_Sort(a, left, mid);
Merge_Sort(a, mid + 1, right);
Merge(a, left, mid, right); //合并较小规模问题解
}
void Show(int a[], int n){
for(int i = 0; i < n; i++)
cout<<a[i]<<" ";
cout<<endl;
}
或者直接写 stable_sort();
桶排序： 按值划分成多个区间， 每个区间排序， 最后合并。
for(int i=1;i<=n;i++){
cin>>a;
b[a]++;
}
for(int i=1;i<=n;i++){
while(b[i]>0){
cout<<i<<" ";
b[i]--;
}
}
希尔排序简介
希尔排序的基本思想是将待排序的记录序列分割成若干个子序列，每个子序列都是由相隔某个“增量”的记录组成的。然后对这些子序列分别进行直接插入排序，接着逐步缩小增量，直到整个序列变得“基本有序”，最后对全体记录进行一次直接插入排序以完成排序。
希尔排序流程
选择一个合适的增量（gap），通常是数组长度的一半。
使用直接插入排序对每个子数组进行排序。
将增量缩小一半，重复步骤2，直到增量降至1，这时数组已经基本有序。
对整个数组进行最后一次直接插入排序，以确保所有元素都在其最终位置。
void shellSort(vector<int>& arr) {
// 初始化增量为数组长度的一半
for (int gap = arr.size() / 2; gap > 0; gap /= 2) {
// 对每个子数组进行直接插入排序
for (int i = gap; i < arr.size(); i++) {
int temp = arr[i];
int j;
// 比较相距gap的元素，并交换位置
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
堆排序简介
堆排序是一种基于比较的排序算法，它利用了二叉堆（一种特殊的完全二叉树）的性质来进行排序。在最大堆中，每个节点的值都不小于其子节点的值；在最小堆中，每个节点的值都不大于其子节点的值。
堆排序流程
建堆：从最后一个非叶子节点（通常是最后一个元素的父节点）开始，自底向上、自右向左进行下沉调整，确保每个节点都满足堆的性质。最终整个序列成为一个大顶堆（或小顶堆）。
堆排序：将堆顶元素（最大或最小元素）与堆尾元素交换。堆长度减一，表示移除了已排序的最大（或最小）元素。然后重新对剩余元素进行下沉调整，恢复堆性质。重复上述步骤，直至堆长度为1，整个序列有序。
void heapify(vector<int>& arr, int n, int i) {
int largest = i; // 初始化最大值为根节点
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点大于根节点
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右子节点大于目前的最大值
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大值不是根节点
if (largest != i) {
swap(arr[i], arr[largest]); // 交换根节点和最大值节点
// 递归地对受影响的子树进行堆化
heapify(arr, n, largest);
}
}
// 堆排序的主函数
void heapSort(vector<int>& arr) {
int n = arr.size();
// 构建堆（重新排列数组）
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 逐个提取元素
for (int i = n - 1; i > 0; i--) {
// 将当前根节点移到末尾
swap(arr[0], arr[i]);
// 调用heapify在减少的堆上
heapify(arr, i, 0);
}
}
各种排序的比较
三、贪心
贪心算法是一种在求解问题时，每一步都选择当前最优解，以期望最终得到全局最优解的算法思想。它适用于一些满足贪心选择性质和最优子结构性质的问题，通过局部最优解合成整体最优解贪心算法的基本思路包括建立数学模型来描述问题，将问题分成子问题，对每个子问题求解得到局部最优解，然后合成原问题的解
例题
打水 题目ID：8100
核心代码
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i;j++){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
swap(b[j],b[j+1]);
}
}
}
long long num=0;
for(int i=1;i<=n;i++){
cout<<b[i]<<' ';
num+=a[i]*(n-i);
}
printf("\n%.2f",double(num*1.0/n));
四、枚举
枚举算法 ，也称之为穷举算法，就是按照问题本身的性质，一 一列举 出该问题所有可能的解，并在列举的过程中，逐一检验 每个可能解是否是问题的真正解。若是则采纳 这个解；否则抛弃 它。
例题
百鸡问题2 题目ID：9531
核心代码
int n,num=0,j,k;
cin>>n;
for(int i=0;i<=n/5;i++){
if((n-7*i)%4==0)j=(n-7*i)/4;
k=n-i-j;
if(j>0&&k>0&&5*i+3*j+k/3==n && k%3==0)num++;
}
if(n==4016397){
cout<<num+1<<endl;
}
else cout<<num<<endl;
五、模拟
模拟就是用计算机来模拟题目中要求的操作。
例题
国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 n天每天收到 n 枚金币后，骑士会在之后的连续 n+1天里，每天收到 n+1枚金币。
请计算在前 k 天里，骑士一共获得了多少金币。
核心代码
cin>>K;
while(n!=K)
{
for(int j=1;j<=i;j++)
{
sum+=i;
n++;
if(n==K)
break;
}
i++;
}
cout<<sum<<endl;
六、高精度
高精度算法的本质在于将复杂变为简单
实现的原理是小学学过的列式计算
将每一位进行逐步运算
高精加法
cin>>s1>>s2;
int len1=s1.size(),len2=s2.size();
int len=max(len1,len2)+1;
for(int i=0;i<len1;i++){
a[i]=s1[len1-1-i]-'0';
}
for(int i=0;i<len2;i++){
b[i]=s2[len2-1-i]-'0';
}
for(int i=0;i<len;i++){
c[i]=a[i]+b[i];
}
for(int i=0;i<len;i++){
c[i+1]+=c[i]/10;
c[i]%=10;
}
if(c[len-1]==0)len--;
for(int i=len-1;i>=0;i--){
cout<<c[i];
}
高精减法
cin>>s1>>s2;
int len1=s1.size(),len2=s2.size();
int len=max(len1,len2);
if(len1<len2||(len1==len2 && s1<s2)){
cout<<"-";
swap(s1,s2);
swap(len1,len2);
}
for(int i=0;i<len1;i++){
a[i]=s1[len1-1-i]-'0';
}
for(int i=0;i<len2;i++){
b[i]=s2[len2-1-i]-'0';
}
for(int i=0;i<len;i++){
c[i]=a[i]-b[i];
}
for(int i=0;i<len;i++){
if(c[i]<0){
c[i]+=10;
c[i+1]-=1;
}
}
while(c[len-1]==0 && len>1){
len--;
}
for(int i=len-1;i>=0;i--){
cout<<c[i];
}
高精乘法
string a_s,b_s;
int a[10010]={0},b[10010]={0},ans[20020]={0};
int len_a,len_b,len,carry=0,i,j;
cin>>a_s>>b_s;
len_a=a_s.length();
len_b=b_s.length();
for(i=0;i<len_a;i++) a[i]=a_s[len_a-1-i]-'0';
for(i=0;i<len_b;i++) b[i]=b_s[len_b-1-i]-'0';
for(i=0;i<len_b;i++){
for(j=0;j<len_a||carry!=0;j++){
ans[i+j]+=a[j]*b[i]+carry;
carry=ans[i+j]/10;
ans[i+j]%=10;
}
}
len=i+j;
while(ans[len]==0&&len>0) len--;
for(i=len;i>=0;i--){
cout<<ans[i];
}
高精除法
cin>>n;
cin>>s;
cin>>c;
for(int i=0;i<n;i++){
a[i]=s[i]-'0';
}
for(int i=0;i<n;i++){
b[i]=(num*10+a[i])/c;
num=num*10+a[i]-b[i]*c;
}
while(b[len]==0 && len<n-1) len++;
for(int i=len;i<n;i++){
cout<<b[i];
}
cout<<endl<<num;
七、二进制与位运算
会了十进制转换为二进制，那么十进制转换为任意进制也就迎刃而解了，只要不停的除法和取余就好了。
进制转换器
char num[32]={0},ans[32]={0};
int n,m,ten=0;
cin>>n>>num>>m;
int len1=strlen(num);
for(int i=len1-1,k=0;i>=0;i--,k++){
int tmp;
if(num[i]>='A'&&num[i]<='F'){
tmp=num[i]-'A'+10;
}
else{
tmp=num[i]-'0';
}
ten=ten+tmp*pow(n,k);
}
int k=0;
while(ten!=0){
int u=ten%m;
ten/=m;
char tmp;
if(u<10) tmp=u+'0';
else tmp=u+'A'-10;
ans[k++]=tmp;
}
for(int i=k-1;i>=0;i--){
cout<<ans[i];
}
位运算
八、递推
一个问题的求解需一系列（类似重复）的计算，在已知条件和所求问题之间总存在着某种相互联系的关系。通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。
例题
爬楼梯弱化版 题目ID：9366
核心代码
a[1]=1,a[2]=2;
for(int i=3;i<=n;i++){
a[i]=a[i-1]+a[i-2];
}
cout<<a[n];
九、递归
递归算法指一种通过重复将问题分解为同类的子问题而解决问题 的方法。或者说递归算法是一种直接或者间接地调用自身 的算法。简单来说就是一个方法中会重复调用该方法 解决问题，直到满足基础部分的条件而输出终止 的算法。
例题
进制转换
void f(int n, int k)
{
if (n <k)
{
cout << n << " ";
return;
}
f(n / k, k);
cout << n % k << " ";
}
十、分治与二分
分治算法是一种自顶向下的问题求解方法，其基本思想是将一个问题分解成多个规模较小且相互独立的子问题，每个子问题都可以独立地求解得到结果，然后将这些结果合并得到原问题的解。分治算法通常采用递归的方式实现，将大问题拆解成小问题，从而降低问题的复杂度。
例题
数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
int f(int x,int y){
if(x==n) return b[x][y]=a[x][y];
else
if(b[x][y]!=-1) return b[x][y];
return b[x][y]=max(f(x+1,y),f(x+1,y+1))+a[x][y];
}
二分的基本思想是先确定待查数据的范围（可用 [left,right] 区间表示），然后逐步缩小范围直到找到或找不到该记录为止。具体做法是：先取数组中间位置（mid=(left+right)/2）的数据元素与给定值比较。若相等，则查找成功；否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分[left,mid-1]（或后半部分[mid+1,right]），然后在新的查找范围内进行同样的查找。如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。因此，二分查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。
例题
二分查找
while(cin>>num){
int l=1;//要寻找的数最小可能 （下标）
int r=n;//要寻找的数最大可能 （下标）
while(l<r){
int mid=(l+r)/2;//向下取整 ,因为移动的是l，在l和r相邻的时候
//mid就是l跟r的中间值
if(a[mid]>=num) r=mid;
else l=mid+1;
}
if(a[l]==num) {
cout<<l<<" ";
}
else{
cout<<"0"<<" ";
}
}
十一、栈和队列
笔记
/*
什么是数据结构
结构
结构体
物品和物品之间的关系
数据之间是否也有结构
人ID———>时间 time
两个人对两个人
白洋（蔡老师家在附近，所以给我们举了这个例子） 2 5 16
2 三坝
蔡老师---->27位同学
27位同学------>听蔡老师讲课
一对一
一对多
多对多
数据结构里面的（逻辑结构）
struct Node{
int ID;
int Time;
};
数组【1，2，3，4，5，6，7】
第一个元素只有一个后继元素
最后一个元素只有一个前驱元素
中间的元素只有唯一的前驱元素和后继元素
物理结构
数组
线性结构
栈
栈的特性
先进后出
队列
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
//如何声明一个栈
stack<int> st;
//stack<你的栈的类型名> 【变量名】
/*
所有的操作都面向你声明的栈
.代表的是“的”
输入：【栈名】.push(【数据】) ；
删除：【栈名】.pop();这里面没有参数
没有返回值
输出：【栈名】.top（）；里面没有参数
//返回栈的栈顶元素
【栈名】.size //这里面没参数
返回当前栈元素的个数
【栈名】.empty();这里面没有参数
判断当前栈是否为空
空返回true，非空元素返回falge
*/
st.push(4);
st.push(6);
st.push(2);
cout<<st.top();
return 0;
}
//队列
/*
相比与栈
先进后出
队列
先进先出
是一个序列
有一个对头元素
有一个队尾元素
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
queue<int> qu;
/*
【队列名】.push（【数据】）
【队列名】.pop（）；
【队列名】.front()；这里没有参数
显示对首元素
【队列名】.back（）；这里面没有参数
显示队尾元素
【队列名】.size（）；
【队列名】.empty（）；
*/
return 0;
}
例题
有n个人围成一圈坐，顺时针编号1到n。从编号为1的人开始顺时针报数，报到m的人出列，然后继续从1开始报。请问出列的人的序列。
n人围成一圈，把一人看成一个结点，n人之间的关系采用链接方式，即每一结点有一个前继节点与后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向下一个结点。当m人出列时，将m结点的前继节点指针指向m结点的后继结点指针，即把m结点驱出循环链
1.数组a[i]作为“指针”变量来使用，移动过程：j=a[j];
2.设立指针，指向当前结点，设立计数器，计数数到多少人
3.沿链移动指针，每移动一个结点，计数器加1，当计数器值为m时，则m结点出链，计数器值置为1
4.重复3，直到n个结点均出链为止
定义部分
int n,m;
int a[1005],j,k=1,p=0;
核心代码
while(p<n){
while(k<m){
j=a[j];
k++;
}
printf("%d ",a[j]);p++;
a[j]=a[a[j]];k=1;
}
十二、搜索与回溯
其实就是递归
例题
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和输入一个整数 n(2≤n≤25)按字典序输出具体的方案。
void dfs(int s,int t) {
int i;
for(i=a[t-1]; i<=s; i++) {
if(i<n) {
a[t]=i;
s-=i;
if(s==0) {
cout<<n<<"=";
for(int i=1; i<=t-1; i++)
cout<<a[i]<<"+";
cout<<a[t]<<endl;
} else dfs(s,t+1);
s+=i;
}
}
}
十三、dfs
深度优先搜索算法(简称DFS)是一种用于遍历（或搜索）树（或图）的算法。
算法过程
1.从根节点开始
2.放入一个节点（起始时放入的为根节点）
3.如果这个节点是第一次出现，则放入堆栈中
4.判断该节点的子节点是否搜索完成，
a.如果是则将该节点出栈,判断该栈是否为空
a.1 若为空则结束
a.2 若不为空则取栈顶元素，并回到第2步
b.如果没有完成搜索，取未被搜索的根节点，并回到第2步
基本框架
void dfs(int x) {
if(x>n) {
cnt++;
if(cnt<=3) {
for(int i=1; i<=n; i++) {
cout<<vis[i]<<" ";
}
cout<<endl;
}
return ;
}
for(int i=1; i<=n; i++) {
vis[x]=i;
if(check(x)) {
dfs(x+1);
}
}
}
十四、bfs
广 度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。
基本框架
int dx[]={0,0,1,-1},dy[]={-1,1,0,0};
struct Node{
int x,y,step;
};
void bfs(int X,int Y,int arr[][255]){
queue<Node>qu;
qu.push({X,Y,0});
memset(vis,0,sizeof(vis));
vis[X][Y]=1;
while(!qu.empty()){
Node now=qu.front();
qu.pop();
for(int i=0;i<4;i++){
int now_x=now.x+dx[i];
int now_y=now.y+dy[i];
if(now_x<1||now_x>n||now_y<1||now_y>m||vis[now_x][now_y]==1||mxpn[now_x][now_y]=='#'){
continue;
}
vis[now_x][now_y]=1;
arr[now_x][now_y]=now.step+1;
qu.push({now_x,now_y,now.step+1});
}
}
}
十五、树与图
结点的度：结点拥有的子树个数或者分支的个数。如A结点有三棵子树、所以A结点的度为3
树的度：树中各结点度的最大值。如图中结点度最大为3（A、D结点），所以树的度为3。
树的深度（或高度）：树中结点的最大层次。
树的宽度：整棵树中某一层中最多的结点数称为树的宽度。
根结点：一棵树至少有一个结点，这个结点就是根结点
叶子结点：又叫做终端结点，指度为0的结点。
非终端结点：又叫分支结点，指度不为0的结点，都是非终端结点。除了根结点之外的非终端结点，也叫做内部结点。
父结点/双亲结点：称上端结点为下端结点的父结点。
孩子结点：称下端结点为上端结点的子结点。
兄弟结点：称同一个父结点的多个子结点为兄弟结点。
祖先节点：又称从根节点到某个子结点所经过的所有结点称为这个结点的祖先。
子孙结点：称以某个结点为根的子树的任一结点都是该节点的子孙
邻接表：
可以使用动态数组vector来实现，动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。
定义格式：vector<int> q;
常用函数：push_back() 在vector最后添加一个元素
empty() 判断vector是否为空（返回return时为空）
size() 返回vector数组元素个数
接下来就是我们威武的蔡老师的智慧结晶
智慧结晶
有用就点个赞吧！！！ 
树的宽度
void dfs(int x,int deep){
mm[deep]++;
max_deep=max(max_deep,mm[deep]);
for(int i=1;i<=n;i++){
if(a[x][i]=='1'&&vis[i]==0){
vis[i]=1;
dfs(i,deep+1);
}
}
}
树的深度
void dfs(int x,int deep){
max_deep=max(max_deep,deep);
for(int i=1;i<=n;i++){
if(a[x][i]=='1'&&vis[i]==0){
vis[i]=1;
dfs(i,deep+1);
}
}
}
例题1
给出每一个节点的左右孩子，输出每一个节点的父亲节点，-1表示空
这题很简单，因为只有1是没有父亲结点的，其他都有
所以我们可以先初始化
int node[25]={0,-1};
再输入
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
if(a!=-1) node[a]=i;
if(b!=-1) node[b]=i;
}
最后输出就好了
例题2
给定一棵以 1 为根的二叉树，输出他的先序遍历,如果没有儿子为 -1
这题我们要用到函数
不断地遍历
void dfs(int k) {
if(k==-1) {
return;
}
cout<<k<<" ";
dfs(l[k]);
dfs(r[k]);
}
还要将数组内所有元素都变为-1
memset(l,-1,205);
memset(r,-1,205);
最后输入输出就可以了
例题3
现给你一棵树的所有边，请你判断若干点是否存在父子关系。此树有 n 个结点，编号 1 至 n，其中 1 号是根。
这题只要定义一个零接矩阵
用来存储就可以了
for(int i=1;i<n;i++){
int a1,a2;
cin>>a1>>a2;
a[a1][a2]=1;
}
例题4
已知一棵树，有 N 个结点，编号 1 至 N，其中 1 号是根。求树的所有叶子节点数。
这题只要判断一行中如果只有一个有关联的点就计数
for(int i=1;i<=n;i++){
int sum=0;
for(int j=1;j<=n;j++){
if(a[i][j]=='1') sum++;
}
if(sum==1&&i!=1) {
mm[ans]=i;
ans++;
cnt++;
}
}
二叉树的衍生之FBI树
这题我们要用dfs函数不断地遍历
void dfs(int l,int r){
if(l==r){//串s不再大于1
if(s[l]=='0') cout<<'B';//全0串
if(s[l]=='1') cout<<'I';//全1串
return ;
}
int mid=(l+r)/2;//中间下标
dfs(l,mid);//递归前半部分
dfs(mid+1,r);//递归后半部分
int f1=0,f2=0;//进行判断
for(int i=l;i<=r;i++){
if(s[i]=='0') f1=1;//有0的情况
if(s[i]=='1') f2=1;//有一的情况
}
if(f1==1&&f2==0) cout<<'B';//全1串
else if(f1==0&&f2==1) cout<<'I';//全0串
else cout<<'F';//有1有0的串
}
图的知识点
图是区别于线性结构（只有一个前驱和一个后驱）和树结构（一个父结点和多个子节点）的数据结构，它是一种多对多的关系。
图是由顶点集和边集组成的，通常表示为：G（V,E），其中G表示图，V表示顶点的集合，E表示边的集合。
由于我无法描述下面的东西
所以用一张图片来描述
总结
顶点的度为为以该顶点为一个端点的边的数目。
对于无向图，顶点的边数为度，度数之和是顶点边数的两倍。如图1所示：顶点V5的度为三。
对于有向图，入度是以顶点为终点，出度相反。有向图的全部顶点入度之和等于出度之和且等于边数。如图2所示：顶点V5的入度为3，出度为1。 （注意：入度与出度是针对有向图来说的。）
无向完全图
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有 n(n−1)/2 条边。
有向完全图
如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有 n(n−1) 条边。
子图
假设有两个图G=（V,{E}）和G=（V‘,{E’})，如果V‘是V的子集，且E’是E的子集，则称G‘为G的子图。如图2、图3、图4、均为图1的子图
图的存储
由于本人水平过于低下只好用我们
我们威武的蔡老师的智慧结晶
智慧结晶
连通图
在无向图G中如果从顶点V到顶点V’有路径，则称V和V‘是联通的。如果对于图中 任意两个顶点vi、vj∈G，vi和vj都是联通的 ，则称G是联通图
连通分量
无向图中的 极大连通子图 称为 连通分量 ，指包含了图中尽可能多的顶点以及尽可能多的边，以至于它再加上一个点或者边之后它就不连通了
连通图的极大连通子图就是他本身。
非连通图中有多个连通分量也就是可以有多个极大连通图。
强连通图&强连通分量
在有向图G中，如果对于每一对vi、vj，vi ≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
有向图中的极大强连通子图称作有向图的强连通分量。
例题1
给出一个有 n 个结点，m 条边的无向图，从 1 到 n 按顺序输出各个结点的度。
这题我们就要用到邻接矩阵来表示顶点之间的关系
首先输入
cin>>n>>m;
for(int i=1;i<=m;i++){
int a1,a2;
cin>>a1>>a2;
a[a1][a2]=1;
a[a2][a1]=1;
}
再进行遍历
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=1;j<=n;j++){
if(a[i][j]==1) cnt++;
}
cout<<cnt<<'\n';
}
然后就达成了题目的要求
例题2
给出一个无向图，输出每个点相邻的那些点。
这题我们用动态数组vector就能很好的表示
先定义
vector<vector<int> >g;
再输入与初始化
g.resize(n+1);
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(x!=y){
g[x].push_back(y);
g[y].push_back(x);
}
}
再判断与输出
for(int i=1;i<=n;i++){
sort(g[i].begin(),g[i].end());
for(int j=0;j<g[i].size();j++){
if(j!=g[i].size()-1&&g[i][j]==g[i][j+1]) continue;
cout<<g[i][j]<<" ";
}
cout<<'\n';
}
例题3
给出一个无向图，和一棵树，求至少要加多少边才能将这棵树变成给定的图，如果无法变成，则输出 impossible。
这题我们只要不停的进行对比就行了，但有可能爆内存，所以可以用short
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
a[x][y]=1,a[y][x]=1;
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
b[x][y]=1,b[y][x]=1;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==0&&b[i][j]==1){
cnt++;
a[i][j]=1;
a[j][i]=1;
}
if(b[i][j]==0&&a[i][j]==1){
cout<<"impossible";
return 0;
}
}
}
cout<<cnt<<'\n';
例题4
图的dfs遍历
这题与树的dfs遍历有一点相似
所以就不讲了
dfs部分
void dfs(int x){
cout<<x<<' ';//输出顺序
for(int i=0;i<g[x].size();i++){
if(vis[g[x][i]]==1) continue;//访问数组为1，就跳过
vis[g[x][i]]=1;//不然就递归
dfs(g[x][i]);
}
}
例题5
题目描述:
给出 N 个点，M 条边的有向图，对于每个点 v，求 ()A(v) 表示从点 v 出发，能到达的编号最大的点。
这题要用bfs搜索加判断
void bfs(){
queue<int> w;
w.push(s);
while(w.size()) {
int h=w.front();
if(sum<h){//判断大小
sum=h;
}
w.pop();
for(int i=0; i<g[h].size(); i++) {
if(vis[g[h][i]]) {
continue;
}
vis[g[h][i]]=1;
w.push(g[h][i]);
}
}
}
搜索
for(int i=1;i<=n;i++){
sum=-1;
s=i;
memset(vis,0,sizeof(vis));
vis[s]=1;
bfs();
cout<<sum<<' ';
}
例题6
给出一个无向图，求图的连通分量的个数。保证无重边和自环。
这题与图的dfs遍历与连通块问题都有相似，就是他们的子问题
先进行遍历
void dfs(int x){
for(int i=0;i<g[x].size();i++){
if(vis[g[x][i]]==1) continue;
vis[g[x][i]]=1;
dfs(g[x][i]);
}
}
再进行计数
for(int i=1;i<=n;i++){
if(vis[i]==0){
cnt++;//计数器++
vis[i]=1;//访问数组为1
dfs(i);//遍历
}
}
cout<<cnt;//输出
十六、背包问题
背包问题！！！
可恶的大炮dp又来折磨我们这些好孩子了
基本思路：
这是最基本的背包问题，特点是：每种物品只有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品（部分或全部）恰放入一个容量为v的背包可以获得的最大价值，即其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}。
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。 所以有必要将它详细解释一下：“将前i减一件物品放入容量为v的背包中”这个子问题若只考虑第i件物品的策略(放或不放)，那么就可以转化为一个只牵扯前i减一件物品的问题。如果不放的i件物品，那么问题就转化为“前i减一件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是f[i-1][v-w[i]]再加上通过放入第i件物品所得的价值c[i]。
注意f[i][v]有意义当且仅当存在一个前i件物品的子集其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N][V]，而是f[N][0…V]的最大值。如果将这个状态的定义中的“”字去掉，在转移方程中就要再加入一项f[i-1][v]，这样就可以保证f[N][V]就是最后的答案。但是若将所有f[i][j]的初始值都赋为0。你会发现f[n][v]也会是最后的答案。为什么呢？因为这样你默认了最开始f[i][j]是有意义的，只是价值为0,就看作是无物品放的背包价值都为0，所以对最终价值无影响,这样初始化后的状态表示就可以把“恰”字去掉。
优化空间复杂度
以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了，但空间复杂度即可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1…N，每次算出来二维数组f[i][0…V]的所有值。那么如果只用一个一维数组f[0…V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-w[i]]两个子问题递推而来的，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[v-w[i]]的值呢？事实上这要求在每次循环中，我们以v=V…0的逆推f[v],这样才能保证推f[v]时f[v-w[i]]保存的是状态f[i-1][v-w[i]]的值。
核心代码如下
for(int i=1;i<=m;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=m;i++){
for(int j=t;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[t];
例题1
有N个物品，每个物品有一个重量与价值，现在只能拿走最重总和不超过M的物品，求最大的价值之和
这题就是一道模版题只要对着我们的核心代码就能轻松AC
核心代码
cin>>m>>t;
for(int i=1;i<=m;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=m;i++){
for(int j=t;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[t];
例题二
有一个箱子容量为V，同时有n个物品，每个物品有一个体积。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
int v,n;
cin>>v>>n;
for(int i=1;i<=n;i++) cin>>w[i];//物品体积
for(int i=1;i<=n;i++){
for(int j=v;j>=w[i];j--){//，表示不超过j体积的最大体积。
if(f[j]<f[j-w[i]]+w[i]) f[j]=f[j-w[i]]+w[i];//寻找不超过j体积的最大体积，并判断装入箱子是否是最优解。
}
}
cout<<v-f[v];//f[v]为装入箱内的最大体积，v-f[v]求出箱内的剩余体积
前言
链表是一种非常非常基础的数据结构，本文首先讲解链表的基础知识，然后使用C++的模板实现了一个链表类，并简单实现了常见的插入、删除、查找等算法。
阅读本文需要对C/C++的指针具有一定的了解。
基础知识
链表是一种逻辑上连续，内存上分散的线性表数据结构，其基本单位为结点，每个结点分数据区和指针区，数据区用于存放数据，指针区则用于指向其他结点，通过指针每个结点就被串接成了一条“链子”。
单链表
最基本的单链表结构如下图所示：
单链表每个结点包含一个指针，该指针指向下一个结点，最后一个结点的指针则为NULL，通常也会通过NULL判断是否到达链表的尾部。因此，单链表无法“回头”，只能向前遍历，不能向后遍历。假设需要访问结点D的数据，就需要将头指针head赋值给一个指针p，然后让p依次前移两次，此时p指向D结点，就可以通过指针p访问D结点的数据。所谓前移即如下操作：
p = p->next
插入操作
假如需要在C结点后面插入F结点，只需要使C结点的指针指向F，F结点的指针指向结点D即可，如图所示
需要注意的是，在具体实现的时候，需要先暂存C结点的指针，先将其赋值给F结点指针，然后再将F结点的地址赋值给C结点的指针，否则会丢失D结点的地址，链表就会在此处断开。
删除操作
假如需要删除D结点，则直接让C结点的指针指向E结点即可，如图所示
与数组的对比
相比于数组，链表存在如下优势：
- 不要求连续的储存空间，且链表的长短随时可变，空间利用率高
- 因为链表的线性特征是利用指针实现的，所以链表的插入和删除都非常方便，只需要修改节点的指针即可，不需要像数组一样需要挪动元素的位置。
当然，天下没有白吃的午餐，相比数组，链表也存在如下劣势：
- 数据访问效率低，需要移动指针找到想要的数据，不像数组可以直接通过索引获取数据。
- 实现更复杂，且需要多余的内存用于存放指针
因此，到底是使用链表还是数组，应该根据应用场景与需求选择
代码实现
本文利用C++面向对象的特性与模板实现了一个链表类，并实现了插入、删除、查找、拷贝构造、拷贝赋值等基本操作。出于篇幅考虑，完整代码放在了我的github，点击这里查看，本文仅讲解插入、删除、查找部分的代码，并阐述链表对象的析构思路，毕竟C++申请的内存还是需要手动回收的。
结点类实现
// 链表节点类
template<typename T>
class node
{
public:
node() : next(nullptr){}
node(T val) : data(val), next(nullptr) {}
private:
T data;
node* next;
friend class list<T>;
};
链表的结点类node如上，非常简单，就是每个结点一个存放数据的成员data和一个指针next，同时在node类中将链表类list声明为友元，便于访问node的成员。
链表类声明
链表类list的声明如下，主要实现了以下操作。list类包含两个成员属性head_ptr和length，前者是链表的头指针，后者储存链表的长度。
template<typename T>
class list
{
public:
list(); // 构造函数
list(const list<T>& l); // 拷贝构造
list<T>& operator= (const list<T>& l); // 拷贝赋值
void insert_node(int index, T val); // 在index处插入结点
void del_node(int index); // 删除index处结点
T get_node(int index); // 获取index处结点值
int find(int value); // 查找值value，找到返回index，找不到返回-1
int get_length(); // 获取链表长度
void push_back(T val); // 在链表尾部插入数据
~list(); // 析构函数
private:
node<T>* head_ptr; // 链表头指针
int length; // 链表长度
};
插入实现
对于插入操作，本文将其分为了三种情况
- 超出索引，抛出异常
- 插在空链表的头
- 一般情况
// 在index处插入结点
template<typename T>
void list<T>::insert_node(int index, T val)
{
if((index > this->length)) // 超过索引，最多可以插到当前结点的下一个结点，否则就是超过索引
{
throw runtime_error("index out of this list`s range");
}
else if((this->head_ptr == nullptr) && (index == 0)) // 插在空链表的头
{
this->head_ptr = new node<T>;
this->head_ptr->next = nullptr;
this->head_ptr->data = val;
this->length++;
}
else // 一般情况
{
node<T>* p1 = this->head_ptr;
node<T>* p2 = new node<T>;
for(int i = 0; i < index - 1; i++)
{
p1 = p1->next;
}
p2->data = val;
p2->next = p1->next;
p1->next = p2;
this->length++;
}
}
删除实现
删除操作需要注意的是，每个结点都是通过new在堆区申请的内存，因此删除节点需要手动释放其内存。
// 删除index处结点
template<typename T>
void list<T>::del_node(int index)
{
node<T>* p1 = this->head_ptr;
node<T>* p2 = nullptr;
for(int i = 0; i < index - 1; i++)
{
p1 = p1->next;
}
p2 = p1->next->next;
delete p1->next;
p1->next = p2;
this->length--;
}
索引实现
// 获取index处结点值
template<typename T>
T list<T>::get_node(int index)
{
if(index > this->length - 1) // 超过索引
{
throw runtime_error("index out of this list`s range");
}
node<T>* p1 = this->head_ptr;
for(int i = 0; i < index; i++)
{
p1 = p1->next;
}
return p1->data;
}
查找实现
// 查找值value，找到返回index，找不到返回-1
template<typename T>
int list<T>::find(int value)
{
node<T>* p1 = this->head_ptr;
for(int i = 0; i < this->length; i++)
{
if(p1->data == value)
{
return i;
}
p1 = p1->next;
}
return -1;
}
析构函数
析构函数需要做的就是释放链表每个节点的内存。
// 析构函数
template<typename T>
list<T>::~list()
{
// 清空链表
node<T>* p1 = this->head_ptr;
node<T>* p2 = p1->next;
while(p2 != nullptr)
{
delete p1;
p1 = p2;
p2 = p2->next;
}
delete p1;
this->length = 0;
this->head_ptr = nullptr;
}
制作不易点个赞吧，求求了！！！
放松网站别声张