算法

高精度 # 加法 # //初始条件：a:存储第一个大数(正序),b:存储第二个大数(正序),c:存储结果(逆序) int a[N],b[N],c[N];//1~N,0号位存储数组长度 void g_add(int* A,int* B,int* C){ C[0] = 1;//数组长度,从第一位开始 int t = 0;//保存进位和结果信息 for(int i = A[0],j = B[0];i > 0 || j > 0;--i,--j,++C[0]){ t += i > 0 ? A[i] : 0; t += j > 0 ? B[j] : 0; C[C[0]] = t % 10; t /= 10; } C[C[0]] = t ? t : C[--C[0]];//如果最高位进位,则将进位信息保存,否则长度-1(循环导致长度+1) } 减法 # //初始条件：a:存储第一个大数(正序),b:存储第二个大数(正序),c:存储结果(逆序),f:确定正负 int a[N],b[N],c[N],f;//1~N,0号位存储数组长度 int g_cmp(int* A,int* B){//A>=B返回1,否则返回0 if(A[0] != B[0]) return A[0] > B[0]; for(int i = 1;i <= A[0];++i) if(A[i] != B[i]) return A[i] > B[i]; return 1; } void g_sub(int* A,int* B,int* C){ C[0] = 1; int t = 0;//存储借位和结果信息 for(int i = A[0],j = B[0];i > 0 || j > 0;--i,--j,++C[0]){ t = i > 0 ? A[i] - t : t; t -= j > 0 ? B[j] : 0; C[C[0]] = (t + 10) % 10; t = t < 0 ? 1 : 0; } while(C[0] > 1 && !C[--C[0]]);//删除前导0 } int main(){ ~~~ if((f = g_cmp(a,b))) g_sub(a,b,c); else g_sub(b,a,c); cout << (f ? "" : "-"); ~~~ return 0; } 乘法 # //初始条件：a:存储第一个大数(正序),b:存储第二个大数(正序),c:存储结果(逆序) int a[N],b[N],c[2*N];//1~N,0号位存储数组长度 void g_mul(int* A,int* B,int* C){ C[0] = A[0] + B[0];//长度多一位,方便判断结果为0的情况 for(int i = A[0];i > 0;--i) for(int j = B[0];j > 0;--j) C[C[0]-i-j+1] += A[i] * B[j];//逆序放置结果 for(int i = 1;i < C[0]-1;++i){//处理每一位进位 C[i+1] += C[i] / 10; C[i] %= 10; } while(C[0] > 1 && !C[--C[0]]);//结果为0时删除多余0 } 除法 # //初始条件：a:存储第一个大数(正序),b:存储第二个大数(正序),c:存储结果(逆序),r:存储余数(正序) int a[N],b[N],c[N],r[N];//1~N,0号位存储数组长度 void g_div(int* A,int* B,int* C,int* R){ if(!g_cmp(A,B)) {//如果B比A大，则直接商0,余数就是A C[0] = 1; for(int i = 0;i <= A[i];++i) R[i] = A[i]; return; } int T[A[0]+1] = {0};//商的结果 C[0] = A[0] + 1;//商的位数预处理和被除数相同 for(int i = A[0];i > 0;--i){ T[++T[0]] = A[A[0]-i+1]; while(g_cmp(T,B)){ ++C[i]; g_sub(T,B,R); if(!R[R[0]==1]) T[0] = 0; else{ for(int j = R[0];j > 0;--j) T[R[0]-j+1] = R[j]; T[0] = R[0]; } } while(T[1] == 0 && T[0] > 0) --T[0]; } while(C[0] > 1 && !C[--C[0]]); for(int i = 0;i <= T[0];++i) R[i] = T[i]; if(T[0] == 0) R[0]= 1; } 数学 # 质数筛法 # //p:存储质数,idx:p的指针,vis:存储当前元素是否被访问 int p[N],idx,vis[N]; void get_primes(int x){ for(int i = 2;i <= x;++i){ if(!vis[i]) p[idx++] = i; for(int j = 0;p[j] <= x/i;++j){ vis[p[j]*i] = 1; if(i % p[j] == 0) break; } } } 高斯消元 # const double eps = 1e-6;//精度判断(是否为0) double a[N][N];//存储方程组矩阵 int gauss(){ int r,c;//行,列 for(c = 0,r = 0;c < n;++c){//系数矩阵第一列开始，遍历到最后一列 int t = r;//记录当前列绝对值最大值所在行 for(int i = r;i < n;++i) if(fabs(a[i][c]) > fabs(a[t][c])) t = i; if(fabs(a[t][c]) < eps) continue;//如果当前为0,则直接进入下一列,利用eps防止c++小数精度问题 for(int i = c;i <= n;++i) swap(a[t][i],a[r][i]);//交换当前行与当前列最大值所在的行 for(int i = n;i >= c;--i) a[r][i] /= a[r][c];//当前行当前列元素置为1,当前行其余元素也要更新,防止影响当前元素,逆序遍历 for(int i = r+1;i < n;++i)//从下一行开始,更新当前列的下面所有行的值为0,更新当前行下面的所有行 if(fabs(a[i][c]) > eps)//当前元素不是0 for(int j = n;j >= c;--j)//逆序计算 a[i][j] -= a[r][j] * a[i][c]; ++r;//如果当前行列不为0,则计算到这里,行数加一,否则就是当前行的下一列开始计算 } if(r < n){//矩阵不满秩 for(int i = r;i < n;++i)//判断是否存在系数为0,常s if(fabs(a[i][n]) > eps) return 2;//无解 return 1;//无穷多解 } for(int i = n-1;i >= 0;--i)//最后一行开始 for(int j = i+1;j < n;++j)//当前行所在对角线的后面所有列 a[i][n] -= a[i][j] * a[j][n];//存储最后结果(当前行其他列全部消为0) return 0;//唯一解 } //使用方式 int t = gauss(); if(t == 0) for(int i = 0;i < n;++i) cout << fixed << setprecision(2) << (fabs(a[i][n]) < eps ? 0 : a[i][n]) << endl;//防止输出-0.00 else if(t == 1) cout << "无穷多解" << endl; else cout << "无解" << endl; 快速幂 # int qmi(int a,int k,int p){ int ret = 1; while(k){ if(k & 1) ret = (LL) ret * a % p; a = (LL) a * a % p; k >>= 1; } return ret; } 最大公约数 # int gcd(int x,int y){ return y ? gcd(y,x%y) : x; } 二分查找 # // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid;//最左边的结果 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid;//最右边的结果 else r = mid - 1; } return l; } 字符串 # 读取整行字符 # //如果读取该行前有读取其他字符或者换行，则需要多加一个getline(cin,s);读取上一行遗留的换行符 getline(cin,s);//会读取一整行包括空格和换行符，但是会自动删去换行符 分割字符串 # //构造原始字符串s的字符串流 stringstream ssin(s); //以delim作为分割符,分割后的字符串存储到t中 string t; while(getline(ssin,t,'delim')){...} 图 # 基本操作 # int h[N],e[N],ne[N],idx; void add(int a,int b){//a->b e[idx] = b;ne[idx] = h[a];h[a] = idx++; } memset(h,-1,sizeof h);//初始化头节点为-1 for(int i = h[a];~i;i = ne[i]){...}//遍历邻接表 边多就用for循环，邻接矩阵存储。边少就用堆优化，连接表存储。