自定义函数库

求两点距离

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;
}