自定义函数库

求两点距离

double dis(double x1, double y1, double x2, double y2){
	return sqrt(pow(x2-x1, 2)+pow(y2-y1, 2));
}

判断闰年

bool isLeapYear(int year){
	return year%4==0 && year%100!=0 || year%400==0;
}

判断素数

bool isPrime(int num){
	if(num<2) return false;
	for(int i=2; i*i<=num; i++){
		if(num%i == 0) return false; 
	}
	return true;
} 

埃氏筛素数

const int N=1e5+1;
bool is_prime[N];
void func(){
	memset(is_prime, true, sizeof(is_prime));
	is_prime[0]=is_prime[1]=false;
	for(int i=2; i*i<=N; i++){
		if(is_prime[i]){
			for(int j=i*i; j<=N; j=j+i){
				is_prime[j]=false;
			}
		}
	}
}

冒泡排序

const int N=101;
int n, arr[N];
void bubbleSort() {
	for(int i=0; i<n-1; i++) {//比较趟数 
		bool flag = 1;
		for(int j=0; j<n-i-1; j++) { 
			if(arr[j] > arr[j+1]) {
				swap(arr[j], arr[j+1]);
				flag = 0;
			}
		}
		if(flag) break;
	}
}

插入排序

const int N=101;
int n, arr[N];
void insertSort() {
	for(int i=1; i<n; i++) {//arr[i]当前需要插入的元素
		int base=arr[i], j; 
		for(j=i-1; j>=0; j--) {
			if(arr[j]>base) {
				arr[j+1]=arr[j];
			}else break;
		}
		arr[j+1]=base;
	}
}

选择排序

const int N=101;
int n, arr[N];
void selectSort() {
	for(int i=0; i<n-1; i++) {//i：当次排序元素应该在的位置 
		int minIndex=i;
		for(int j=i+1; j<n; j++) {
			if(arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}
		swap(arr[minIndex], arr[i]);
	}
}

归并排序

const int N=101;
int n, arr[N], tmp[N];
void mergeSort(int left, int right){
	int mid=(left+right)/2;
	if(left<mid) partition(left, mid);
	if(mid+1<right) partition(mid+1, right);
	int i=left, j=mid+1, t=0;
	while(i<=mid && j<=right){
		if(arr[i] < arr[j]) tmp[t++] = arr[i++];
		else tmp[t++] = arr[j++];
	}
	while(i<=mid) tmp[t++] = arr[i++];
	while(j<=right) tmp[t++] = arr[j++];
	for(int i=0; i<t; i++) arr[i+left] = tmp[i];
}

快速排序

const int N=101;
int n, arr[N];
void quickSort(int left, int right){
	int num = arr[left], i=left, j=right;
	while(i<j){
		while(i<j && arr[j]>=num)  j--;
		arr[i]=arr[j];
		while(i<j && arr[i]<=num)i++;
		arr[j]=arr[i];
	}
	arr[i]=num;
	if(left<i-1) quickSort(left, i-1);
	if(i+1<right) quickSort(i+1, right); 
}

排列-n个数中抽m个进行全排列

const int N=10;
int n, m, arr[N], box[N]; 
bool vis[N];
void dfs(int pos){
	if(pos==m){
		for(int i=0; i<m; i++) cout<<box[i]<<" ";
		cout<<endl;
		return;
	}
	for(int i=0; i<n; i++){
		if(!vis[i]){
			vis[i]=true;
			box[pos]=arr[i];
			dfs(pos+1);
			vis[i]=false;
		}
	}
}

组合-n个数中抽m个进行组合

const int N=10;
int n, m, arr[N], box[N]; 
bool vis[N];
void dfs(int idx, int pos){
	if(pos==m){
		for(int i=0; i<m; i++) cout<<box[i]<<" ";
		cout<<endl;
		return;
	}
	for(int i=idx; i<n; i++){
		if(!vis[i]){
			vis[i]=true;
			box[pos]=arr[i];
			dfs(i+1, pos+1);
			vis[i]=false;
		}
	}
}

高精度数加法

string add(string a, string b) {
	int lena=a.length(), lenb=b.length(), a1[1005]= {}, b1[1005]= {};
	for(int i=0; i<lena; i++) a1[lena-1-i] = a[i]-'0';
	for(int i=0; i<lenb; i++) b1[lenb-1-i] = b[i]-'0';
	int lenc=lena>lenb?lena:lenb, c1[1005]= {}, carry=0;
	for(int i=0; i<lenc; i++) {
		c1[i]=a1[i]+b1[i]+carry;
		carry=c1[i]/10;
		c1[i]%=10;
	}
	if(carry>0) c1[lenc++]=carry;
	string res="";
	for(int i=lenc-1; i>=0; i--) res += c1[i]+'0';
	return res;
}

高精度数减法

string sub(string a, string b) {
	bool f=true; //标记a和b的大小关系，默认a大 
	int lena=a.length(), lenb=b.length();
	if(lena<lenb || lena==lenb && a<b){
		f=false;
		swap(a, b);
		swap(lena, lenb);
	} 
	int a1[1005]= {}, b1[1005]= {};
	for(int i=0; i<lena; i++) a1[lena-1-i] = a[i]-'0';
	for(int i=0; i<lenb; i++) b1[lenb-1-i] = b[i]-'0';
	int c1[1005]= {}, lenc=lena;
	for(int i=0; i<lenc; i++) {
		if(a1[i]<b1[i]){
			a1[i+1]--;
			a1[i]+=10;
		} 
		c1[i]=a1[i]-b1[i];
	}
	while(lenc>1 && c1[lenc-1]==0) lenc--; 
	string res="";
	if(f==false) res+='-';
	for(int i=lenc-1; i>=0; i--) res += c1[i]+'0';
	return res;
}

高精度数乘法，大数乘大数

string mul1(string a, string b) {
	int lena=a.length(), lenb=b.length(), a1[1005]= {}, b1[1005]= {};
	for(int i=0; i<lena; i++) a1[lena-1-i] = a[i]-'0';
	for(int i=0; i<lenb; i++) b1[lenb-1-i] = b[i]-'0';
	int lenc=lena+lenb, c1[2005]= {}, carry;
	for(int i=0; i<lenb; i++) {
		carry=0;
		for(int j=0; j<lena; j++) {
			c1[i+j]+=a1[j]*b1[i]+carry;
			carry = c1[i+j]/10;
			c1[i+j]%=10;
		}
		c1[i+lena]=carry;
	}
	while(lenc>1 && c1[lenc-1]==0) lenc--;
	//保存运算结果
	string res="";
	for(int i=lenc-1; i>=0; i--) res += c1[i]+'0';
	return res;
}

高精度数乘法，大数乘小数

string mul2(string a, int b){
    int lena=a.length(), a1[1005]={};
    for(int i=0; i<lena; i++) a1[lena-1-i]=a[i]-'0';
    int lenc=lena, c1[2005]={}, carry=0;
    for(int i=0; i<lenc; i++){
        c1[i] = a1[i]*b+carry;
        carry = c1[i]/10;
        c1[i] %= 10;
    }
    while(carry){
        c1[lenc++]=carry%10;
        carry/=10;
    }
	string res="";
    for(int i=lenc-1; i>=0; i--) res+=c1[i]+'0';
    return res;
}