Programming Contest Archive

# find solutions in Rustfind. -name"*.rs"# find solutions in Cfind. -name"*.c"

Handy templates in Rust

#[allow(unused_imports)]use std::cmp::max;#[allow(unused_imports)]use std::cmp::min;#[allow(unused_imports)]use std::collections::HashMap;#[allow(unused_imports)]use std::collections::HashSet;use std::io;// input macros#[allow(unused_macros)]// rustc +nightly -Zunpretty=expanded your.rsmacro_rules! read{// eg.// let s = read!();() =>{{letmut line:String =String::new();        io::stdin().read_line(&mut line).unwrap();        line.trim().to_string()}};// eg.// let v = read!(Vec<i32>)// let v = read!(Vec<char>)(Vec<$t:ty>) =>({letmut line:String =String::new();        io::stdin().read_line(&mut line).unwrap();        line.split_whitespace().map(|x| x.parse::<$t>().unwrap()).collect()});// eg.// let v = read!(i32);// let v = read!(i64);// let (i, j, k) = read!(i32, i32, i32);($($t:ty),*) =>{{letmut line =String::new();        io::stdin().read_line(&mut line).unwrap();letmut iter = line.split_whitespace();($(iter.next().unwrap().parse::<$t>().unwrap()),*)}};}fnsolve(){}fnmain(){letmut t =read!(i32);while t >0{        t -=1;solve();print!("\n");}}

Handy templates in C

1. printf

1.1 符号说明

      %a(%A)     浮点数、十六进制数字和p-(P-)记数法(C99)      %c         字符      %d         有符号十进制整数      %f         浮点数(包括float和double)      %e(%E)     浮点数指数输出[e-(E-)记数法]      %g(%G)     浮点数不显无意义的零"0"      %i         有符号十进制整数(与%d相同)      %u         无符号十进制整数      %o         八进制整数    e.g.     0123      %x(%X)     十六进制整数0f(0F)   e.g.   0x1234      %p         指针      %s         字符串      %%         "%"

1.2 对齐

      左对齐："-"   e.g.   "%-20s"      右对齐："+"   e.g.   "%+20s"      空格：若符号为正，则显示空格，负则显示"-"   e.g.   "%  6.2f"            #：对c,s,d,u类无影响；对o类，在输出时加前缀o；对x类，在输出时加前缀0x；对e,g,f 类当结果有小数时才给出小数点

1.3 格式化输出

 ［标志］［输出最少宽度］［．精度］［长度］类型  "％-md" ：左对齐，若m比实际少时，按实际输出。  "%m.ns"：输出m位，取字符串(左起)n位，左补空格，当n>m or m省略时m=n.  e.g. "%7.2s"输入CHINA                                 　     输出"     CH"  "%m.nf"：输出浮点数，m为宽度，n为小数点右边数位           e.g. "%3.1f"   输入3852.99                                       输出3853.0

2. 符号的英文读法

+　 plus　加号；正号-　 minus　减号；负号±　plus or minus　正负号×　is multiplied by　乘号÷　is divided by　除号＝　is equal to　等于号≠　is not equal to　不等于号≡　is equivalent to　全等于号≌　is equal to or approximately equal to　等于或约等于号≈　is approximately equal to　约等于号＜　 is less than　小于号＞　is greater than　大于号≮　is not less than　不小于号≯ 　is not more than　不大于号≤　is less than or equal to　小于或等于号≥　is more than or equal to　大于或等于号%　 per cent　百分之…‰　per mill　千分之…∞　 infinity　无限大号∝　varies as　与…成比例√　(square) root　平方根∵　since; because　因为∴　hence　所以∷　equals, as (proportion)　等于，成比例∠　angle　 角⌒　semicircle　半圆⊙　circle　圆○　circumference　圆周π　pi 圆周率△ 　triangle　三角形⊥　perpendicular to　垂直于∪　union of　并，合集∩　 intersection of 交，通集∫　the integral of …的积分∑　(sigma) summation of　总和°　degree　度′　minute　分″　second　秒℃　Celsius system　摄氏度{ 　open brace, open curly　左花括号}　close brace, close curly　右花括号(　 open parenthesis, open paren　左圆括号)　close parenthesis, close paren　右圆括号() brakets/ parentheses　括号[　open bracket 左方括号]　 close bracket 右方括号[] square brackets　方括号.　period, dot　句号，点|　 vertical bar, vertical virgule　竖线&　ampersand, and, reference, ref　和，引用*　asterisk, multiply, star, pointer　星号，乘号，星，指针/　slash, divide, oblique 斜线，斜杠，除号//　slash-slash, comment 双斜线，注释符#　pound　井 号\　backslash, sometimes escape　反斜线转义符，有时表示转义符或续行符~　tilde　波浪符. 　full stop　句号,　comma　逗号:　colon　冒号;　semicolon　分号?　 question mark　问号!　exclamation mark (英式英语) exclamation point (美式英语)‘ 　apostrophe　撇号-　hyphen　连字号– dash 破折号…　dots/ ellipsis　省略号" 　single quotation marks 单引号""　double quotation marks 双引号‖ parallel 双线号&　ampersand = and～　swung dash 代字号§　section; division 分节号→　arrow 箭号；参见号

3. C/C++头文件

///C#include<assert.h>//断言#include<ctype.h>//字符处理#include<errno.h>//定义错误码#include<float.h>//浮点数处理#include<limits.h>//定义各种数据类型最值常量#include<locale.h>//定义本地化函数#include<math.h>//定义数学函数#include<setjmp.h>//非局部跳转#include<signal.h>//信号处理#include<stdarg.h>//变长变元表#include<stddef.h>#include<stdio.h>//定义输入／输出函数#include<stdlib.h>//定义杂项函数及内存分配函数#include<string.h>//字符串处理#include<time.h>//定义关于时间的函数//////////////////////////////////////////////////////////////////////////////////标准 C++///C语言部分略#include<algorithm>//STL 通用算法#include<bitset>//STL 位集容器#include<complex>//复数类#include<deque>//STL 双端队列容器#include<exception>//异常处理类#include<fstream>//文件输入/输出#include<functional>//STL 定义运算函数（代替运算符）#include<limits>#include<list>//STL 线性列表容器#include<map>//STL 映射容器#include<iomanip>#include<ios>//基本输入／输出支持#include<iosfwd>//输入／输出系统使用的前置声明#include<iostream>#include<istream>//基本输入流#include<ostream>//基本输出流#include<queue>//STL 队列容器#include<set>//STL 集合容器#include<sstream>//基于字符串的流#include<stack>//STL 堆栈容器　　　　#include<stdexcept>//标准异常类#include<streambuf>//底层输入／输出支持#include<string>//字符串类#include<utility>//STL 通用模板类#include<vector>//STL 动态数组容器#include<cwchar>#include<cwctype>usingnamespacestd;//////////////////////////////////////////////////////////////////////////C99 增加#include<complex.h>//复数处理#include<fenv.h>//浮点环境#include<inttypes.h>//整数格式转换#include<stdbool.h>//布尔环境#include<stdint.h>//整型环境#include<tgmath.h>//通用类型数学宏///////////////////////////////////////////////////////////////////////

4. 注意事项

5. N次方求和

6. 字符串处理

/** *颠倒一个字符串的顺序 "abc\0" – "cba\0" *array为需要颠倒顺序的字符串 *length 为字符串array的长度 */intstringReverse(char*array,intlength){inti=0,j=length-1;while(i<j){charcha=array[i];array[i]=array[j];array[j]=cha;i++;j--;    }return1;}

// 颠倒一个字符串部分位置的顺序, 原地inlinevoidswap(char*x,char*y) {chart=*x;*x=*y;*y=t;}char*reverse(char*buffer,inti,intj){while (i<j)swap(&buffer[i++],&buffer[j--]);returnbuffer;}

// 反转整数#include<stdio.h>#include<stdlib.h>#defineINF_MAX 0x7fffffff#defineINF_MIN -0x7fffffff-1intreverse(intx){intans=0;intl=x;while(l!=0 ) {inth=l%10;l=l/10;// ans * 10 + h > INF_MAX// ans * 10 + h < INF_MINif(INF_MAX/10<ans|| (INF_MAX/10==ans&&h>7)) {return0;        }elseif(INF_MIN/10>ans|| (INF_MIN/10==ans&&h<-8)) {return0;        }ans=ans*10+h;    }returnans;}intmain() {printf("%d\n",reverse(123));printf("%d\n",reverse(-123));return0;}

// 最长回文子串, 暴力解法// 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。//// 示例 1：//// 输入: "babad"// 输出: "bab"// 注意: "aba" 也是一个有效答案。// 示例 2：//// 输入: "cbbd"// 输出: "bb"#include<stdio.h>#include<stdlib.h>#include<string.h>intvalid(char*s,inti,intj) {while(i <=j) {if(s[i++]!=s[j--]) {return0;        }    }return1;}char*longestPalindrome(char*s){intlen=strlen(s);if (len==1) {returns;    }intmax=1,maxi=0;for(inti=0;i<len-1;i++) {for(intj=i+1;j<len;j++) {intx=j-i+1;if(x>max&&valid(s,i,j)) {if(x>max) {max=x;maxi=i;                }            }        }    }s=s+maxi;s[max]='\0';returns;}intmain() {chara[10]="babad";printf("%s\n",longestPalindrome(a));return0;}

7. 进制转换

/** *将任意进制数转换成整型范围内的十进制数 *str   为base进制数 *base  为str的进制 *length为str的长度 */intmyPow(inta,intb){intrs=1;while(b--){rs *=a;}returnrs;}intanyToDecimal(char*str,intbase,intlength){intdecimal=0,i;for(i=0;i<length;i++){if(str[i] >=65)/*为十六进制的时候*/{decimal+=myPow(base,length-1-i)*(str[i]-'A'+10);}elseif(str[i] <='9'){decimal+=myPow(base,length-1-i)*(str[i]-'0');}}returndecimal;}

8. 栈

/** *栈 C++ *clear() push() top() empty() pop() size() *free()*/typedefint T;structmyStack{int curr,size_limit;    T *array;myStack(int s){//必须传入栈的大小        curr = -1; size_limit = s;        array =new T[s];    }voidclear(){curr = -1;}/*清空栈 重新使用*/voidfree(){delete array;clear();}/*释放栈 不能再使用*/    Ttop(){if(curr > -1){return array[curr];}elsereturn curr;}boolpush(T v){if(curr+1 < size_limit){array[++curr] = v;returntrue;}returnfalse;}boolempty(){if(curr <0)returntrue;elsereturnfalse;}voidpop(){curr--;}intsize(){return curr+1;}};

// c stack 没有安全检查, 使用时自己注意#include<stdio.h>#include<stdlib.h>typedefintT;structstack {T*values;intpos,size;};voidinit_stack(structstack*s,intsize) {s->pos=0;s->size=size;s->values=malloc(sizeof(T)*size);}structstack*create(intsize) {structstack*p=malloc(sizeof(structstack));init_stack(p,size);returnp;}voiddelete (structstack*s) {free(s->values); }// not safevoidpush(structstack*s,Tv) {s->values[s->pos++]=v; }voiddump(structstack*s) {printf("[%p",s->values[0]);inti=1;while(i<s->pos) {printf(", %p",s->values[i++]);   }printf("]\n");}intempty(structstack*s) {returns->pos==0; }intfull(structstack*s) {returns->pos >=s->size; }structT*pop(structstack*s) {returns->values[--s->pos]; }structT*top(structstack*s) {returns->values[s->pos-1]; }intmain() {structstack*s=create(10);push(s,1);dump(s);delete (s);}

8. 表达式转换

/***自己定义操作符的优先级*/intpriorityLevel(constchar x){}/***自己定义操作符的结合性，左或者右*/intrightAssociative(constchar x){switch(x){case'^':{return1;}    }return0;}/***shunting_yard: infix expression to RPN*中缀转换成后缀*传入中缀表达式expression，RPN保存在result中*/voidshunting_yard(char *result,constchar *expression){    stack<char> my;int len =strlen(expression), r =0;for(int  i =0;i < len;i++){if(expression[i] =='')continue;if(expression[i] >='0' && expression[i] <='9'){//是数字直接加到输出队列            result[r++] = expression[i];        }else{//操作符或者括号///以下代码需要根据具体情况修改///需要注意操作符的优先级和结合性if(r !=0 && result[r-1] !='') result[r++] ='';//数字之间必须要用空格隔开if(expression[i] ==')'){while(!my.empty() && my.top() !='('){//遇到右括号的时候 要将括号里边的表达式看成一个整体//将左括号之后的内容都弹出                    result[r++] = my.top(); my.pop();                }if(!my.empty()) my.pop();//弹出左括号            }else{while(expression[i] !='('//左括号直接入栈                    &&!my.empty()//栈为空的时候也直接入栈///如果是操作符 需要弹出栈里优先级比它高 或者 优先级相等但是是左结合的操作符                    && my.top() !='('//遇到左括号相当于栈为空                    && (                        (priorityLevel(my.top()) >priorityLevle(expression[i]))                  ||(priorityLevel(my.top())==priorityLevle(expression[i])&& !rightAssociative(my.top()))                       )                    ){                    result[r++] = my.top(); my.pop();                }                my.push(expression[i]);//将这个操作符入栈            }        }    }while(!my.empty()){        result[r++] = my.top(); my.pop();    }    result[r] ='\0';}

9. 搜索

/** *二分查找 *如果找到flag为1 posi为所查找到的位置 *如果没找到flag为0 posi为该值应该插入的位置 *传入的区间为[left,right) */structnode{intflag;//0表示不存在intposi;//返回插入或者删除的位置};structnode*binarySearch(int*array,intvalue,intleft,intright){structnode*pointer= (structnode*)malloc(sizeof(structnode));pointer->flag=0;pointer->posi=-1;if(right==0){//left == -1 impossiblepointer->flag=pointer->posi=0;returnpointer;    }while(left <=right){intmid= ((left+right) >>1);if(value==array[mid]){pointer->flag=1;pointer->posi=mid;returnpointer;        }else{(value>array[mid])?(left=mid+1):(right=mid-1);}}pointer->posi=left;returnpointer;}

10. 排序

/** * 二叉排序树模板 * 插入函数 插入之前应先申请一个要插入的p节点 然后传进去 * 查找函数 root为根节点 parent等于root value为要查找的值 * ret_flag为0返回查找到的节点的父节点这样便于删除时使用  ret_flag * 为1返回查找到的节点的指针 * 删除函数 传入要删除的节点的父节点和要删除的节点 * 如果待删节点为父节点的左孩子is_left=1 如果为右孩子 is_left=1 构造函数 * 将一个数组从start到end（不包括end）的范围构造为一个二叉排序树 root为根节点 */#include<stdio.h>#include<stdlib.h>structnode {intvalue;structnode*left,*right;};structnode*bst_insert(structnode*curr,structnode*p) {if (curr==NULL) {returnp;//插入的节点的左右孩子的初始值一定要为NULL  }elseif (p->value<curr->value) {curr->left=bst_insert(curr->left,p);  }else {curr->right=bst_insert(curr->right,p);  }returncurr;}voidbst_inorder_traversal(structnode*curr) {if (curr!=NULL) {bst_inorder_traversal(curr->left);printf("(%p, %d)\n",curr,curr->value);bst_inorder_traversal(curr->right);  }}voidbst_preorder_traversal(structnode*curr) {if (curr!=NULL) {printf("(%p, %d)\n",curr,curr->value);bst_preorder_traversal(curr->left);bst_preorder_traversal(curr->right);  }}voidbst_postorder_traversal(structnode*curr) {if (curr!=NULL) {bst_postorder_traversal(curr->left);bst_postorder_traversal(curr->right);printf("(%p, %d)\n",curr,curr->value);  }}structnode*bst_search(structnode*curr,structnode*parent,intvalue,intret_flag) {if (curr==NULL) {// leaf nodereturnNULL;  }elseif (curr->value==value) {// found, check ret flag// 返回的是要查找节点的父节点或者是要查找的节点// 使用父节点是因为这样便于删除的时候使用父节点进行删除if (ret_flag==0) {returnparent;    }else {returncurr;    }  }elseif (value<curr->value) {returnbst_search(curr->left,curr,value,ret_flag);  }else {returnbst_search(curr->right,curr,value,ret_flag);  }}intbst_delete(structnode*parent,structnode*p,intis_left) {if (p->left==NULL&&p->right==NULL) {// leaft nodeif (is_left) {// p 为parent的左子叶// 将 parent的左指针置为空parent->left=NULL;    }else {// p 为parent的右子叶parent->right=NULL;    }free(p);  }elseif (p->left==NULL) {// 待删除节点无左子树，说明有右子树if (is_left) {// 将待删除的节点的右子树 赋值给父节点的左子树parent->left=p->right;    }else {// 将待删除的节点的右子树 赋值给父节点的左子树parent->right=p->right;    }free(p);  }elseif (p->right==NULL) {// 待删除节点无右子树，说明有左子树if (is_left) {parent->left=p->left;    }else {parent->right=p->left;    }free(p);  }else {structnode*s=p->right;structnode*sp=p;//找右子树中最左的节点 或者找左子树中最右的节点//然后和要删除的位置交换value//这里选择前者while (s->left!=NULL) {sp=s;s=s->left;    }printf("%d --> %d\n",p->value,s->value);p->value=s->value;if (sp==p) {// p 的右子树没有左子树sp->right=s->right;    }else {//因为s肯定没有左子树 所以把右子树接在父节点的左指针上就行了sp->left=s->right;    }free(s);  }return1;}voidbst_build(structnode*root,int*array,intstart,intend) {// [start, end)while (start<end) {// create nodestructnode*p=malloc(sizeof(structnode));p->value=array[start];p->left=p->right=NULL;// initbst_insert(root,p);start++;  }}intmain() {inta[10]= {1,450,3,4,56,12,123,45,23,6};structnode*root=malloc(sizeof(structnode));root->left=root->right=NULL;root->value=a[0];bst_build(root,a,1,10);bst_inorder_traversal(root);printf("root %p %d\n",root,root->value);structnode*ans=bst_search(root,root,56,0);if (ans!=NULL) {printf("ans value %d\n",ans->value);bst_delete(ans,ans->right,1);bst_preorder_traversal(root);bst_inorder_traversal(root);bst_postorder_traversal(root);  }}

/** *quickSort , 快速排序，传入要排序的数组和需要排序的范围[left, right] *从小到大*/voidquickSort(int left,int right,int array[]){int i = left,j = right,x = array[(left+right)/2];do{while(array[i] < x)i++;while(array[j] > x)j--;//使左边的值都比右边的小if(i <= j) {std::swap(array[i++],array[j--]);}    }while(i < j);//i >= jif(i < right)quickSort(i,right,array);if(j > left)quickSort(left,j,array);}

/** *heapSort 堆排序模板 （大根堆） */intmySwap(int*a,int*b){if(a==b)return;(*a)= (*a) ^ (*b);(*b)= (*a) ^ (*b);(*a)= (*a) ^ (*b);return1;}intsift(intarray[],intk,intm)//one-based{//把k到m范围内的值调整为大根堆inti=k,j=i<<1;//置i为要筛的节点 j 为i的左孩子while(j <=m){//仍然在范围之内if(j<m&&array[j]<array[j+1]){//右孩子存在 且左孩子小于右孩子j++;//因为要建大根堆 所以选择孩子中较大者进行交换        }if(array[i]>array[j]){break;//不需要再向下比较 因为之前也是调整过的大根堆        }else{mySwap(&array[i],&array[j]);i=j;j= (i<<1);//被筛节点移动到j节点 计算左孩子        }    }return1;}intheapSort(intarray[],intn){// one-based 从1开始保存的 到n结束 left_child = 2*parentinti;for(i=n>>1;i >=1;i--){sift(array,i,n);//初始建堆 从 最后一个非终端节点到 1    }for(i=1;i<n;i++){//重复执行移走堆顶并重建堆的操作mySwap(&array[1],&array[n-i+1]);//从n到2 不断和堆顶交换 one-basedsift(array,1,n-i);//重建堆    }return1;}

11. 递归

/** *汉诺塔 递归实现 */intmove(intn,charx,chary){printf("move %d from %c to %c\n",n,x,y);//输出移动过程return1;}inthanoi(intn,chara,charb,charc){//将n个盘子借助b从a移动到cif(n==1){move(1,a,c);}else{hanoi(n-1,a,c,b);//把n-1个盘子借助c从a移动到bmove(n,a,c);//把第n个盘子从a移动到chanoi(n-1,b,a,c);//将n-1个盘子借助a从b移动到c    }return1;}

12. 链表

/** *构建一个未赋值的循环单链表 至少有头和尾两个节点 */structnode{intvalue;structnode*next;};structnode*constructRecurrentSingleChain(intstart,intend){structnode*head= (structnode*)malloc(sizeof(structnode));structnode*tail= (structnode*)malloc(sizeof(structnode));head->next=tail;tail->next=head;//head->value= -1;//tail->value= -1;while(start!=end){structnode*new_node= (structnode*)malloc(sizeof(structnode));//new_node->value     = start;根据具体情况进行赋值new_node->next=head;tail->next=new_node;tail=new_node;start++;    }returnhead;}

/** *构建未赋值的循环双链表 至少有头和尾两个节点 */structnode{intvalue;structnode*prev;structnode*next;};structnode*constructRecurrentDoubleChain(intstart,intend){structnode*head= (structnode*)malloc(sizeof(structnode));structnode*tail= (structnode*)malloc(sizeof(structnode));head->prev=tail;head->next=tail;tail->next=head;tail->prev=head;//head->value= -1;//tail->value= -1;while(start!=end){structnode*new_node= (structnode*)malloc(sizeof(structnode));//new_node->value       = start;tail->next=new_node;head->prev=new_node;new_node->prev=tail;new_node->next=head;tail=new_node;start++;    }returnhead;}

13. 大数

/** *大数的加法 乘法运算 *效率很低 不能用于算大数阶乘*/classBigInteger {public:BigInteger();BigInteger(int);BigInteger(string);boolDisplay();friend BigIntegeroperator +(const BigInteger&,const BigInteger&);friend BigIntegeroperator *(const BigInteger&,const BigInteger&);friend ostream&operator<<(std::ostream&,BigInteger&);private:staticconstint max_len =100000;public:int len;int array[max_len]; };  BigInteger:: BigInteger(){memset(array,0,sizeof(array));//或者将sizeof(array) 换成 max_len*4     len =0; } BigInteger:: BigInteger(string digit){memset(array,0,sizeof(array));     len = digit.size();for(int i =0;i < len;i++){         array[i] = digit[len - i -1] -'0';     } } BigInteger:: BigInteger(int digit){memset(array,0,sizeof(array));if(digit ==0)len =1;elselen =0;while(digit !=0){         array[len++] = digit %10;         digit        = digit /10;     } }bool BigInteger:: Display(){for(int i = len -1;i >=0;i--) cout << array[i];returntrue; } std::ostream&operator<<(ostream &out, BigInteger &digit){     digit.Display();return out; } BigIntegeroperator +(const BigInteger &augend,const BigInteger &addend){     BigInteger result;     result.len =max(augend.len,addend.len);for(int i =0;i < result.len;i++)         result.array[i] = augend.array[i] + addend.array[i];for(int i=0;i < result.len;i++){if(result.array[i] >=10){             result.array[i] -=10;             result.array[i+1]++;         }     }if(result.array[result.len] >0){result.len++;}return result; } BigIntegeroperator *(const BigInteger &multiplicand,const BigInteger &multiplier) {     BigInteger result;     result.len = multiplicand.len + multiplier.len -1;for(int i =0;i < multiplicand.len;i++){for(int j =0;j < multiplier.len;j++)             result.array[i + j] += multiplicand.array[i]*multiplier.array[j];     }for(int i =0;i < result.len;i++){if(result.array[i] >9){             result.array[i+1] += result.array[i] /10;             result.array[i]   %=10;         }     }if(result.array[result.len] >0) result.len++;while(result.len >1 && result.array[result.len-1] ==0)         result.len--;//为0的时候不用去掉第一位的0return result; }

/** *n的阶乘 结果为大数，保存在array数组中 *end - 1 到 0为结果 (end-1)在前,为高位 */intfactorial(int*array,intn){intend=1;array[0]=1;for(inti=2;i <=n;i++){intr=0;for(intj=0;j<end;j++){//乘以每一位intt=array[j]*i+r;array[j]=t%10;r=t/10;        }while(r){array[end++]=r %10;r /=10;        }    }returnend;}

/** *大数模板(浙大) *注意这里的int可能会超 void div(bignum_t a,const int b,int& c) */#defineDIGIT 3//千进制#defineDEPTH1000//千进制#defineMAX     1000//位数typedefintbignum_t[MAX+1];intread(bignum_ta,istream&is=cin){charbuf[MAX*DIGIT+1],ch;inti,j;memset((void*)a,0,sizeof(bignum_t));if (!(is>>buf))return0;for (a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch;for (a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');for (i=1;i<=a[0];i++)for (a[i]=0,j=0;j<DIGIT;j++)a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0';for (;!a[a[0]]&&a[0]>1;a[0]--);return1;}voidwrite(constbignum_ta,ostream&os=cout){inti,j;for (os<<a[i=a[0]],i--;i;i--)for (j=DEPTH/10;j;j/=10)os<<a[i]/j%10;}intcomp(constbignum_ta,constbignum_tb){inti;if (a[0]!=b[0])returna[0]-b[0];for (i=a[0];i;i--)if (a[i]!=b[i])returna[i]-b[i];return0;}intcomp(constbignum_ta,constintb){intc[12]={1};for (c[1]=b;c[c[0]]>=DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);returncomp(a,c);}intcomp(constbignum_ta,constintc,constintd,constbignum_tb){inti,t=0,O=-DEPTH*2;if (b[0]-a[0]<d&&c)return1;for (i=b[0];i>d;i--){t=t*DEPTH+a[i-d]*c-b[i];if (t>0)return1;if (t<O)return0;}for (i=d;i;i--){t=t*DEPTH-b[i];if (t>0)return1;if (t<O)return0;}returnt>0;}voidadd(bignum_ta,constbignum_tb){inti;for (i=1;i<=b[0];i++)if ((a[i]+=b[i])>=DEPTH)a[i]-=DEPTH,a[i+1]++;if (b[0]>=a[0])a[0]=b[0];elsefor (;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);a[0]+=(a[a[0]+1]>0);}voidadd(bignum_ta,constintb){inti=1;for (a[1]+=b;a[i]>=DEPTH&&i<a[0];a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);for (;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);}voidsub(bignum_ta,constbignum_tb){inti;for (i=1;i<=b[0];i++)if ((a[i]-=b[i])<0)a[i+1]--,a[i]+=DEPTH;for (;a[i]<0;a[i]+=DEPTH,i++,a[i]--);for (;!a[a[0]]&&a[0]>1;a[0]--);}voidsub(bignum_ta,constintb){inti=1;for (a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);for (;!a[a[0]]&&a[0]>1;a[0]--);}voidsub(bignum_ta,constbignum_tb,constintc,constintd){inti,O=b[0]+d;for (i=1+d;i<=O;i++)if ((a[i]-=b[i-d]*c)<0)a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH;for (;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);for (;!a[a[0]]&&a[0]>1;a[0]--);}voidmul(bignum_tc,constbignum_ta,constbignum_tb){inti,j;memset((void*)c,0,sizeof(bignum_t));for (c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++)for (j=1;j<=b[0];j++)if ((c[i+j-1]+=a[i]*b[j])>=DEPTH)c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH;for (c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--);}voidmul(bignum_ta,constintb){inti;for (a[1]*=b,i=2;i<=a[0];i++){a[i]*=b;if (a[i-1]>=DEPTH)a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH;}for (;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);for (;!a[a[0]]&&a[0]>1;a[0]--);}voidmul(bignum_tb,constbignum_ta,constintc,constintd){inti;memset((void*)b,0,sizeof(bignum_t));for (b[0]=a[0]+d,i=d+1;i<=b[0];i++)if ((b[i]+=a[i-d]*c)>=DEPTH)b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH;for (;b[b[0]+1];b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);for (;!b[b[0]]&&b[0]>1;b[0]--);}voiddiv(bignum_tc,bignum_ta,constbignum_tb){inth,l,m,i;memset((void*)c,0,sizeof(bignum_t));c[0]=(b[0]<a[0]+1)?(a[0]-b[0]+2):1;for (i=c[0];i;sub(a,b,c[i]=m,i-1),i--)for (h=DEPTH-1,l=0,m=(h+l+1)>>1;h>l;m=(h+l+1)>>1)if (comp(b,m,i-1,a))h=m-1;elsel=m;for (;!c[c[0]]&&c[0]>1;c[0]--);c[0]=c[0]>1?c[0]:1;}voiddiv(bignum_ta,constintb,long long&c){inti;for (c=0,i=a[0];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);for (;!a[a[0]]&&a[0]>1;a[0]--);}voidsqrt(bignum_tb,bignum_ta){inth,l,m,i;memset((void*)b,0,sizeof(bignum_t));for (i=b[0]=(a[0]+1)>>1;i;sub(a,b,m,i-1),b[i]+=m,i--)for (h=DEPTH-1,l=0,b[i]=m=(h+l+1)>>1;h>l;b[i]=m=(h+l+1)>>1)if (comp(b,m,i-1,a))h=m-1;elsel=m;for (;!b[b[0]]&&b[0]>1;b[0]--);for (i=1;i<=b[0];b[i++]>>=1);}intlength(constbignum_ta){intt,ret;for (ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++);returnret>0?ret:1;}intdigit(constbignum_ta,constintb){inti,ret;for (ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--);returnret%10;}intzeronum(constbignum_ta){intret,t;for (ret=0;!a[ret+1];ret++);for (t=a[ret+1],ret*=DIGIT;!(t%10);t/=10,ret++);returnret;}voidcomp(int*a,constintl,constinth,constintd){inti,j,t;for (i=l;i<=h;i++)for (t=i,j=2;t>1;j++)while (!(t%j))a[j]+=d,t/=j;}voidconvert(int*a,constinth,bignum_tb){inti,j,t=1;memset(b,0,sizeof(bignum_t));for (b[0]=b[1]=1,i=2;i<=h;i++)if (a[i])for (j=a[i];j;t*=i,j--)if (t*i>DEPTH)mul(b,t),t=1;mul(b,t);}voidcombination(bignum_ta,intm,intn){int*t=newint[m+1];memset((void*)t,0,sizeof(int)*(m+1));comp(t,n+1,m,1);comp(t,2,m-n,-1);convert(t,m,a);delete []t;}voidpermutation(bignum_ta,intm,intn){inti,t=1;memset(a,0,sizeof(bignum_t));a[0]=a[1]=1;for (i=m-n+1;i<=m;t*=i++)if (t*i>DEPTH)mul(a,t),t=1;mul(a,t);}

14. 并查集

intfather[15];voidmakeSet(){for(inti=0;i <=n;i++){father[i]=i;    }}intfindSet(intx){if(x!=father[x]){father[x]=findSet(father[x]);    }returnfather[x];}voidunionSet(intx,inty){x=findSet(x);y=findSet(y);father[x]=y;}

15. 状态压缩

/** *状态压缩法求阶乘，虽然可以求但这只是状态压缩恰好的一个性质 它主要用在动态规划中 *注释里的是f[13] = f[12] + f[5] + f[9] 的工作过程，t -= t & -t 就是将最开始的t的每位1取出来，取 *出来的那位1和原来的值t异或就把那位1变成0了，有点别扭 :( */long longf[1<<20]= {};f[0]=1;//f[2^0 - 1] = f[0] = 1 (0的阶乘为1)for(inti=1;i< (1<<n);i++){// 1 到 2^n - 1for(intt=i;t>0;t-= (t&-t)){//f(01101) = f(00101) + f(01001) + f(01100)//1 t = 13//2 13 -= 1//3 12 -= 4//4 8  -= 8f[i]+=f[i ^ (t&-t)];//将某些位变为0 计算和//1 f[(01101) ^ (01101 & 10011)] = f[01100]//2 f[(01101) ^ (01100 & 10100)] = f[01001]//3 f[(01101) ^ (01000 & 11000)] = f[00101]    }}// n! = f[(1<<n)-1]

16. 树状数组

/** *一维树状数组,树状数组C[],输入的数组A[] *A[] C[]都是从1开始的 在build之前C[]初始化为0 */intlowbit(intx){returnx& (x^(x-1));//这一步是把x的二进制表示中的最低位1取出来//x   = ***100//x-1 = ***011//x ^ (x-1) = 000111//x & (x ^ (x-1)) = 000100//return x&(-x);//另一种写法//x  = ***100//-x = ---011 + 1 = ---100;//x&-x = 000100;}voidadd(inti,intv,intupper){//对A[i]进行加v操作 同时更新C//对A[i]的更新直接不要放在这里 因为build也要调用该函数while(i <=upper){C[i]+=v;i+=lowbit(i);    }}voidbuild(intbegin,intend){//根据A[begin]到A[end]构建树状数组while(begin <=end){add(begin,A[begin],end);    }}intsum(inti){//求前n项和intsum=0;while(i >=1){sum+=C[i];i-=lowbit(i);    }returnsum;}

/** *二维树状数组 *二维树状数组和一维几乎一样 */intlowbit(intx){returnx& (x^(x-1));}voidadd(inti,intj,intv,intupper){//增加intt_i,t_j;for(t_i=i;t_i <=upper;t_i+=lowbit(t_i)){for(t_j=j;t_j <=upper;t_j+=lowbit(t_j)){C[t_i][t_j]+=v;        }    }}intquery(inti,intj){//查询intsum=0,t_i,t_j;for(t_i=i;t_i>0;t_i-=lowbit(t_i)){for(t_j=j;t_j>0;t_j-=lowbit(t_j)){sum+=C[t_i][t_j];        }    }returnsum;}

17. 线段树

/** *树状数组是前序和，应用范围要窄，线段树可以求区间和、区间最大值等等 *下面是求线段树求区间和的示例，可以根据具体情况修改 */#defineMAX 100000structnode{intleft,right;long longsum,weight;}tree[MAX];intA[MAX];//MAX_nvoidbuild(inti,inta,intb){//构建线段树 i为层数 初始为1 ，传入区间[a,b]//tree[i].left tree[i].right为节点i的左右边界if(a!=b){tree[i].left=a;tree[i].right=b;build(i<<1,a,(a+b)>>1);//递归构造左子树build((i<<1)+1,((a+b)>>1)+1,b);//递归构造右子树tree[i].sum=tree[i<<1].sum+tree[(i<<1)+1].sum;//回溯 左右子树的和等于父节点    }else{tree[i].left=tree[i].right=a;tree[i].sum=A[a];//A[]为输入的数组return;    }tree[i].weight=0;}intadd(inti,inta,intb,intv){//将某个区间的所有值加上vif(tree[i].left==a&&tree[i].right==b){//恰好是这个区间tree[i].weight+=v;//将这个值保存而不是直接累加//查询的时候再进行更新 节省时间开销return1;    }else{//不是该区间但是属于该区间tree[i].sum+=v*(b-a+1);    }intmid= (tree[i].left+tree[i].right) >>1;if(a <=mid&&b>mid){add(i<<1,a,mid,v);add((i<<1)+1,mid+1,b,v);    }else{add((i<<1)+(b<=mid?0:1),a,b,v);    }return1;}long longquery(inti,inta,intb){//查询某个区间的所有值的和intmid= (tree[i].left+tree[i].right) >>1;if(tree[i].left==a&&tree[i].right==b){returntree[i].sum+ (tree[i].right-tree[i].left+1)*tree[i].weight;    }elseif(tree[i].weight!=0){tree[i].sum+= (tree[i].right-tree[i].left+1)*tree[i].weight;//首先更新自己tree[i<<1].weight+=tree[i].weight;//然后传递给左右子树tree[(i<<1)+1].weight+=tree[i].weight;tree[i].weight=0;//自身清零    }if(a <=mid&&b>mid){returnquery(i<<1,a,mid)+query((i<<1)+1,mid+1,b);    }returnquery((i<<1)+ (b<=mid?0:1),a,b);}

/** *二维线段树 *调用add,query,build时注意传参时的大小顺序，左小于右 *二维线段树的x维度和y维度表示的意义不一定是一样的 *下面是求平面上的矩形面积和(去掉重复区域后的面积和)，可以根据具体情况修改 */#defineMAX 1500vector<double>x;vector<double>y;//用于离散化structy_node{intleft,right;doublelen;//被覆盖的区间长度};structx_node{intleft,right;doublearea;//被覆盖的面积structy_nodesub[MAX];}tree[MAX];voidbuildSub(inti,intj,intyl,intyr){tree[i].sub[j].left=yl;tree[i].sub[j].right=yr;tree[i].sub[j].len=0;if(yr-yl==1){return;    }buildSub(i,j<<1,yl,(yl+yr)>>1);buildSub(i,(j<<1)+1,((yl+yr)>>1),yr);//最小元是个线段所以不加1}voidbuild(inti,intxl,intxr,intylm,intyrm){tree[i].left=xl;tree[i].right=xr;tree[i].area=0;if(xr-xl==1){buildSub(i,1,ylm,yrm);//建立子树 只对叶子节点建立子树return;    }build(i<<1,xl,(xl+xr)>>1,ylm,yrm);build((i<<1)+1,((xl+xr)>>1),xr,ylm,yrm);}voidaddSub(inti,intj,intyl,intyr){if(tree[i].sub[j].left==yl&&tree[i].sub[j].right==yr){tree[i].sub[j].len=y[tree[i].sub[j].right]-y[tree[i].sub[j].left];return;    }intmid= (tree[i].sub[j].left+tree[i].sub[j].right)>>1;if(yl<mid&&yr>mid){addSub(i,(j<<1),yl,mid);addSub(i,(j<<1)+1,mid,yr);    }else{addSub(i,(j<<1)+((yl >=mid)?1:0),yl,yr);    }tree[i].sub[j].len=mymax(tree[i].sub[j].len,tree[i].sub[(j<<1)].len+tree[i].sub[(j<<1)+1].len);}voidadd(inti,intxl,intxr,intyl,intyr){//if(tree[i].right-tree[i].left==1){//元区间addSub(i,1,yl,yr);//对y坐标加边 并计算长度tree[i].area=tree[i].sub[1].len*(x[xr]-x[xl]);//计算面积return;    }intmid= (tree[i].left+tree[i].right)>>1;if(xl<mid&&xr>mid){add((i<<1),xl,mid,yl,yr);add((i<<1)+1,mid,xr,yl,yr);    }else{add((i<<1)+((xl >=mid)?1:0),xl,xr,yl,yr);    }//更新面积tree[i].area=tree[(i<<1)].area+tree[(i<<1)+1].area;}doublequerySub(inti,intj,intya,intyb){if(tree[i].sub[j].left==ya&&tree[i].sub[j].right==yb){returntree[i].sub[j].len;    }else{//不是目标区间但包含目标区间//do something    }intmid= (ya+yb)>>1;if(ya <=mid&&yb>mid){returnquerySub(i,j<<1,ya,mid)+querySub(i,(j<<1)+1,mid,yb);    }elsereturnquerySub(i,(j<<1)+(yb<=mid?0:1),ya,yb);}doublequery(inti,intxa,intxb,intya,intyb){if(tree[i].left==xa&&tree[i].right==xb){returntree[i].area;    }else{//do something    }intmid= (xa+xb)>>1;if(xa <=mid&&xb>mid){returnquery(i<<1,xa,mid,ya,yb)+query((i<<1)+1,mid,xb,ya,yb);    }elsereturnquery((i<<1)+(xb<=mid?0:1),xa,xb,ya,yb);}//main中的离散化代码sort(x.begin(),x.end());sort(y.begin(),y.end());//排序之后去重x.resize(unique(x.begin(),x.end())-x.begin());y.resize(unique(y.begin(),y.end())-y.begin());

18. Trie树

/** *trie树，hash的方式，用空间换时间 注意别忘了创建根节点 */#defineMAX 256 //每个节点可能有多少个孩子structnode{///数据域intused;//标记是否有对应的字母structnode*next[MAX];};voidcreate(structnode*t){for(inti=0;i<MAX;i++){t->next[i]=newstructnode;///initialize    }}voidtrieInsert(structnode*curr,constchar*str,constintlen){for(inti=0;i<len;i++){//在当前节点的孩子中找intindex= (int)str[i];if(curr->next[index]->used==0){//没有这个字母curr->next[index]->used=1;create(curr->next[index]);//创建它的孩子        }curr=curr->next[index];    }///do something}

19. 矩阵

/** *矩阵快速幂(2行2列) */typedefdoubledataType;structmatrix{dataTypemat[2][2];matrix(){memset(mat,0,sizeof(mat));}//初始化为0matrix(doublev1,doublev2,doublev3,doublev4){mat[0][0]=v1;mat[0][1]=v2;mat[1][0]=v3;mat[1][1]=v4;}matrixoperator*(constmatrix&b){matrixrs;for(inti=0;i<2;i++){for(intk=0;k<2;k++){for(intj=0;j<2;j++){rs.mat[i][j]+=mat[i][k]*b.mat[k][j];                }            }        }returnrs;    }};matrixfastPower(matrixa,intpo){//a^pomatrixrs(1,0,0,1);//初始化为1while(po){if(po&1){rs=rs*a;}a=a*a;po= (po>>1);    }returnrs;}

20. 精度处理

/** *返回0表示x==0，-1表示x < 0, 1表示x大于0 *complf(a-b) == 0, a == b 或者 fabs(a-b) < eps *complf(a-b) != 0, a != b 或者 fabs(a-b) > eps *complf(a-b) <  0, a <  b 或者 a - b < -eps *complf(a-b) >  0, a >  b 或者 a - b > eps *complf(a-b) <= 0, a <= b 或者 a - b < eps *complf(a-b) >= 0, a >= b 或者 a - b > -eps */#defineeps 1e-8intcomplf(doublex){returnx<-eps?-1:((x<eps)?0:1);}

21. 动态规划

/** *0-1 背包 （二维实现，可以优化到一维） *注释中所说的对象可以为一个物体，也可以为一种方案，视题目而定 */dp[n+1][v+1];memset(dp[0],0,sizeof(int)*(v+1));//不放任何对象时，不管背包容量多少的价值都是0for(i=1;i <=n;i++){//从第一个对象开始//处理第i 个对象，在当前背包容量为j的时候选还是不选这个对象for(j=0;j <=v;j++){//枚举每个容量if(volume[i]>j){//这个对象肯定是不能放在容量为j的背包里的//如果j < volume[i]，相减之后就小于0了dp[i][j]=dp[i-1][j];        }else{//如果体积刚好等于剩余的容量也不一定会被放进去//因为可能有其它几个对象组合之后的价值比这个单个对象的高dp[i][j]=mymax(dp[i-1][j],dp[i-1][j-volume[i]]+weight[i]);        }    }}//结果保存在 dp[n][v]中，即对前n个对象做出取舍后的最优解

22. 素数生成

/** *筛法求素数 筛法求素数，找到[1,MAXL]的所有素数 */#defineMAXL 100000#defineMAXC 50000boolnot_prime[MAXL+1];//用于判断是否被筛掉 2的倍数都会被筛掉，但是没有标记intprimeTable[MAXC];//保存素数long longgetPrime(){long longi,j,step,prime_num=1;not_prime[0]=not_prime[1]= true;primeTable[0]=2;//第一个素数是2for(i=3;i <=MAXL;i+=2){if(not_prime[i]== false){primeTable[prime_num++]=i;for(j=i*i,step=2*i;j <=MAXL;j+=step){not_prime[j]= true;}        }    }returnprime_num;}

23. 素数测试

/** *Miller-Rabin 素数测试 *随机选取s个基 出错的概率至多为 1/(2^s)，50已经足够了 *RAND_MAX包含在stdlib中，不同的库会有不同，但都至少为32767 *//** *快速幂取模 返回 a^n mod m */long longexp_mod(long longa,long longn,long longm){//x*y mod m = ((x%m) * (y%m))%mif(n==1)returna %m;elseif(n==0)return1;if(n&1){//奇数 a^n = (a^(n-1))*areturn ((a%m)*exp_mod(a,n-1,m)) %m;    }else{//偶数 a^n = (a^(n>>1))^2long longt=exp_mod(a,n>>1,m) %m;returnt*t%m;    }}intwitness(inta,intn){//a^(n-1) = 1 (mod n)intt=0,u=n-1;while(!(u&1)){t++;u= (u>>1);}// n - 1 = u*(2^t)long longx[2];x[0]=x[1]=exp_mod(a,u,n);for(inti=1;i <=t;i++){x[1]=x[0]*x[0]%n;if(x[1]==1&&x[0]!=1&&x[0]!= (n-1)){return1;//检测到一个非平凡平方根        }x[0]=x[1];    }if(x[1]!=1)return1;return0;}intmillerRabin(intn,ints=50){if(n==2)return1;elseif(!(n&1))return0;for(inti=0;i<s;i++){inta= (int)((rand()*1.0/RAND_MAX)*(n-2))+1;if(witness(a,n)){//a^(n-1) = 1 (mod n) 如果n为素数，那么对于a(1<=a<=n-1)都满足这个等式return0;//基数a是n为合数的证据        }    }return1;//几乎可以确定n是个素数}

24. 最大公约数/最小公倍数

/** *最大公约数 gcd *最小公倍数 lcm = a*b/gcd(a,b) */intgcd(inta,intb){returnb ?gcd(b,a %b ) :a;}intlcm(inta,intb){returna/gcd(a,b)*b;}

/** *二进制欧几里得辗转相除法求gcd *传参的时候注意a >= b */typedeflong longint64;int64binaryGcd(int64a,int64b){if(a==b)returna;if((a&1)&& (b&1)){returnbinaryGcd(a-b,b);    }elseif((a&1)==0&& (b&1)==0){return2*binaryGcd(a>>1,b>>1);    }elseif((a&1)){returnbinaryGcd(a,b>>1);    }returnbinaryGcd(mymax(a>>1,b),mymin(a>>1,b));}

25. 欧拉 phi 函数

/** *欧拉phi函数  返回小于x且与x互质的数的个数 */inteuler_phi(intx){inta=ceill(sqrt(x)),i,rs=x;for(i=2;i <=a;i++){if(x %i==0){rs-=rs/i;//减去 在这rs个元素中有i因子的 数 的个数while(x %i==0){x /=i;}//将x中含有i因子的数去掉if(x==1)break;//x已经到1了        }    }if(x!=1) {rs-= (rs /x);}returnrs;}

26. 快速幂取模

/** *快速幂取模 返回 a^n mod m */intexp_mod(inta,intn,intm){//x*y mod m = ((x%m) * (y%m))%mif(n==1)returna %m;elseif(n==0)return1 %m;if(n&1){//奇数 a^n = (a^(n-1))*areturn ((a%m)*exp_mod(a,n-1,m)) %m;    }else{//偶数 a^n = (a^(n>>1))^2long longt=exp_mod(a,n>>1,m) %m;returnt*t%m;    }}

27. 扩展欧几里得

/** *扩展欧几里德 ax+by = gcd(a,b) 解出x,y */long longextendedEuclid(long longa,long longb,long long&x,long long&y){if(b==0){x=1;y=0;returna;    }else{long longgcd,x1,y1;gcd=extendedEuclid(b,a%b,x1,y1);x=y1;y=x1- (a/b)*y1;returngcd;    }}

28. 梅森素数

/** *扩展欧几里德 ax+by = gcd(a,b) 解出x,y */long longextendedEuclid(long longa,long longb,long long&x,long long&y){if(b==0){x=1;y=0;returna;    }else{long longgcd,x1,y1;gcd=extenedEuclid(b,a%b,x1,y1);x=y1;y=x1- (a/b)*y1;returngcd;    }}

29. 最大流

/** *最大流 传入源点 汇点和顶点数 *graph[u][v]为u到v的剩余流量 （residual flow） *初始的流量根据具体情况而定，如果没有边相连流量为0 *graph[v][u]为流过e(u,v)的流量 */#defineINF 1000000000#defineMAX 100intEdmonds_Karp(intsource,intsink,intvertex_num){intmaxFlow=0;while(true) {inthead,tail,pre_of[MAX],my_queue[MAX];head=tail=0;//初始化队列my_queue[tail++]=source;//放入源点memset(pre_of,-1,sizeof(pre_of));////(pre_of[v],v) 代表边(u,v)while(head<tail){intu=my_queue[head++];for(intv=1;v <=vertex_num;v++) {//也可以从0开始if(pre_of[v]==-1&&graph[u][v]>0){my_queue[tail++]=v;/*入队*/pre_of[v]=u;/*保存这条边*/if(u==sink)break;                }            }if(pre_of[sink]!=-1)break;//找到增广路径        }if(pre_of[sink]==-1)break;//没有增广路径intmin_flow=INF;for(intv=sink;v!=source;v=pre_of[v]) {min_flow=mymin(min_flow,graph[pre_of[v]][v]);//对pre保存的路径进行回溯找到最小的流(最大可流通流量)        }maxFlow+=min_flow;for(intv=sink;v!=source;v=pre_of[v]) {//更新流网络graph[pre_of[v]][v]-=min_flow;graph[v][pre_of[v]]+=min_flow;        }    }returnmaxFlow;}

/** *ISAP求最大流 */typedefstruct {intv,next,val;}edge;constintMAXN=20010;constintMAXM=500010;edgee[MAXM];intp[MAXN],eid;inlinevoidinit() {memset(p,-1,sizeof(p));eid=0;}//有向inlinevoidinsert1(intfrom,intto,intval) {e[eid].v=to;e[eid].val=val;e[eid].next=p[from];p[from]=eid++;swap(from,to);e[eid].v=to;e[eid].val=0;e[eid].next=p[from];p[from]=eid++;}//无向inlinevoidinsert2(intfrom,intto,intval) {e[eid].v=to;e[eid].val=val;e[eid].next=p[from];p[from]=eid++;swap(from,to);e[eid].v=to;e[eid].val=val;e[eid].next=p[from];p[from]=eid++;}intn,m;//n为点数 m为边数inth[MAXN];intgap[MAXN];intsource,sink;inlineintdfs(intpos,intcost) {if (pos==sink) {returncost;}intj,minh=n-1,lv=cost,d;for (j=p[pos];j!=-1;j=e[j].next) {intv=e[j].v,val=e[j].val;if(val>0) {if (h[v]+1==h[pos]) {if (lv<e[j].val) {d=lv;}else {d=e[j].val;}d=dfs(v,d);e[j].val-=d;e[j ^1].val+=d;lv-=d;if (h[source] >=n) {returncost-lv;}if (lv==0) {break;}}if (h[v]<minh){minh=h[v];}}}if (lv==cost) {--gap[h[pos]];if (gap[h[pos]]==0) {h[source]=n;}h[pos]=minh+1;++gap[h[pos]];}returncost-lv;}intsap(intst,inted) {source=st;sink=ed;intret=0;memset(gap,0,sizeof(gap));memset(h,0,sizeof(h));//gap[st] = n;gap[0]=n;while (h[st]<n) {ret+=dfs(st,INT_MAX);}returnret;}

30. 最短路

/** *SPFA可以用来求单源最短路径和求解差分约束 *可以处理负边和负权回路 */#defineINF 1000000000#defineMAX 50010//最大的点数，根据题目structnode{intu,v,weight,next;}edge[10*MAX];//边数一般比点数多inthead[MAX];intcount=0;voidadd(intu,intv,intc){//邻接表的加边操作edge[count].u=u;edge[count].v=v;edge[count].weight=c;edge[count].next=head[u];head[u]=count++;}intSPFA(intll,intrr){//根据具体情况对i点到起点的长度进行初始化intd[MAX];for(inti=ll;i <=rr;i++){d[i]=-INF;}d[ll]=0;queue<int>my_queue;my_queue.push(ll);//放入起点boolin_queue[MAX]= {};//用于判断某点当前是否在队列中while(!my_queue.empty()){intstart=my_queue.front();my_queue.pop();in_queue[start]= false;//拿出来了 所以不在队列中了for(inti=head[start];i!=-1;i=edge[i].next){intu=edge[i].u,v=edge[i].v,weight_of_uv=edge[i].weight;if(d[v]<d[u]+weight_of_uv){d[v]=d[u]+weight_of_uv;if(!in_queue[v]){//可以入队且不在队列中//可能会继续松弛表示可以入队my_queue.push(v);in_queue[v]= true;//标记为在队列中                }            }        }    }returnd[rr];//根据具体情况返回一个结果}

/** *dijkstra求最短路，用优先队列优化 *传入源点和顶点个数(注意顶点是从0还是1开始) *如果只计算源点到单个目的点的最短路，需将flag标记为1 并传入目的点 *注意head, countt等初始化*/#defineMAX1100#defineINF1000000000structnode{int u,v,w,next;//顶点结构体}edge[100100];int head[MAX], countt=0;//每次都要初始化voidadd(int u,int v,int w){//加边    edge[countt].u = u;    edge[countt].v = v;    edge[countt].w = w;    edge[countt].next = head[u];head[u] = countt++;}structnode2{int ver,dist;//顶点和dist[ver]node2(int v,int d){ver = v;dist = d;}};booloperator > (const node2 &a,const node2 &b){//重载优先队列的 > 运算符if(a.dist > b.dist)returntrue;returnfalse;}booloperator < (const node2 &a,const node2 &b){//重载优先队列的 < 运算符if(a.dist < b.dist)returntrue;returnfalse;}intdijkstra(int source,int vertex_num,int end=-1,int flag=0){int dist[MAX];//优先队列(小根,top为最小值)    priority_queue<node2,vector<node2>,greater<node2> > my;for(int i =1;i <= vertex_num;i++){        dist[i] = INF;    }dist[source] =0;    my.push(node2(source,0));//放入源点int pre_of[MAX];memset(pre_of,-1,sizeof(pre_of));while(!my.empty()){        node2 u = my.top();my.pop();if(flag && u.ver == end){return dist[u.ver];}if(dist[u.ver] == INF)break;//肯定没有更小的for(int i = head[u.ver];i != -1;i = edge[i].next){int v = edge[i].v,w = edge[i].w;if(dist[v] > dist[u.ver] + w){                dist[v] = dist[u.ver] + w;                pre_of[v] = u.ver;//保存路径                my.push(node2(v,dist[v]));            }        }    }///dist[i]保存的是源点到所有i点的最短距离return1;}

31. 最小生成树

/** *kruskal求最小生成树 */#defineMAX 1000structnode{intu,v,cost;}array[MAX*MAX];intedge_count;//边的数量intfather[MAX];voidmakeSet(intn){for(inti=1;i <=n;i++){//根据具体条件对并查集初始化father[i]=i;    }}intfind(intx){if(father[x]!=x){returnfather[x]=find(father[x]);    }returnfather[x];}voidunionSet(intx,inty){//将x所在的集合合并到y所在的集合father[find(x)]=find(y);}intkruskal(){inttotal_cost=0;//总花费//对边排序pseudocode:sort(array,array+edge_count);for(inti=0;i<edge_count;i++){if(find(array[i].u)==find(array[i].v)){//端点在同一个集合的不能添加进去//因为会构成回路continue;        }total_cost+=array[i].cost;unionSet(array[i].u,array[i].v);    }returntotal_cost;}