高精度

存储

高精度算法是对竖式的模拟，要求各位对齐，所以使用逆序存储。

void read(int a[]) {
  static char s[LEN + 1];
  scanf("%s", s);
  clear(a);
  int len = strlen(s);
  for (int i = 0; i < len; ++i) a[len - i - 1] = s[i] - '0';
}

这里首先正向读入了字符串s，然后将其逆序存储到a里。

输出

例如我输入一个数：0000563，这是存在前导0的，逆序存储后得到3650000，也就是说输出的时候要找到数组中第一个非0位然后再向前输出。

void print(int a[]){
    int i = LEN - 1;
    while(a[i] == 0) i--;
    while(i >= 0){
        putchar(a[i] + '0');
        i--;
    }
}

加法

因为之前都是野路子，这里最好还是规范一下写法，提高比赛效率。

主要就是处理进位问题，从低位向高位计算，如果要进位就把前面一位增加1即可。

void add(int a[],int b[],int c[]){
    clear(c);
    for(int i = 0;i<LEN - 1;i++){
        c[i] += a[i] + b[i];
        if(c[i] >= 10){
            c[i + 1] += 1;
            c[i] -= 10;
        }
    }
}

竞赛中常用的高精实现

在递推问题上，经常需要加法高精度，如果是两个因子的递推式，可以用一个二维数组存储高精结果，每次加法计算先各位相加，然后再依次计算进位，在过程中记录结果长度len，每次处理完进位后检查是否多出一位，此时增加len的值即可。

void add(int x){
    for(int i = 1;i<=len;i++){
        f[x][i] = f[x-1][i] + f[x-2][i];//相加
    }
    for(int i = 1;i<=len;i++){//进位
        if(f[x][i] >= 10){
            f[x][i+1] += f[x][i]/10;
            f[x][i] %= 10;
        }
    }
    if(f[x][len+1] > 0) len++;
}

P2437 蜜蜂路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

减法

多关键字排序

PTA乙级1015 多关键字排序通常使用sort函数解决，并且手写一个比较函数：

bool cmp(const student &a,const student &b){
	return a > b;//结果为5>4>3,降序
	return a < b;//结果为3<4<5,升序
}

[[多项式]]

秦九韶公式的实现是由内向外的计算，每次的计算结果作为一个整体$p$，下次计算则计算$a_{i-1}+xp$，一直到$i=1$为止。

年月日转换

将日期转换成时间戳$time=year\times 10000+month\times 100+day$，拉大年月日之间的差距，后续直接比较这个时间戳即可判定日期先后顺序。