补充中

编译指令

Windows

Windows 修改语言标准及开栈编译命令为 -std=c++14 -O2 -Wl,--stack=1073741824

其中 -Wl,--stack=1073741824 在某些场景可能需要双引号括起来。

Linux

Linux 当前会话开栈命令为 ulimit -s unlimited

可以用 ulimit -s 查看栈空间大小。

保留 3 位小数

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

最大公因数/最小公倍数

比赛时允许使用 C++ 自带的 {{ic|code=__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;
}

判断质数

判断单个质数

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

筛法

核心都是对于质数 $p$ 与任意数 $i$，把 $p\times i$ 标记为合数。

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

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

广搜核心逻辑

多测要清空

起点入队

重复取出队头并扩散

动态规划经典思路

大胆猜测状态

求最大长度：“前 i 项的最大长度”、“以第 i 项结尾的最大长度”

求方案数：“前 i 项的方案数”、“以第 i 项结尾的方案数”

求最大收益：“前 i 个物品的最大收益”

求最少操作次数：“s 的前 i 项与 t 的前 j 项的最少操作次数”

大胆猜测决策

选不选第 i 项

上一项选谁

不好求就加维度

前 i 个物品的最大收益：前 i 个物品在 j 体积下的最大收益