Q1: 洛谷P2807中的题目:
把大三角形的每条边n等分,将对应的等分点连接起来(连接线分别平行于三条边),这样一共会有多少三角形呢?编程来解决这个问题。
给定 nnn,三角形数量 ttt 满足 t=n(n+2)(2n+1)8t = \frac{n(n+2)(2n+1)}{8}t=8n(n+2)(2n+1)。如何证明?
Q2: 类似的,给定 nnn,求这些所有三角形的面积之和(假设最小的小三角形面积为1,如 n=4n=4n=4 时 S=87S = 87S=87,某OJ真题)。如何求解类似 Q1 这样的时间复杂度 O(1)O(1)O(1) 的公式?