ACGO 巅峰赛#15 - 题目解析
> 间隔四个月再战 ACGO Rated，鉴于最近学业繁忙，比赛打地都不是很频繁。虽然这次没有 AK 排位赛（我可以说是因为周末太忙，没有充足的时间思考题目…（好吧，其实也许是因为我把 T5 给想复杂了））。
>
> 本文依旧提供每道题的完整解析（因为我在赛后把题目做出来了）。
T1 - 高塔
题目链接跳转：点击跳转
> 插一句题外话，这道题的题目编号挺有趣的。
没有什么特别难的点，循环读入每一个数字，读入后跟第一个输入的数字比较大小，如果读入的数字比第一个读入的数字要大（即 ai>a1a_i > a_1ai >a1 ），直接输出 iii 并结束主程序即可。
本题的 C++ 代码如下：
本题的 Python 代码如下：
T2 - 营养均衡
题目链接跳转：点击跳转
也是一道入门题目，没有什么比较难的地方，重点是把题目读清楚了。
我们设置一个数组 arr\tt{arr}arr，其中 arri\tt{arr_i}arri 表示种营养元素还需要的摄入量。那么，如果 arri≤0\tt{arr_i} \le 0arri ≤0 的话，就表示该种营养元素的摄入量已经达到了 “健康饮食” 的所需标准了。按照题意模拟一下即可，最后遍历一整个数组判断是否有无法满足的元素。换句话说，只要有任意的 ∀i\forall i∀i，满足 arri>0\tt{arr_i} > 0arri >0 就需要输出 No。
本题的 C++ 代码如下：
本题的 Python 代码如下：
T3 - ^_^ 还是 :-(
题目链接跳转：点击跳转
> 一道简单的思维题目，难度定在【普及-】还算是合理的。不过 USACO 的 Bronze 组别特别喜欢考这种类似的思维题目。
普通算法
考虑采用贪心的思路，先把序列按照从大到小的原则排序。暴力枚举一个节点 iii，判断是否有可能满足选择前 iii 个数字 −1-1−1，剩下的数字都至少 +1+1+1 的情况下所有的数字都大于零。
那么该如何快速的判断是否所有的数字都大于零呢？首先可以肯定的是，后 n−in - in−i 个数字一定是大于零的，因为这些数字只会增加不会减少。所以我们把重点放在前 iii 个数字上面。由于数组已经是有序的，因此如果第 iii 个数字是大于 111 的，那么前 iii 个数字在减去 111 之后也一定是正整数。
由于使用了排序算法，本算法的单次查询时间复杂度在 O(Nlog2N)O(N \log_2 N)O(Nlog2 N) 级别，总时间复杂度为 O(N2log2N)O(N^2 \log_2 N)O(N2log2 N)，可以在 1s\tt{1s}1s 内通过所有的测试点。
本题的 C++ 代码如下：
本题的 Python 代码如下：
二分答案优化
注意到答案是单调的，因此可以使用二分答案的算法来将算法的单次查询复杂度降低到 O(log2N)O(\log_2 N)O(log2 N) 级别，因此该算法的总时间复杂度为 O(Nlog2N)O(N \log_2 N)O(Nlog2 N)。
优化后的 C++ 代码如下：
优化后的 Python 算法如下：
T4 - AZUSA的计划
题目链接跳转：点击跳转
这道题的难度也不是很高，稍微思考一下即可。
任何事件时间 ttt 对 (a+b)(a + b)(a+b) 取模后，事件可以映射到一个固定的周期内。这样，问题就转化为一个固定长度的区间检查问题。
因此，在读入数字后，将所有的数字对 (a+b)(a + b)(a+b) 取模并排序，如果数字分布（序列的最大值和最小值的差值天数）在 aaa 范围内即可满足将所有的日程安排在休息日当中。但需要注意的是，两个日期的差值天数不能单纯地使用数字相减的方法求得。以正常 777 天为一周作为范例，周一和周日的日期差值为 111 天，而不是 7−1=67 - 1 = 67−1=6 天。这也是本题最难的部分。
如果做过 区间 DP 的用户应该能非常快速地想到如果数据是一个 “环状” 的情况下该如何解决问题（参考题目：石子合并（标准版））。我们可以使用 “剖环成链” 的方法，将环中的元素复制一遍并将每个数字增加 (a+b)(a + b)(a+b)，拼接在原数组的末尾，这样一个长度为 nnn 的环就被扩展为一个长度为 2n2n2n 的线性数组。
最后只需要遍历这个数组内所有长度为 nnn 的区间 [i,n+i−1][i, n + i - 1][i,n+i−1]，判断是否有任意一个区间的最大值和最小值的差在 aaa 以内即可判断是否可以讲所有的日程安排都分不在休息日中。
本题的时间复杂度为 O(Nlog2N)O(N \log_2 N)O(Nlog2 N)。
本题的 C++ 代码如下：
本题的 Python 代码如下：
T5 - 前缀和问题
题目链接跳转：点击跳转
> 我个人认为这道题比最后一道题要难，也许是因为这类题目做的比较少的原因，看到题目后不知道从哪下手。
使用分类讨论的方法，设置一个阈值 SSS，考虑暴力枚举所有 b>Sb > Sb>S 的情况，并离线优化 b≤Sb \le Sb≤S 的情况。将 SSS 设置为 N\sqrt{N}N ，则有：
1. 对于大步长 b>Sb > Sb>S，任意一次查询只需要最多遍历 550550550（即 N\sqrt{N}N ）次就可以算出答案，因此暴力枚举这部分。
2. 对于小步长 b≤Sb \le Sb≤S，按 bbb 分组批量离线查询。
对于大步长部分，每一次查询的时间复杂度为 O(N)O(\sqrt{N})O(N )，在最坏情况下总时间复杂度为 O(N×N)O(N \times \sqrt{N})O(N×N )。对于小步长的部分，每一次查询的时间复杂度约为 O(n)O(n)O(n)，在最坏情况下的时间复杂度为 O(N×N)O(N\times \sqrt{N})O(N×N )，因此本题在最坏情况下的渐进时间复杂度为：
O(N×N)\large{O(N \times \sqrt{N})} O(N×N )
最后，本题的 C++ 代码如下：
本题的 Python 代码如下（不保证可以通过所有的测试点）：
T6 - 划分区间
题目链接跳转：点击跳转
一道线段树优化动态规划的题目，难度趋近于 CSP 提高组的题目和 USACO 铂金组的中等题。一眼可以看出题目是一个典型的动态规划问题，但奈何数据量太大了，O(N2)O(N^2)O(N2) 的复杂度肯定会 TLE。但无论如何都是 “车到山前必有路”，看到数据范围不用怕，先打一个暴力的动态规划再优化。
按照一位 OI 大神的说法：“所有的动态规划优化都是在基础的代码上等量代换”。
与打家劫舍等线性动态规划类似，对于本题而言，设状态的定义为 dpidp_idpi 表示对 [1,i][1, i][1,i] 这个序列划分后可得到的最大贡献。通过暴力遍历 j,(1≤j<i)j, (1 \le j < i)j,(1≤j<i)，表示将 (j,i](j, i](j,i] 归位一组。另设 A(j,i)A(j, i)A(j,i) 为区间 (j,i](j, i](j,i] 的贡献值。根据以上信息可以得到状态转移方程：
dpi=max0≤j<i(dpj+A(j,i))\large{dp_i = \max_{0 \le j<i}{(dp_j + A(j, i))}} dpi =0≤j<imax (dpj +A(j,i))
接下来就是关于 A(j,i)A(j, i)A(j,i) 的计算了。设前缀和数组 SiS_iSi 表示从区间 [1,i][1, i][1,i] 的和，那么 (j,i](j, i](j,i] 区间的和可以被表示为 S[i]−S[j]S[i] - S[j]S[i]−S[j]。根据不同的 S[i]−S[j]S[i] - S[j]S[i]−S[j]，则有以下三种情况：
1. 当 S[i]−S[j]>0S[i] - S[j] > 0S[i]−S[j]>0 时，证明该区间的和是正数，贡献为 i−ji - ji−j。
2. 当 S[i]−S[j]=0S[i] - S[j] = 0S[i]−S[j]=0 时，该区间的和为零，贡献为 000。
3. 当 S[i]−S[j]<0S[i] - S[j] < 0S[i]−S[j]<0 时，证明该区间的和是负数，贡献为 −(i−j)=j−i- (i - j) = j - i−(i−j)=j−i。
综上所述，可以写出一个暴力版本的动态规划代码：
接下来考虑优化这个动态规划，注意到每一次寻找 max\tt{max}max 都非常耗时，每一次都需要遍历一遍才能求出最大值。有没有一种方法可以快速求出某一个区间的最大值呢？答案就是线段树。线段树是一个非常好的快速求解区间最值问题的数据结构。
> 更多有关区间最值问题的学习请参考：[# 浅入线段树与区间最值问题](# 浅入线段树与区间最值问题)
综上，我们可以通过构建线段树来快速求得答案。简化三种情况可得：
因此我们构造三棵线段树，分别来维护这三个区间：
1. max0≤j<idpj\max_{0\le j < i} dp_jmax0≤j<i dpj
2. max0≤j<i(dpj−j)\max_{0\le j < i} (dp_j - j)max0≤j<i (dpj −j)
3. max0≤j<i(dpj+j)\max_{0\le j < i} (dp_j + j)max0≤j<i (dpj +j)
然而我们的线段树不能仅仅维护这个区间，因为这三个的最大值还被 A(j,i)A(j, i)A(j,i) 的三种状态所限制着，因此，我们需要找的是满足 Si−SjS_i - S_jSi −Sj 在特定条件下的最大值。这样就出现了另一个严重的问题，SiS_iSi 的值可能非常的大，因此我们需要对前缀和数组离散化一下（坐标压缩：类似于权值线段树的写法）才可以防止内存超限。
这样子对于每次寻找最大值，都可以在 O(log2N)O(\log_2N)O(log2 N) 的情况下找到。本算法的总时间复杂度也控制在了 O(N×log2N)O(N \times \log_2N)O(N×log2 N) 级别。
本题的 C++ 代码如下：
本题的 Python 代码如下（由于 Python 常数过大，因此没有办法通过这道题所有的测试点，但是代码的正确性没有问题）：
当然也可以用树状数组来写，速度可能会更快一点：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
更新日志：
Dec. 3, 2024：优化了代码的变量名，T6 增加了树状数组解法。
