Algorithm(1)

算法

 2024/09/24 

写在前面（关于做题的经验）

判断是不是用简单的算法思想就能解决（不需要更多数据结构），分治？贪心？
如果是贪心，核心是确定好cmp函数
如果是分治，确定递归函数的内容，全局数组+左边界（参数1）+右边界（参数2）+参数3
剪枝：搜索过程中利用某些额外的条件判断提前返回从而优化搜索时间
反向思考，a要能到b，b到a？
常见数据结构和算法的模板

高精度计算

本质上是字符串处理。参考oi wiki的高精乘和加模板

高精加：

void add(int a[], int b[], int c[]) {
  clear(c);
  // 高精度实现中，一般令数组的最大长度 LEN 比可能的输入大一些
  // 然后略去末尾的几次循环，这样一来可以省去不少边界情况的处理
  // 因为实际输入不会超过 1000 位，故在此循环到 LEN - 1 = 1003 已经足够
  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;
    }
  }
}

高精*低精：

void mul_short(int a[], int b, int c[]) {
  clear(c);
  for (int i = 0; i < LEN - 1; ++i) {
    // 直接把 a 的第 i 位数码乘以乘数，加入结果
    c[i] += a[i] * b;
    if (c[i] >= 10) {
      // 处理进位
      // c[i] / 10 即除法的商数成为进位的增量值
      c[i + 1] += c[i] / 10;
      // 而 c[i] % 10 即除法的余数成为在当前位留下的值
      c[i] %= 10;
    }
  }
}

进位单独抽出来也行：

void result_1()
{
    memset(sav,0,sizeof(sav));
    for(register int i=1;i<=500;i+=1)
        for(register int j=1;j<=500;j+=1)
            sav[i+j-1]+=res[i]*f[j];//先计算每一位上的值（不进位）
    for(register int i=1;i<=500;i+=1)
    {
        sav[i+1]+=sav[i]/10;//单独处理进位问题，不容易出错
        sav[i]%=10;
    }
    memcpy(res,sav,sizeof(res));//cstring库里的赋值函数，把sav的值赋给res
}

高精*高精：

void mul(int a[], int b[], int c[]) {
  clear(c);
  for (int i = 0; i < LEN - 1; ++i) {
    // 这里直接计算结果中的从低到高第 i 位，且一并处理了进位
    // 第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
    // 这样做的效果和直接进行上图的运算最后求和是一样的，只是更加简短的一种实现方式
    for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];

    if (c[i] >= 10) {
      c[i + 1] += c[i] / 10;
      c[i] %= 10;
    }
  }
}

高精度输入输出：

void clear(int a[]) {
  for (int i = 0; i < LEN; ++i) a[i] = 0;
}

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[i] - '0' 就是 s[i] 所表示的数码
  // 有些同学可能更习惯用 ord(s[i]) - ord('0') 的方式理解
}

void print(int a[]) {
  int i;
  for (i = LEN - 1; i >= 1; --i)
    if (a[i] != 0) break;
  for (; i >= 0; --i) putchar(a[i] + '0');
  putchar('\n');
}

快速模幂的代码实现

原理课上学过，拆成2进制后复用自乘减少次数，优化复杂度到$Ologn$

int quickPower(int a, int b)//是求a的b次方
{
	int ans = 1, base = a;//ans为答案，base为a^(2^n)
	while(b > 0)//b是一个变化的二进制数，如果还没有用完
    {
		if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
			ans *= base;//把ans乘上对应的a^(2^n)
		
        base *= base;//base自乘，模乘这里要取模
		b >>= 1;// 模乘这里要取模
        //位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
	}
    // 模乘这里要处理b为0情况
    // ans%=p
	return ans;
}

模乘的话，就在每一个乘法后面都添加一个模，注意边界情况。

素性检测

$n^2$遍历

最大流

最大流最小割定理：最大流的值等于最小割的容量。（强对偶）

Ford-Fulkerson $O(mnC)$

KMP算法

Next Post

ByteCTF2024——ezheap
Previous Post

Algorithm(2)

CATALOG

1. 写在前面（关于做题的经验）
2. 高精度计算
3. 快速模幂的代码实现
4. 素性检测
5. 最大流
6. KMP算法