acmer-qualification-code

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>
using namespace std; 

///////////////////////////////////////////////////////////////////////
///C99 增加
#include <complex.h>        //复数处理
#include <fenv.h>           //浮点环境
#include <inttypes.h>       //整数格式转换
#include <stdbool.h>        //布尔环境
#include <stdint.h>         //整型环境
#include <tgmath.h>         //通用类型数学宏
///////////////////////////////////////////////////////////////////////

4. 注意事项

• 变量名count会和<algorithm>中的count冲突
• cin和scanf不能同时使用，cout和printf不能同时使用
• GCC/G++中，输出double应该使用printf("%f") 而不是lf
• 如果用scanf接收了一行数据，再用gets, gets会直接接收到空串！因为，scanf接受了一行数据以后换行符仍然在缓冲区中，gets()遇到换行符，接收会结束. 解决方法，scanf 后加一个getchar()
• 精度问题
• 2^31-1 =0x7fffffff
• -2^31 =-0x7fffffff-1
• 精确的pi :double pi=acos(-1);

5. N次方求和

6. 字符串处理

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

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

// 反转整数
#include<stdio.h>
#include<stdlib.h>
#define INF_MAX 0x7fffffff
#define INF_MIN -0x7fffffff-1
int reverse(int x){
    int ans = 0;
    int l = x;
    while(l != 0 ) {
        int h = l%10;
        l = l/10;
        // ans * 10 + h > INF_MAX
        // ans * 10 + h < INF_MIN
        if(INF_MAX/10 < ans || (INF_MAX/10 == ans && h > 7)) {
            return 0;
        }else if(INF_MIN/10 > ans || (INF_MIN/10 == ans && h < -8)) {
            return 0;
        }
        ans = ans * 10 + h;
    }
    return ans;
}

int main() {
    printf("%d\n", reverse(123));
    printf("%d\n", reverse(-123));
    return 0;
}

// 最长回文子串, 暴力解法
// 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
// 
// 示例 1：
// 
// 输入: "babad"
// 输出: "bab"
// 注意: "aba" 也是一个有效答案。
// 示例 2：
// 
// 输入: "cbbd"
// 输出: "bb"

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int valid(char *s, int i, int j) {
    while(i <= j) {
        if(s[i++] != s[j--]) {
            return 0;
        }
    }
    return 1;
}
char * longestPalindrome(char * s){
    int len = strlen(s);
    if (len == 1) {
        return s;
    }
    int  max = 1, maxi = 0;
    for(int i = 0;i < len-1;i++) {
        for(int j = i+1;j < len;j++) {
            int x = j - i + 1;
            if(x > max && valid(s, i,j)) {
                if(x  > max) {
                    max = x;
                    maxi = i;
                }
            }
        }
    }
    s = s+maxi;
    s[max] = '\0';
    return s;
}

int main() {
    char a[10] = "babad";
    printf("%s\n", longestPalindrome(a));
    return 0;
}

7. 进制转换

/**
 *将任意进制数转换成整型范围内的十进制数
 *str   为base进制数
 *base  为str的进制
 *length为str的长度
 */
int myPow(int a,int b){
    int rs = 1;
    while(b--){rs *= a;}
    return rs;
}
int anyToDecimal(char *str,int base,int length){
	int decimal = 0,i;
	for(i = 0;i < length;i++){
		if(str[i] >= 65)/*为十六进制的时候*/{
			decimal += myPow(base,length-1 - i)*(str[i] - 'A' + 10);
		}
		else if(str[i] <= '9'){
			decimal += myPow(base,length-1 - i)*(str[i] - '0');
		}
	}
	return decimal;
}

8. 栈

/**
 *栈 C++
 *clear() push() top() empty() pop() size()
 *free()
 */
typedef int T; 
struct myStack{

    int curr,size_limit;
    T *array;
    myStack(int s){//必须传入栈的大小
        curr = -1; size_limit = s;
        array = new T[s];
    }
    void clear(){curr = -1;}/*清空栈 重新使用*/
    void free(){delete array;clear();}/*释放栈 不能再使用*/
    T top(){
        if(curr > -1){return array[curr];}
        else return curr;}
    bool push(T v){
        if(curr+1 < size_limit){array[++curr] = v;return true;}
        return false;}
    bool empty(){
        if(curr < 0)return true;
        else return false;}
    void pop(){curr--;}
    int  size(){return curr+1;}

}; 

// c stack 没有安全检查, 使用时自己注意
#include <stdio.h>
#include <stdlib.h>

typedef int T;
struct stack {
  T *values;
  int pos, size;
};

void init_stack(struct stack *s, int size) {
  s->pos = 0;
  s->size = size;
  s->values = malloc(sizeof(T) * size);
}

struct stack *create(int size) {
  struct stack *p = malloc(sizeof(struct stack));
  init_stack(p, size);
  return p;
}
void delete (struct stack *s) { free(s->values); }

// not safe
void push(struct stack *s, T v) { s->values[s->pos++] = v; }
void dump(struct stack *s) {
  printf("[%p", s->values[0]);
  int i = 1;
  while(i < s->pos) {
     printf(", %p", s->values[i++]); 
  }
  printf("]\n");
}
int empty(struct stack *s) { return s->pos == 0; }
int full(struct stack *s) { return s->pos >= s->size; }
struct T *pop(struct stack *s) { return s->values[--s->pos]; }
struct T *top(struct stack *s) { return s->values[s->pos - 1]; }

int main() {
  struct stack *s = create(10);
  push(s, 1);
  dump(s);
  delete (s);
}

8. 表达式转换

/**
*自己定义操作符的优先级
*/
int priorityLevel(const char x){
}
/**
*自己定义操作符的结合性，左或者右
*/
int rightAssociative(const char x){

    switch(x){
        case '^':{ return 1;}
    }
    return 0;

}	
/**
*shunting_yard: infix expression to RPN
*中缀转换成后缀
*传入中缀表达式expression，RPN保存在result中
*/
void shunting_yard(char *result, const char *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)
 */

struct node{
    int flag;//0表示不存在
    int posi;//返回插入或者删除的位置
};
struct node *binarySearch(int *array,int value,int left,int right){
    struct node *pointer = (struct node*)malloc(sizeof(struct node));
    pointer->flag = 0;pointer->posi = -1;
    if(right == 0){//left == -1 impossible
        pointer->flag = pointer->posi = 0;
        return pointer;
    }
    while(left <= right){
        int mid = ((left + right) >> 1);
        if(value == array[mid]){
            pointer->flag = 1;
            pointer->posi = mid;
            return pointer;
        }
        else{
			(value > array[mid])?(left=mid+1):(right=mid-1);
		}
	}
	pointer->posi = left;return pointer;
}

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>

struct node {
  int value;
  struct node *left, *right;
};
struct node *bst_insert(struct node *curr, struct node *p) {
  if (curr == NULL) {
    return p;  //插入的节点的左右孩子的初始值一定要为NULL
  } else if (p->value < curr->value) {
    curr->left = bst_insert(curr->left, p);
  } else {
    curr->right = bst_insert(curr->right, p);
  }
  return curr;
}

void bst_inorder_traversal(struct node *curr) {
  if (curr != NULL) {
    bst_inorder_traversal(curr->left);
    printf("(%p, %d)\n", curr, curr->value);
    bst_inorder_traversal(curr->right);
  }
}

void bst_preorder_traversal(struct node *curr) {
  if (curr != NULL) {
    printf("(%p, %d)\n", curr, curr->value);
    bst_preorder_traversal(curr->left);
    bst_preorder_traversal(curr->right);
  }
}

void bst_postorder_traversal(struct node *curr) {
  if (curr != NULL) {
    bst_postorder_traversal(curr->left);
    bst_postorder_traversal(curr->right);
    printf("(%p, %d)\n", curr, curr->value);
  }
}

struct node *bst_search(struct node *curr, struct node *parent, int value,
                        int ret_flag) {
  if (curr == NULL) {
    // leaf node
    return NULL;
  } else if (curr->value == value) {
    // found, check ret flag
    // 返回的是要查找节点的父节点或者是要查找的节点
    // 使用父节点是因为这样便于删除的时候使用父节点进行删除
    if (ret_flag == 0) {
      return parent;
    } else {
      return curr;
    }
  } else if (value < curr->value) {
    return bst_search(curr->left, curr, value, ret_flag);
  } else {
    return bst_search(curr->right, curr, value, ret_flag);
  }
}

int bst_delete(struct node *parent, struct node *p, int is_left) {
  if (p->left == NULL && p->right == NULL) {
    // leaft node
    if (is_left) {
      // p 为parent的左子叶
      // 将 parent的左指针置为空
      parent->left = NULL;
    } else {
      // p 为parent的右子叶
      parent->right = NULL;
    }
    free(p);
  } else if (p->left == NULL) {
    // 待删除节点无左子树，说明有右子树
    if (is_left) {
      // 将待删除的节点的右子树 赋值给父节点的左子树
      parent->left = p->right;
    } else {
      // 将待删除的节点的右子树 赋值给父节点的左子树
      parent->right = p->right;
    }
    free(p);
  } else if (p->right == NULL) {
    // 待删除节点无右子树，说明有左子树
    if (is_left) {
      parent->left = p->left;
    } else {
      parent->right = p->left;
    }
    free(p);
  } else {
    struct node *s = p->right;
    struct node *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);
  }
  return 1;
}
void bst_build(struct node *root, int *array, int start, int end) {
  // [start, end)
  while (start < end) {
    // create node
    struct node *p = malloc(sizeof(struct node));
    p->value = array[start];
    p->left = p->right = NULL;  // init
    bst_insert(root, p);
    start++;
  }
}

int main() {
  int a[10] = {1, 450, 3, 4, 56, 12, 123, 45, 23, 6};
  struct node *root = malloc(sizeof(struct node));
  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);
  struct node *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]
 *从小到大
 */
void quickSort(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 >= j
    if(i < right)quickSort(i,right,array);
    if(j > left)quickSort(left,j,array);

}

/**
 *heapSort 堆排序模板 （大根堆）
 */
int mySwap(int *a,int *b){
if(a == b) return;
	(*a) = (*a) ^ (*b);
	(*b) = (*a) ^ (*b);
	(*a) = (*a) ^ (*b);
    return 1;
}	
int sift(int array[],int k,int m)//one-based
{
//把k到m范围内的值调整为大根堆
    int i = 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节点 计算左孩子
        }
    }
    return 1;
}
int heapSort(int array[],int n){// one-based 从1开始保存的 到n结束 left_child = 2*parent
    int i;
    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-based
        sift(array,1,n - i);//重建堆
    }
    return 1;
}

11. 递归

/**
 *汉诺塔 递归实现
 */
int move(int n,char x,char y){
    printf("move %d from %c to %c\n",n,x,y);//输出移动过程
    return 1;
}
int hanoi(int n,char a,char b,char c){//将n个盘子借助b从a移动到c
    if(n==1){move(1,a,c);}
    else{
        hanoi(n-1,a,c,b);//把n-1个盘子借助c从a移动到b
        move(n,a,c);//把第n个盘子从a移动到c
        hanoi(n-1,b,a,c);//将n-1个盘子借助a从b移动到c
    }
    return 1;
}

12. 链表

/**
 *构建一个未赋值的循环单链表 至少有头和尾两个节点
 */
struct node{
    int 	value;
    struct node *next;
};
struct node *constructRecurrentSingleChain(int start,int end){
    struct node *head = (struct node*)malloc(sizeof(struct node));
    struct node *tail = (struct node*)malloc(sizeof(struct node));

    head->next = tail;
    tail->next = head;
    //head->value= -1;
    //tail->value= -1;
    while(start != end){
        struct node *new_node = (struct node*)malloc(sizeof(struct node));
        //new_node->value     = start;根据具体情况进行赋值
        new_node->next        = head;
        tail->next            = new_node;
        tail                  = new_node;
        start++;
    }
    return head;
}

/**
 *构建未赋值的循环双链表 至少有头和尾两个节点
 */
struct node{
    int value;
    struct node *prev;
    struct node *next;
};
struct node *constructRecurrentDoubleChain(int start,int end){
    struct node *head = (struct node*)malloc(sizeof(struct node));
    struct node *tail = (struct node*)malloc(sizeof(struct node));

    head->prev = tail;
    head->next = tail;
    tail->next = head;
    tail->prev = head;
    //head->value= -1;
    //tail->value= -1;
    while(start != end){
        struct node *new_node = (struct node*)malloc(sizeof(struct node));
        //new_node->value       = start;
        tail->next            = new_node;
        head->prev            = new_node;
        new_node->prev        = tail;
        new_node->next        = head;
        tail                  = new_node;
        start++;
    }
    return head;
}

13. 大数

/**
 *大数的加法 乘法运算
 *效率很低 不能用于算大数阶乘
 */
 class BigInteger
 {
public:

     BigInteger();
     BigInteger(int);
     BigInteger(string);
     bool Display();
     friend BigInteger operator +(const BigInteger&,const BigInteger&);
     friend BigInteger operator *(const BigInteger&,const BigInteger&);
     friend ostream&   operator<<(std::ostream&,BigInteger&);

private:

     static const int 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;
     else		len = 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];
     return true;

 }
 std::ostream& operator<<(ostream &out, BigInteger &digit){

     digit.Display(); return out;

 }
 BigInteger operator +(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;

 }
 BigInteger operator *(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的时候不用去掉第一位的0
     return result;

 }

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

/**
 *大数模板(浙大)
 *注意这里的int可能会超 void div(bignum_t a,const int b,int& c)
 */
#define DIGIT 	3//千进制
#define DEPTH	1000//千进制
#define MAX     1000//位数
typedef int bignum_t[MAX+1];

int read(bignum_t a,istream& is=cin){
	char buf[MAX*DIGIT+1],ch;
	int i,j;
	memset((void*)a,0,sizeof(bignum_t));
	if (!(is>>buf))	return 0;
	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]--);
	return 1;
}

void write(const bignum_t a,ostream& os=cout){
	int i,j;
	for (os<<a[i=a[0]],i--;i;i--)
		for (j=DEPTH/10;j;j/=10)
			os<<a[i]/j%10;
}

int comp(const bignum_t a,const bignum_t b){
	int i;
	if (a[0]!=b[0])
		return a[0]-b[0];
	for (i=a[0];i;i--)
		if (a[i]!=b[i])
			return a[i]-b[i];
	return 0;
}

int comp(const bignum_t a,const int b){
	int c[12]={1};
	for (c[1]=b;c[c[0]]>=DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);
	return comp(a,c);
}

int comp(const bignum_t a,const int c,const int d,const bignum_t b){
	int i,t=0,O=-DEPTH*2;
	if (b[0]-a[0]<d&&c)
		return 1;
	for (i=b[0];i>d;i--){
		t=t*DEPTH+a[i-d]*c-b[i];
		if (t>0) return 1;
		if (t<O) return 0;
	}
	for (i=d;i;i--){
		t=t*DEPTH-b[i];
		if (t>0) return 1;
		if (t<O) return 0;
	}
	return t>0;
}

void add(bignum_t a,const bignum_t b){
	int i;
	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];
	else
		for (;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);
	a[0]+=(a[a[0]+1]>0);
}

void add(bignum_t a,const int b){
	int i=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]++);
}

void sub(bignum_t a,const bignum_t b){
	int i;
	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]--);
}

void sub(bignum_t a,const int b){
	int i=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]--);
}

void sub(bignum_t a,const bignum_t b,const int c,const int d){
	int i,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]--);
}

void mul(bignum_t c,const bignum_t a,const bignum_t b){
	int i,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]--);
}

void mul(bignum_t a,const int b){
	int i;
	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]--);
}

void mul(bignum_t b,const bignum_t a,const int c,const int d){
	int i;
	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]--);
}

void div(bignum_t c,bignum_t a,const bignum_t b){
	int h,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;
			else l=m;
	for (;!c[c[0]]&&c[0]>1;c[0]--);
	c[0]=c[0]>1?c[0]:1;
}

void div(bignum_t a,const int b,long long & c){
	int i;
	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]--);
}

void sqrt(bignum_t b,bignum_t a){
	int h,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;
			else l=m;
	for (;!b[b[0]]&&b[0]>1;b[0]--);
	for (i=1;i<=b[0];b[i++]>>=1);
}

int length(const bignum_t a){
	int t,ret;
	for (ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++);
	return ret>0?ret:1;
}

int digit(const bignum_t a,const int b){
	int i,ret;
	for (ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--);
	return ret%10;
}

int zeronum(const bignum_t a){
	int ret,t;
	for (ret=0;!a[ret+1];ret++);
	for (t=a[ret+1],ret*=DIGIT;!(t%10);t/=10,ret++);
	return ret;
}

void comp(int* a,const int l,const int h,const int d){
	int i,j,t;
	for (i=l;i<=h;i++)
		for (t=i,j=2;t>1;j++)
			while (!(t%j))
				a[j]+=d,t/=j;
}

void convert(int* a,const int h,bignum_t b){
	int i,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);
}

void combination(bignum_t a,int m,int n){
	int* t=new int[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;
}

void permutation(bignum_t a,int m,int n){
	int i,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. 并查集

int father[15];
void makeSet(){
    for(inti = 0;i <= n;i++){
        father[i] = i;
    }
}
int findSet(int x){
    if(x != father[x]){
        father[x] = findSet(father[x]);
    }
    return father[x];
}
void unionSet(int x,int y){
    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 long f[1<<20] = {};
f[0] = 1;//f[2^0 - 1] = f[0] = 1 (0的阶乘为1)
for(int i = 1;i < (1<<n);i++){// 1 到 2^n - 1
    for(int t = 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  -= 8
        f[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
 */

int lowbit(int x){
    return x & (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;
}
void add(int i,int v,int upper){//对A[i]进行加v操作 同时更新C
    //对A[i]的更新直接不要放在这里 因为build也要调用该函数
    while(i <= upper){
        C[i] += v; i += lowbit(i);
    }
}
void build(int begin,int end){//根据A[begin]到A[end]构建树状数组
    while(begin <= end){
        add(begin,A[begin],end);
    }
}
int sum(int i){//求前n项和
    int sum = 0;
    while(i >= 1){
        sum += C[i]; i -= lowbit(i);
    }
    return sum;
}

/**
 *二维树状数组
 *二维树状数组和一维几乎一样
 */

int lowbit(int x){
    return x & (x^(x-1));
}
void add(int i,int j,int v,int upper){//增加
    int t_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;
        }
    }
}
int query(int i,int j){//查询
    int sum = 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];
        }
    }
    return sum;
}

17. 线段树

/**
 *树状数组是前序和，应用范围要窄，线段树可以求区间和、区间最大值等等
 *下面是求线段树求区间和的示例，可以根据具体情况修改
 */
 
#define MAX 100000
struct node{
    int left,right;
    long long sum,weight;
}tree[MAX];
int A[MAX];//MAX_n
void build(int i,int a,int b){//构建线段树 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;
}
int add(int i,int a,int b,int v){//将某个区间的所有值加上v
    if(tree[i].left == a && tree[i].right == b){
        //恰好是这个区间
        tree[i].weight += v;//将这个值保存而不是直接累加
	   //查询的时候再进行更新 节省时间开销
        return 1;
    }
    else{
        //不是该区间但是属于该区间
        tree[i].sum += v*(b - a + 1);
    }
    int mid = (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);
    }
    return 1;
}
long long query(int i,int a,int b){//查询某个区间的所有值的和
    int mid = (tree[i].left+tree[i].right) >> 1;
    if(tree[i].left == a && tree[i].right == b){
        return tree[i].sum + (tree[i].right - tree[i].left + 1)*tree[i].weight;
    }
    else if(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){
        return query(i<<1,a,mid) + query((i<<1)+1,mid+1,b);
    }
    return query((i<<1) + (b<=mid?0:1),a,b);
}

/**
 *二维线段树
 *调用add,query,build时注意传参时的大小顺序，左小于右
 *二维线段树的x维度和y维度表示的意义不一定是一样的
 *下面是求平面上的矩形面积和(去掉重复区域后的面积和)，可以根据具体情况修改
 */
#define MAX 1500
vector<double> x;
vector<double> y;//用于离散化
struct y_node{
    int left,right;
    double len;//被覆盖的区间长度
};	
struct x_node{
    int left,right;
    double area;//被覆盖的面积
    struct y_node sub[MAX];
}tree[MAX];

void buildSub(int i,int j,int yl,int yr){
    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
}
void build(int i,int xl,int xr,int ylm,int yrm){
    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);
}
void addSub(int i,int j,int yl,int yr){
    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;
    }
    int mid = (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);
}
void add(int i,int xl,int xr,int yl,int yr){//

    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;
    }
    int mid = (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;
}
double querySub(int i,int j,int ya,int yb){
    if(tree[i].sub[j].left == ya && tree[i].sub[j].right == yb){
        return tree[i].sub[j].len;
    }
    else{
        //不是目标区间但包含目标区间
        //do something
    }
    int mid = (ya+yb)>>1;
    if(ya <= mid && yb > mid){
        return querySub(i,j<<1,ya,mid) + querySub(i,(j<<1)+1,mid,yb);
    }
    else return querySub(i,(j<<1)+(yb<=mid?0:1),ya,yb);
}
double query(int i,int xa,int xb,int ya,int yb){
    if(tree[i].left == xa && tree[i].right == xb){
        return tree[i].area;
    }
    else{
        //do something
    }
    int mid = (xa+xb)>>1;
    if(xa <= mid && xb > mid){
        return query(i<<1,xa,mid,ya,yb) + query((i<<1)+1,mid,xb,ya,yb);
    }
    else return query((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());