A5555.三数和 题解
思路
这个题的话有四种方法。
方法1：
枚举 a,b,ca,b,ca,b,c，计算是否等于 nnn 且 0<a<b<c≤n0 \lt a \lt b \lt c \leq n0<a<b<c≤n，时间复杂度 O(n3)O(n^{3})O(n3)，期望得分 60pts60pts60pts,加了一点点不算优化的优化实际得分 100pts100pts100pts。
方法2：
枚举 a,ba,ba,b，计算 ccc，判断是否 b<c≤nb \lt c \leq nb<c≤n，时间复杂度 O(n2)O(n^{2})O(n2)，期望得分 100pts100pts100pts。做到这里就算正解了。
方法3：
通过缩减 bbb 的枚举范围，发现 bbb 缩减到 ⌈n−a2⌉−1−a\lceil {\frac{n-a}{2}} \rceil - 1 - a⌈2n−a ⌉−1−a 的时候一定有一个 ccc 符合条件，aaa 枚举到 n3\frac{n}{3}3n 即可，因为 a>n3a > \frac{n}{3}a>3n 的时候方案数会变成负数。
所以归根结底就是求
∑i=1⌊n3⌋−1⌈n−i2⌉−1−i\sum ^{\lfloor \frac{n}{3} \rfloor-1} _ {i=1}\lceil {\frac{n-i}{2}} \rceil - 1 - i i=1∑⌊3n ⌋−1 ⌈2n−i ⌉−1−i
是多少。
时间复杂度 O(n)O(n)O(n)，期望得分 100pts100pts100pts。
方法4:
这个方法不推荐，用正确代码打表就可以了。时间复杂度 O(1)O(1)O(1)，期望得分 100pts100pts100pts。
代码
方法 1 代码
方法 2 代码
方法 3 代码
方法 4 代码
