竞赛常⽤模板整理（ACMICPCCCSP）竞赛常⽤模板（ACM/ICPC/CCSP/蓝桥杯/传智杯等）
常⽤算法
0.1 快速排序
void ksort(int l,int h,int a[])
{
if(h < l +2)
{
return;
}
中国法医学杂志int e = h, p = l;
while(l < h)
{
while(++l < e && a[l]<= a[p]);
while(--h > p && a[h]>= a[p]);
if(l < h)
{
swap(a[l], a[h]);
}
}
swap(a[h], a[p]);
ksort(p, h, a);
ksort(l, e, a);
return;
深二度烧伤}
0.2 希尔排序
void Shell_sort(int s[],int len){
int tmp,j;
for(int step=len/2;step>0;step/=2){//设置步长
for(int i=step;i<=len;++i){
tmp=s[i];
for(j=i-step;j>0&&tmp<s[j];j-=step);
for(int k=i;k>j+step;k-=step)s[k]=s[k-step];
s[j+step]=tmp;
}
}
}
0.3 选择排序
void Select_sort(int s[],int len){
int k;
for(int i=1;i<len;++i){
k=i;
for(int j=i+1;j<=len;++j)
if(s[k]>s[j])k=j;
if(k!=i)swap(s[i],s[k]);
}
}
0.4 归并排序
void Merge(int s[],int t[],int low,int mid,int high){
int i=low,j=mid+1,k=low;
while(i<=mid&&j<=high){
if(s[i]<=s[j])t[k++]=s[i++];
else t[k++]=s[j++];
}
while(i<=mid)t[k++]=s[i++];
while(j<=high)t[k++]=s[j++];
for(int i=low;i<=high;++i)s[i]=t[i];//将区间[low,high]拷贝到原来数组s对应的位置，表⽰该区间元素已排好序} 0.5 堆排序
void Heap_Adjust(int s[],int cur,int len){
int tmp=s[cur];//先取出当前元素cur
for(int j=2*cur;j<=len;j*=2){//向下筛选
if(j<len&&s[j]<s[j+1])++j;
if(tmp>=s[j])break;
s[cur]=s[j];cur=j;//将⼦节点j值赋给⽗节点cur（不⽤进⾏交换）
}
s[cur]=tmp;
}
void Heap_sort(int s[],int len){
//1、构建⼤根堆
for(int i=len/2;i>0;--i)Heap_Adjust(s,i,len);
//2.调整堆结构+交换堆顶元素与末尾元素
for(int i=len;i>1;--i){
swap(s[i],s[1]);
Heap_Adjust(s,1,i-1);//将[1,i-1]重新调整为⼤根堆
}
}
测试
#include<bits/stdc++.h>
using namespace std;
template<class T>
class MinHeap {
private:
T* heapArray;//存放堆数据的数组
int currentSize;//当前堆中的元素个数
int maxSize;//堆的⼤⼩
//交换位置x和位置y的元素
void swap(int x,int y){
T pas = heapArray[x];
heapArray[x]= heapArray[y];
heapArray[y]= pas;可编程序控制器原理及应用
}
//构建堆
void BuildHeap(){
cout <<"你想加⼊多少元素？"<< endl;
cout <<"你想加⼊多少元素？"<< endl;
int size;
cin >> size;
currentSize = size;
cout <<"请加⼊你的元素："<< endl;
for(int i =0; i < size; i++){
T value;
cin >> value;
heapArray[i]= value;
}
for(int i = currentSize /2-1; i >=0; i--){
SiftDown(i);
}
}
public:
//构造函数，参数n为堆的⼤⼩
MinHeap(const int n){
if(n <=0){
currentSize =0;
maxSize =0;
heapArray =new T;
return;
}
currentSize =0;
maxSize = n;
heapArray =new T[maxSize];
BuildHeap();
}
//虚析构函数
virtual~MinHeap(){
delete[]heapArray;
}
//层序遍历打印堆中元素
void print(){
for(int i =0; i < currentSize; i++){
cout << heapArray[i]<<" ";
}
}
/
/判断是否为叶结点
bool isLeaf(int pos)const{
return(pos >= currentSize /2)&&(pos < currentSize); }
//返回左孩⼦的位置
int LeftChild(int pos)const{
return2* pos +1;
}
//返回右孩⼦的位置
int RightChild(int pos)const{
return2* pos +2;
}
/
/返回⽗结点的位置
int Parent(int pos)const{
return(pos -1)/2;
}
//向堆中插⼊新元素
bool Insert(const T& newNode){
if(currentSize == maxSize){
return false;
}
heapArray[currentSize]= newNode;
SiftUp(currentSize);
currentSize++;
return true;
}
T&RemoveMin(){
if(currentSize ==0){
cout <<"Can't Delete!";
exit(1);
}
else{
swap(0,--currentSize);
if(currentSize >1){
SiftDown(0);
}
return heapArray[currentSize];
}
}
//删除给定下标元素，并记录删除的元素
bool Remove(int pos){
if((pos <0)||(pos >= currentSize)){
法律关系本座说
return false;
}
heapArray[pos]= heapArray[--currentSize];//⽤最后的元素替代被删除元素if(heapArray[Parent(pos)]> heapArray[pos]){
SiftUp(pos);
}
else{
SiftDown(pos);
}
return true;
}
//从pos开始向上调整
void SiftUp(int pos){
int temppos = pos;
南传术数
T temp = heapArray[temppos];
while((temppos >0)&&(heapArray[Parent(temppos)]> temp)){
heapArray[temppos]= heapArray[Parent(temppos)];
temppos =Parent(temppos);
}
heapArray[temppos]= temp;
}
//从pos开始向下筛选
void SiftDown(int pos){
int i = pos;
int j =LeftChild(i);
T temp = heapArray[i];
while(j < currentSize){
if((j < currentSize -1)&&(heapArray[j]> heapArray[j +1])){
j++;
}
if(temp > heapArray[j]){
heapArray[i]= heapArray[j];
i = j;
j =LeftChild(j);
}
else{
break;
}
}
heapArray[i]= temp;
}
};
int main(){
//MinHeap<int> test(100);
MinHeap<int>test(INT_MAX /8);
test.print();
test.Remove(2);//删除下标为⼏的数
cout<<""<<endl;
test.RemoveMin();
test.print();
}
1 素数合数
1.1 埃拉托斯特尼筛法
/*
|埃式筛法|
|快速筛选素数|
*/
int prime[maxn];
bool is_prime[maxn];
int sieve(int n){
int p =0;
for(int i =0; i <= n;++i)
is_prime[i]=true;
is_prime[0]= is_prime[1]=false;
for(int i =2; i <= n;++i){// 注意数组⼤⼩是n
if(is_prime[i]){
prime[p++]= i;
for(int j = i + i; j <= n; j += i)// 轻剪枝，j必定是i的倍数 is_prime[j]=false;
}
}
return p;// 返回素数个数
加密代理}
1.2 合数分解
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议