引入
相信大家都知道高斯求和公式:首项加末项的和乘项数除以二等于等差数列的和。
实际应用中往往不会这么简单,常常会告诉你等差数列的和然后让你反过来求等差数列的信息,这时候对于边界的处理就很重要。
P1014 [NOIP1999 普及组] Cantor 表
显然可以 \(O(N)\) 模拟,但这太慢了。
先来看分子:\(1,2,1,1,2,3,4,3,2,1,\ldots\)
容易发现对于 \(1\to\infty\) 的每个 \(i\),如果 \(i\bmod 2=1\),那么就填入 \(1\to i\),否则填入 \(i\to 1\)。
这不禁让我们想到快速计算的方式,先求出 \(\frac{(1+i)\times i}{2}<n\) 的最大的 \(i\),然后确定具体填的数。
显然可以 \(O(\log N)\) 二分出来,但这太慢了。
移项得到 \((1+i)\times i<2n\),取 \(j=\lfloor\sqrt{2n}\rfloor\)。
而 \((1+j)\times j\) 可能大于也可能小于等于 \(2n\),这要看 \(n\) 的具体取值。
如果出现了大于的情况,因为 \(j\leq\sqrt{2n}<j+1\),所以 \(j\times(j-1)<2n\),只需要判断一次即可。
分母除了填入方向相反外别的完全相同。
CF1426C Increase and Copy
肯定是先 \(+1\) 再复制,元素的值和元素个数越相近总和越大。
令 \(i=\lfloor\sqrt n\rfloor\):
- \(i^2=n\),\(+1\) 和复制都是 \(i-1\) 次。
- \(i\times(i+1)\geq n\),多 \(+1\) 一次或者多复制一次。
- 否则两者都多做一次。