初学者常用内容

补充中

保留 3 位小数

cout << fixed << setprecision(3) << 1.0 / 3;

最大公因数/最小公倍数

比赛时允许使用 C++ 自带的 __gcd(a,b) 函数求最大公因数。

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

判断质数

判断单个质数

• 如果小于 [math]\displaystyle{ 2 }[/math] 肯定不是质数
• 检查 [math]\displaystyle{ 2\sim \sqrt{n} }[/math]，如果有因子，肯定不是质数
• 通过了前面的检查就肯定是质数

筛法

核心都是对于质数 [math]\displaystyle{ p }[/math] 与任意数 [math]\displaystyle{ i }[/math]，把 [math]\displaystyle{ p\times i }[/math] 标记为合数。

• 埃氏筛法：[math]\displaystyle{ O(n\log \log n) }[/math] 把筛出来的质数的倍数标记为合数。
• 欧拉筛法：[math]\displaystyle{ O(n) }[/math] 把每个数的质数倍标记为合数，如果当前质数是因子，就不用考虑更大的质数了（肯定会可以由一个更大的数乘以那个作为因子的质数）

欧拉筛法能保证每个数只被最小质因子筛，可以用来处理一些积性函数求解。

广搜核心逻辑

1. 多测要清空
2. 起点入队
3. 重复取出队头并扩散

动态规划经典思路

1. 大胆猜测状态
   1. 求最大长度：“前 i 项的最大长度”、“以第 i 项结尾的最大长度”
   2. 求方案数：“前 i 项的方案数”、“以第 i 项结尾的方案数”
   3. 求最大收益：“前 i 个物品的最大收益”
   4. 求最少操作次数：“s 的前 i 项与 t 的前 j 项的最少操作次数”
2. 大胆猜测决策
   1. 选不选第 i 项
   2. 上一项选谁
3. 不好求就加维度
   1. 前 i 个物品的最大收益：前 i 个物品在 j 体积下的最大收益