首页 > 编程语言 >【数据结构】：破译排序算法--数字世界的秩序密码（二）

【数据结构】：破译排序算法--数字世界的秩序密码（二）

时间：2024-10-15 22:18:43浏览次数：7  
标签：排序 递归 -- int right 数组 数据结构 left

文章目录

前言

在上一篇文章中，主要讲了插入排序，希尔排序，选择排序，堆排序（详细可以看我上一篇文章哦），在接下来的这篇文章中，将重点讲解冒泡排序，快速排序，归并排序以及计数排序。

一.比较排序算法

1.Bubble Sort冒泡排序

1.1.冒泡排序原理

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。

1.2.冒泡排序过程

  • 比较相邻的元素，如果第一个比第二个大（升序），就交换他们两个。

  • 遍历数列，对每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对，这步结束后，最大（或最小）的元素会在数列的结尾。

  • 针对所有的元素重复以上步骤，除了最后一个。

  • 重复上面的步骤，直到没有任何一对元素需要比较。

在这里插入图片描述

在这里插入图片描述

1.3.代码实现

//交换
void Swap(int*a,int*b){
    int t=*a;
    *a=*b;
    *b=t;
}
void BubbleSort(int*a,int n){
    for(int j=0;j<n;j++){
        //设置一个变量用来判断每一趟是否交换
        bool exchange=false;
        //内层循环是每一趟的比较交换
        for(int i=1;i<n-j;i++){
            if(a[i-1]>a[i]){
                Swap(&a[i-1],&a[i]);
                exchange=true;
            }
        }
        //如果某一趟没有进行交换就是序列已经有序，直接结束排序
        if(exchange==false){
            break;
        }
    }
}

1.4.复杂度和稳定性

  • 时间复杂度：冒泡排序的平均和最坏时间复杂度都是O(n^2)。
  • 空间复杂度；冒泡排序的空间复杂度为O(1)。
  • 稳定性：冒泡排序是稳定的排序算法，即相等的元素在排序后的序列中保持原来的顺序。但由于其效率较低，通常不被用作主要的排序算法。

2.Quick Sort快速排序

2.1递归快速排序

2.1.1.递归快速排序原理

快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它采用分治（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

快速排序的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分的所有记录均比另一部分的所有记录小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2.1.2.递归快速排序过程

  • 选择基准值：从代排序的数列中选出一个元素作为基准值（key），最常用的就是三数取中法，通过比较数列的第一个和最后一个以及中间的值，选出这三个数的中间值，然后和最左端的也就是第一个数交换。基准值的选择对于排序的效率有重要影响。

  • 分区：重新排列数列，所有比基准值小的元素排在基准值前面，比基准值大的元素排在基准值后面（相同的数可以放在任意一边）。分区的操作有多种实现方法，如hoare法，挖坑法，前后指针法。

    1.hoare法：

    在这里插入图片描述

    2.挖坑法：

    在这里插入图片描述

    3.前后指针法：

    在这里插入图片描述

  • 递归排序子序列：递归地将小于基准值的子序列和大于基准值的子序列排序。递归的最底部情形是数列的大小是零活着一，也就是已经排好序。

2.1.3.代码实现
//获取基准值
int Getmid(int*a,int left, int right) {
	int mid = (left + right) / 2;
	if (a[left] > a[mid]) {
		if (a[mid]> a[right]) {
			return mid;
		}
		else if (a[right] > a[left]) {
			return left;
		}
		else{
			return right;
		}
	}
	else {
		if (a[right] > a[mid]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}
//hoare法
int keysort1(int* a, int left, int right) {
	int key = Getmid(a, left, right);
	Swap(&a[left], &a[key]);
	key = left;
	while (left < right) {
		while (left < right && a[right] >= a[key]) {
			right--;
		}
		while (left < right && a[left] <= a[key]) {
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);
	key = left;
	return key;
}
//挖坑法
int keysort2(int* a, int left, int right) {
	int key = Getmid(a, left, right);
	Swap(&a[left], &a[key]);
	int keyi = a[left];
	int hole = left;
	while (left < right) {
		while (left<right && a[right]>=keyi) {
			right--;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= keyi) {
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = keyi;
	hole = left;
	return hole;
}
//前后指针法
int keysort3(int* a, int left, int right) {
	int mid = Getmid(a, left, right);
	Swap(&a[left], &a[mid]);
	int key = left;
	//后指针
	int prev = left;
	//快指针
	int cur = left + 1;
	while (cur <= right) {
		if (a[cur] < a[key] && ++prev != cur) {
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[key], &a[prev]);
	key = prev;
	return key;
}

void QuickSort(int* a, int left,int right) {
	if (left >= right) {
		return;
	}
	int begin = left;
	int end = right;
    //分区，三种方法选一种即可
	int key = keysort3(a, left, right);
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

2.2.非递归快速排序

2.2.1.非递归快速排序原理

非递归快速排序的原理和过程与递归快速排序相似，但主要区别在于非递归版本通过显式地使用一个辅助栈（或队列）来模拟递归过程中的函数调用栈，从而避免了递归调用。

2.2.2.非递归快速排序过程

  1. 初始化栈：

    • 创建一个空栈用于保存待排序子数组的起始和结束索引。

  2. 将初始数组的起始和结束索引入栈：

    • 这对应于最初的排序问题。

  3. 循环处理栈中的元素：

    • 当栈不为空时，进行以下操作：

      1. 弹出栈顶的一对索引（起始和结束索引），这指定了当前要处理的子数组。

      2. 在当前子数组上选择一个基准元素，并进行分区操作。

        (分区操作会将数组分为左右两部分，并返回基准元素的最终位置。)

      3. 如果基准元素左侧的子数组有超过一个元素，则将其起始和结束索引作为一对入栈。

      4. 如果基准元素右侧的子数组有超过一个元素，也将其起始和结束索引作为一对入栈。

  4. 重复步骤3，直到栈为空，此时所有子数组都已经被正确排序。

2.2.3.代码实现
void QuickSortNoNR(int* a, int left, int right) {
	//创建栈
	Stack st;
	//初始化栈
	InitStack(&st);
	int begin = left;
	int end = right;
	//将第一个区间入栈
	pushStack(&st, end);
	pushStack(&st, begin);
	//循环条件栈不为空
	while (!IsEmpty(&st)) {
		//将区间出栈
		begin = getpopStack(&st);
		popStack(&st);
		end = getpopStack(&st);
		popStack(&st);
		//获取key值下标，分区
		int key = keysort3(a, begin, end);
		//右子区间满足条件入栈
		if (key + 1 < end) {
			pushStack(&st, end);
			pushStack(&st, key + 1);
		}
		//左子区间满足条件入栈
		if (begin < key - 1) {
			pushStack(&st, key - 1);
			pushStack(&st, begin);
		}
	}
	//销毁栈
	DestroyStack(&st);
}

2.3.复杂度和稳定性

  • 时间复杂度：快速排序的时间复杂度平均为O(n log n)，但在最坏情况下（如数组已经有序时）会退化到O(n^2)。
  • 空间复杂度：
  • 稳定性：快速排序是不稳定的排序算法，即相同的元素可能在排序过程中改变相对位置。

二.归并排序算法

Merge Sort归并排序

1.递归归并排序

1.1.递归归并排序原理

递归归并排序是建立在归并操作上的一种有效排序算法，它采用分治法（Divide and Conquer）来进行排序。分治法的基本思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题，子问题再继续分解，直到这些子问题变得简单到可以直接解决，然后再合并子问题的解为原问题的解。

在归并排序中，分治法的应用体现在：

  1. 分解：将待排序的数组分解成两个较小的子数组，然后子数组再继续分解，直到子数组的大小为1（即只有一个元素，此时认为它是有序的）。
  2. 解决：递归地对子数组进行排序并合并，得到有序的子数组。
  3. 合并：将两个有序的子数组合并成一个有序的大数组，直到合并为1个完整的数组。
1.2.递归归并排序过程

  1. 分解：

    • 将待排序的数组a[begin...end]分解成两个子数组a[begin...mid]和a[mid+1...end]，其中mid是begin和end的中间位置（mid = (begin + end) / 2）。
    • 递归地对这两个子数组进行分解，直到子数组的大小为1。

  2. 递归排序并合并：

    • 对分解得到的子数组进行递归排序。
    • 合并两个有序的子数组为一个有序数组。合并过程中，通过比较两个子数组的元素，将较小的元素依次放入一个新的临时数组tmp中，直到所有元素都被合并。

  3. 合并：

    • 合并过程中，使用两个指针begin1,begin2分别指向两个子数组的起始位置，比较两个指针所指的元素，将较小的元素放入临时数组中，并移动该指针。
    • 当其中一个子数组的所有元素都被合并后，将另一个子数组中剩余的元素依次复制到临时数组的末尾。
    • 最后，将临时数组中的元素复制回原数组中的相应位置，完成合并。

  4. 递归终止条件：

    • 当子数组的大小为1时，递归终止，因为单个元素的数组自然是有序的。

  5. 排序完成：

    • 当整个数组被分解为单个元素的子数组，并通过递归合并成有序的大数组时，排序完成。

在这里插入图片描述

在这里插入图片描述

1.3.代码实现
void _MergeSort(int*a,int begin,int end,int*tmp){
    //不满足条件时结束返回
    if(begin>=end){
        return;
    }
    //找中间值下标
    int mid=(begin+end)/2;
    //递归分区，[begin,mid],[mid+1,end]
    _MergeSort(a,begin,mid,tmp);
    _MergeSort(a,mid+1,end,tmp);
    //设置分区的下标
    int begin1=begin,end1=mid;
    int begin2=mid+1,end2=end;
    //循环比较，依次存放到tmp数组中
    //注意：这里tmp数组的下标一定要从begin开始，而不是从0开始
    int i=begin;
    while(begin1<=end1&&begin2<=end2){
        if(a[begin1]<a[begin2]){
            tmp[i++]=a[begin1++];
        }
        else{
            tmp[i++]a[begin2++];
        }
    }
    while(begin1<=end1){
        tmp[i++]=a[begin1++];
    }
    while(begin2<=end2){
        tmp[i++]=a[begin2++];
    }
    //将tmp数组中排序好的拷贝到原数组中,复制范围是每次函数调用的左右区间
    memcpy(a+begin,tmp+begin,sizeof(int)*(end-begin+1));
}

void MergeSort(int*a,int n){
    //创建一个临时数组用来存放排好序的序列
    int*tmp=(int*)malloc(sizeof(int)*n);
    if(tmp==NULL){
        perror("malloc false");
        return;
    }
    _MergeSort(a,0,n-1,tmp);
}

2.非递归归并排序

2.1.非递归归并排序原理

==非递归归并排序（也称为迭代归并排序）==与递归归并排序在原理上相同，都是基于分治法的排序算法。不过，在实现方式上，非递归归并排序通过循环而不是递归调用来控制排序过程。非递归归并排序也是将数组分解成若干个子数组，直到子数组的大小为1（即只有一个元素，此时认为它是有序的）。然后，通过迭代的方式，逐步合并相邻的有序子数组，直到合并成一个完整的有序数组。

2.2.非递归归并排序过程
  1. 初始化：
    • 定义一个变量gap，用于表示当前归并的子数组的大小（即每次合并时考虑的元素个数）。初始时，gap通常设置为1，表示每个子数组只包含一个元素。
  2. 迭代合并：
    • 使用一个外层循环，不断增大gap的值，直到gap大于等于数组的长度。这个循环控制归并的轮数。
    • 在每一轮归并中，使用一个内层循环来遍历数组，并合并相邻的、大小为gap的有序子数组。合并过程中，需要使用一个临时数组tmp来存放合并后的结果。
  3. 合并相邻子数组：
    • 在内层循环中，对于每一对相邻的子数组（它们的起始位置相差gap），使用类似于递归归并排序中合并函数的方法将它们合并成一个有序的子数组。
    • 合并过程中，使用两个指针begin1,begin2分别指向两个子数组的起始位置，比较两个指针所指的元素，将较小的元素放入临时数组中，并移动该指针。
    • 当其中一个子数组的所有元素都被合并后，将另一个子数组中剩余的元素依次复制到临时数组的末尾。
    • 最后，将临时数组中的元素复制回原数组中的相应位置，完成合并。
  4. 更新gap：
    • 在外层循环的每次迭代结束时，将gap的值加倍（即gap *= 2），以便在下一轮归并中合并更大范围的子数组。
  5. 排序完成：
    • 当gap大于等于数组的长度时，排序完成。此时，整个数组被合并成一个有序的大数组。

在这里插入图片描述

2.3.代码实现
void MergeSortNoNR(int*a,int n){
    //创建一个临时数组用来存放排好序的序列
    int* tmp=(int*)malloc(sizeof(int)*n);
    if(tmp==NULL){
        perror("malloc false");
        return;
    }
    //初始化：设置分区间隔值gap，从1开始
    int gap=1;
    //迭代合并：
    while(gap<n){
        //合并相邻子数组：
        for(int i=0;i<n;i+=gap*2){
            //分区
            int begin1=i,end1=i+gap-1;
            int begin2=i+gap,end2=i+gap*2-1;
            int j=i;
            //处理临界情况
            if(begin2>=n){
                break;
            }
            if(end2>=n){
                end2=n-1;
            }
            //循环比较，依次存放到tmp数组中
            while(begin1<=end1&&begin2<=end2){
                if(a[begin1]<a[begin2]){
                    tmp[j++]=a[begin1++];
                }
                else{
                    tmp[j++]=a[begin2++];
                }
            }
            while(begin1<=end1){
                tmp[j++]=a[begin1];
            }
            while(begin2<=end2){
                tmp[j++]=a[begin2];
            }
            //将tmp数组中排序好的拷贝到原数组中
            //注意：这里用i，不用begin1,是因为begin1++值已经改变
            memcpy(a+i,tmp+i,sizeof(int)*(end2-i+1));
        }
        //更新gap:
        gap*=2;
    }
}

3.复杂度和稳定性

  • 时间复杂度：归并排序的时间复杂的为O(n*log n)。
  • 空间复杂度：归并排序的空间复杂度为O(n),因为借助了一个临时数组tmp，数组长度为n。
  • 稳定性：归并排序是一种稳定的排序算法。

三.非比较排序算法

Cout Sort计数排序

计数排序原理

计数排序（Counting Sort）是通过统计待排序元素的出现次数来确定元素的相对位置，从而实现排序。这种算法不是基于比较的排序算法，而是通过统计每个元素的出现次数，并利用这些信息来重新排列元素。

计数排序过程

  1. 找出待排序数组的最大值和最小值：

    • 遍历待排序数组，找出数组中的最大值max和最小值min。

  2. 创建计数数组并初始化：

    • 根据最大值和最小值创建一个计数数组countA，其长度range为max - min + 1（如果数组中存在负数，则需要对所有元素进行偏移，使得所有元素都是非负的）。
    • 将计数数组的所有元素初始化为0。

  3. 统计每个元素的出现次数：

    • 再次遍历待排序数组，对于数组中的每个元素x，将countA[x - min]（如果元素是负数或需要特殊偏移，则相应调整）的值增加1。这样，计数数组就记录了每个元素的出现次数。

  4. 对计数数组进行累加（也称为前缀和）：

    • 遍历计数数组，将每个元素的值更新为从计数数组开始到当前元素位置（包括当前元素）的所有元素之和。这一步完成后，计数数组中的每个元素都表示小于等于该索引对应元素值的元素个数。

  5. 根据计数数组将元素放回原数组的正确位置：

    • 创建一个临时数组temp，其长度与待排序数组相同。
    • 从后往前遍历待排序数组（这是为了确保排序的稳定性），对于每个元素x，通过count[x - min] - 1（如果元素是负数或需要特殊偏移，则相应调整）找到其在临时数组中的正确位置，并将x放入该位置。然后，将count[x - min]的值减1，以便下一个相同值的元素能够找到其正确的位置。

  6. 将排序后的元素复制回原数组（如果需要）：

    • 如果原数组需要被直接修改以反映排序后的结果，则将临时数组temp中的元素复制回原数组。否则，可以直接使用临时数组作为排序后的数组。

在这里插入图片描述

代码实现

void CountSort(int*a,int n){
    //找出待排序数组的最大值和最小值
    int max=a[0],min=a[0];
    for(int i=0;i<n;i++){
        if(a[i]>max){
            max=a[i];
        }
        if(a[i]<min){
            min=a[i];
        }
    }
    //创建计数数组并初始化
    int range=max-min+1;
    int*countA=(int*)malloc(sizeof(int)*range);
    if(countA==NULL){
        perror("malloc false");
        return;
    }
    //将计数数组的所有元素初始化为0
    memset(countA,0,sizeof(int)*range);
    //统计每个元素的出现次数
    for(int i=0;i<n;i++){
        countA[a[i]-min]++;
    }
    //将原数组的元素按照计数数组的个数复制到原数组中
    int j=0;
    for(int i=0;i<n;i++){
        while(countA[i]--){
            a[j++]=i+min;
        }
    }
}

复杂度和稳定性

  • 时间复杂度：计数排序的的时间复杂度为O(n+k)，n是待排序数组的长度，k是元素范围，最大值-最小值加一。
  • 空间复杂度：空间复杂度为O(n+k)，需要创建计数数组。
  • 稳定性：计数排序是一种稳定的排序算法，适用于整数或有限范围内的非负整数排序。

四.代码文件

这里附上整个代码文件：

  • 头文件Sort.h
  • 测试文件test.c
  • 接口函数实现文件Sort.c(文件内容就是每个代码实现)

1.头文件Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
//递归快速排序
void QuickSort(int* a, int left, int right);
//三数取中
int Getmid(int* a, int left, int right);
//霍尔版本快速排序
int keysort1(int* a, int left, int right);
//挖坑法快速排序
int keysort2(int* a, int left, int right);
//前后指针法快速排序
int keysort3(int* a, int left, int right);
//非递归快速排序
void QuickSortNoNR(int* a, int left, int right);
//递归归并排序
void MergeSort(int* a, int n);
void _MergeSort(int* a, int left, int right, int* tmp);
//非递归归并排序1
void MergeSortNoNR1(int* a, int n);
//非递归归并排序2
void MergeSortNoNR2(int* a, int n);
//计数排序
void CountSort(int* a, int n);

2.测试文件test.c

//冒泡排序测试
void Bubbletest() {
	int a[10] = { 3,6,7,2,1,5,4,9,8,10 };
	int n = (sizeof(a) / sizeof(int));
	BubbleSort(a, n);
	printf("冒泡排序：\n");
	PrintArray(a, n);
}
//快速排序测试
void Quicktest() {
	int a[20] = { 3,6,7,2,1,5,4,9,8,10,-2,7,-4,23,-1,-5,65,4,16,-3 };
	int n = (sizeof(a) / sizeof(int));
	QuickSortNoNR(a, 0, sizeof(a) / sizeof(int) - 1);
	printf("快速排序：\n");
	PrintArray(a, n);
}
//归并排序测试
void Mergetest() {
	int a[9] = { 2,1,7,5,4,9,3,8,6 };
	int n = (sizeof(a) / sizeof(int));
	MergeSortNoNR2(a, n);
	printf("归并排序：\n");
	PrintArray(a, n);
}
//计数排序测试
void Counttest() {
	int a[9] = { 2,1,7,2,4,1,3,8,6 };
	int n = (sizeof(a) / sizeof(int));
	CountSort(a, n);
	printf("计数排序：\n");
	PrintArray(a, n);
}
int main(){
    Bubbletest();

	Quicktest();

	Mergetest();

	Counttest();

	return 0;
}
}

3.测试结果

在这里插入图片描述

以上就是关于排序部分冒泡排序，快速排序，归并排序和计数排序的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
在这里插入图片描述

标签：排序,递归,--,int,right,数组,数据结构,left
From： https://blog.csdn.net/2301_82347435/article/details/142965686

相关文章

  • QT实现改变窗口大小其子控件也自动调节大小
    创建一个顶层布局即可，一定要在MainWindows或者Widget的下面！ 观察图标变化带有禁止的意思是分拆布局（当前无布局）现在是添加布局后了 注意：一定是在MainWindows或Widget才可以添加顶层布局，才可以实现控件自适应现在我想实现的是文字跟随变化，效果图如下所以我们利用......
  • QT的信号与槽
    提出疑问：界面上已经有的按键，怎么操作才能让用户按下按键后有操作上的反应呢？在Qt中，信号和槽机制是一种非常强大的事件通信机制。这是一个重要的概念，特别是对于初学者来说，理解它对于编写Qt程序至关重要。信号(Signals)：是由对象在特定事件发生时发出的消息。例如，QPushButt......
  • 自定义信号与槽
    在Qt中，自定义信号与槽是实现对象间通信的一种机制。信号和槽是Qt对象通信的核心特性，使得一个对象能够在发生某种事件时通知其他对象。自定义信号与槽的实现步骤如下：定义信号：在Qt中，信号是由signals关键字声明的类成员函数。它们不需要实现，只需声明。classMyClass:publi......
  • 解压视频素材从哪儿下载？下载解压视频素材的网站有哪些？
    做抖音小说推文，哪里找爆款素材？作为一名从业多年的视频剪辑师，今天就来给大家揭秘可以下载爆款推文视频素材的网站，如果你也在苦苦找寻找，赶紧进来看看吧～1、稻虎网首先是稻虎网，作为国内顶级的短视频素材网站，提供了大量小说推文视频素材，无论是无论是太空沙、刮肥皂、液压机，还是手......
  • 法阵
    法阵题意给你一个长\(n\)的数列，有\(t\)次询问，每次询问区间\([l,r]\)里满足\(l\lex<y<z\ler,y-x\lez-y\)的三元组\(a_x+a_y+a_z\)的最大值。其中\(n,t\leq5\times10^5\)。solution结论：最终对答案有贡献的二元组\((x,y)\)一定满足\(a_x>\max_{i=x+1}^{y-1}......
  • Krita配置comfyui，ai绘图 记录
     comfyui使用b站up、赛博佛祖秋葉aaaki的整合包。此地址下载ai插件https://github.com/Acly/krita-ai-diffusionkrita中安装下载好的插件，从文件导入python插件打开ai绘图面板：缺失节点使用复制链接地址然后,在复制的地址后加上.git后使用comfyUImanager通过gitURL安装......
  • 函数
    Rust代码中的函数和变量名使用snakecase规范风格。在snakecase中，所有字母都是小写并使用下划线分隔单词。这是一个包含函数定义示例的程序：fnmain(){println!("Hello,world!");another_function();}fnanother_function(){println!("Anotherfuncti......
  • [题解]CF1136E Nastya Hasn't Written a Legend
    思路首先考虑操作1一个点\(i\)能被操作到的条件。注意到此时\(x\simi-1\)这些位置都是被更新过的，再仔细观察此时\(\forallj\in[x,i),a_j=a_x+\sum_{p=x}^{j-1}k_p\)。那么对于\(a_i\)如果会被修改将会变为\(a_x+\sum_{p=x}^{i-1}k_p\)，那么\(a_i......
  • 10.15
    学习了如何在JavaWeb项目中进行数据库连接操作。通过JDBC连接数据库，执行SQL查询语句获取数据。importjava.sql.Connection;importjava.sql.DriverManager;importjava.sql.ResultSet;importjava.sql.Statement;publicclassDatabaseAccessExample{publicstatic......
  • [ABC213G] Connectivity 2 题解
    T3[ABC213G]Connectivity2题意：给定一张无向图\(G\)，将其删去\(0\) 条及以上的边构成一张新图，求对于所有点\(k\in(1,n]\)，使\(k\) 与\(1\) 连通的新图的个数。比较套路的一道状压DP。尽管刚开始思考毫无头绪。Step1.令\(f_S\)表示点集为\(S\)的连通子图的个数，\(......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99