数组中不等三元组的数目

【暴力】考试专用三重for循环。

也可以调库。

【排序 + 枚举】排序后aabbbc。枚举中间的数x，x对答案的贡献为小于x的数 × 等于x的数 × 大于x的数，统计三部分的个数。 记a开头idx = start，计最后一个b的idx = i，计第一个c的idx = n - 1- i。

【容斥原理】

二叉搜索树最近节点查询

【中序遍历 + 二分查找】因为题目没说BST是平衡的，最坏情况会退化成链，所以不需要在二叉搜索树上找，可以中序遍历一次，把所有值取出来，得到一个有序数组，直接二分。

到达首都的最少油耗

【DFS】把一升油耗看作消耗一辆车，求返回首都最少的总车数（车流量）。设子树大小为size，则至少需要⌈size/seats⌉辆车。

完美分割的方案数

【DP + 前缀和优化】定义f[i] [j]为把s的前j个字符分割成i段的方案数，定义j为分割点，等价于s[j]不是指数且s[j + 1]是指数，j是分割点则考虑枚举第i-1段和第i段的分割点j - l。需u满足l ≥ minlength。累加所有f[i-1] [j - l]。加上剪枝和前缀和优化。