Acwing Blue Bridge Cup summary

第一讲 递推与递归

• 递归实现指数型枚举：1到n中选任意多个，每个数都有选与不选两种可能。
• 递归实现排列型枚举：1到n输出所有的不同顺序的序列，此为排列型。
• 递归实现组合型枚举：1到n中选m个数，此为组合型。

worth reviewing

• 带分数：求解公式的变形，再穷举。
• 翻硬币：一种无后效性的递推。

第二讲 二分与前缀和

1. 二分与三分

• 整数二分
• 实数二分：实数二分时，注意l与r均为double类型。
• 三分

worth reviewing

• 四平方和：把四位递推优化成二维递推加二分查找，也可以优化成二维递推加哈希表查找。

2. 前缀和与差分

worth reviewing

• 子矩阵的和：插入:a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];，查找:a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1]。