模拟赛总结（3）
一.题目解析
1.石砖楼梯
由于对于 \(100 \%\) 的数据，\(n \leq 2^{31}-1\) 所以暴力会被卡掉。
初步估算时间复杂度为：\(O(Tlongn)\)。
先观察一下每层正好垒完需要的砖数：
1 : 1
2 : 3
3 : 6
4 : 10
5 : 15
下面以此类推，我们可以发现：垒完 \(x\) 列楼梯需要 \(\frac{x \times (x+1)}{2}\)。
然后还需要二分枚举 \(x\) 列可以构成的砖数，满足 \(l \leq n \leq r\)（\(l, r\) 为区间的左右端点），用等差数列求出已搬完的即可。
还有一种数学方法：
解一元二次方程：\(\frac{1}{2}k^2 + \frac{1}{2}k - n = 0\)
带入求根公式：
\(x_1 = -\frac{1}{2} - \sqrt{\frac{1}{4}+2n}\)
\(x_2 = -\frac{1}{2} - \sqrt{\frac{1}{4}+2n}\)
\(x_1 < 0\) 舍去，留 \(x_2\)，之后和第一种方法一样，用等差数列。
2.像素画板
这个题的时间复杂度是需要优化的，我们对于每一个 \(4\) 号询问，可以看成 \((0,0)\) （可能会改变）到 \((x,y)\) 之间被染色的方块个数。
既然是求区间，就可以用前缀和预处理：
sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
处理完后暴力就行。
3.分堆
先用欧拉筛预处理所有的质数。
欧拉筛模版：
int vis[N], prime[N], cnt = 0;
for (int i = 2;i <= n; ++i){
if (!vis[i]) prime[++cnt] = i;
for (int j = 1;j <= cnt && i * prime[j] <= n; ++j) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
然后我们想：对于一个数，分解的最大值确认，由于可能被多次分出，所以考虑 \(DP\) 预处理：
dp[i] = max(dp[i], dp[j] + dp[i-j] + zs[i])
其中 \(zs[i]\) 是判断 \(i\) 是否为质数的数组。
而有可能出现多个 \(j\) 都转移出最终结果，其中 \(j\) 和 \(i-j\) 可能都不是质数，质数只需枚举到 \((i+1)/2\)，最后直接枚举。
4.小A的金币
枚举左端点 \(l\)，二分出 \(r\)，计算把 \([l,r]\) 内的所有 \(S\) 都变成 \(C\)，之后把每个 \(S\) 块的开头设成 \(1\) 后使用前缀和。
时间复杂度：\(O(mlongm)\)，显然过不了 \(100 \%\) 的数据。
我们考虑 \(DP\)。
我们发现，\(P\) 变成 \(S\) 还是 \(C\) 并不影响消耗的次数与答案，\(P\) 附近有什么变什么。
固定左端点，考虑右端点 \(r \rightarrow r+1\)
-
如果 \(r+1\) 是 \(C\) 可以直接洗。
-
如果 \(r+1\) 是 \(P\) 可以花费 \(2\) 代价换，不过如果 \(n<2\) 就不能再扩展了。
-
如果 \(r+1\) 是 \(S\)，则如果 \(max\{x,l\}\) 之间有其他 \(S\)，代价不变化，否则代价变化。
时间复杂度：\(O(n)\)，这样就可以过 \(100 \%\) 的数据。
二.总结
\(T1\) 多组数据，输入时 scanf("%d", &n) 前面没有加 \(\sim\) 挂了 \(100 \ pts\)。