10
ACGO排位赛#13 - 题目解析
> 感谢大家参加本次排位赛！
T1 - 纪元流星雨
题目链接跳转：点击跳转
也没有特别大的难度，手动模拟一下就可以了。
解题步骤
1. 先计算出这个人一生中第一次看到流星雨的日子：(E+B)mod 50(E + B) \mod 50(E+B)mod50 。
2. 计算出剩余一生中可以看到流星雨的年份 YYY。
3. 答案就是 Y50+1\dfrac{Y}{50} + 150Y +1。
代码实现
本题的 C++ 代码如下：
本题的 Python 代码如下：
T2 - MARCONCATENATE
题目链接跳转：点击跳转
根据题目模拟就可以了，没有什么难度。
代码实现
本题的 C++ 代码如下：
本题的 Python 代码如下：
T3 - TNT接力
题目链接跳转：点击跳转
> 这道题是本次比赛的第三道题，但是许多参赛选手认为这道题是本场比赛最难的题目。
解题思路
1. 滑动窗口：使用滑动窗口技术，先在前 KKK 个方块中计算有多少个空气方块。接着，随着窗口向右滑动，我们移除窗口左端的一个方块，并加入窗口右端的一个方块，更新空气方块的数量。
2. 最大空气方块数量：我们维护一个变量 mx，表示在当前窗口中最多有多少个空气方块。
3. 计算答案：每次计算答案时，使用 K−最大空气方块数量K - \text{最大空气方块数量}K−最大空气方块数量 来表示最小的 TNT 方块数量，这表示需要多少步才能避免 TNT 的塌陷。如果 K≥NK \geq NK≥N，表示玩家可以直接跳过整个桥，输出 −1-1−1 。
时间复杂度
每次处理一个序列的时间复杂度是 O(N)O(N)O(N)，其中 NNN 是方块序列的长度。整体复杂度为 O(T×N)O(T \times N)O(T×N)，其中 TTT 是测试用例的数量。关于本体，还可以用二分来进一步优化。本文不过多陈述。
代码实现
本题的 C++ 代码如下：
本题的 Python 代码如下：
T4 - 小丑牌
题目链接跳转：点击跳转
解题思路
也是一道模拟题，但需要注意以下几点：
1. 同一个点数可能会出现五次，那么此时应该输出 High Card（如题意）。
2. 如果有一个牌型符合上述多条描述，请输出符合描述的牌型中在规则中最后描述的牌型。
3. 牌的数量不局限于传统的扑克牌，每张牌可以题目中四种花色的任意之一。
代码实现
本题的 C++ 代码如下：
T5 - VERTEX VERSE
题目链接跳转：点击跳转
直接模拟情况就可以了，但是细节比较多需要注意一下。
时间复杂度
其中 work 函数会在每次迭代中被调用 444 次，每次的复杂度是 O(E)O(E)O(E)。因此，对于每个输入的 qqq 对点，总的时间复杂度是 Θ(4×q×E)\Theta(4 \times q \times E)Θ(4×q×E)，即O(q×E)O(q \times E)O(q×E)。但在最坏情况下，图中的边数 EEE 可以接近 O(n×m)O(n \times m)O(n×m)，因此总时间复杂度是 O(q×n×m)O(q \times n \times m)O(q×n×m) 。
代码实现
本题的 C++ 代码如下：
另一种写法如下：
T6 - 最优政府大楼选址-2
题目链接跳转：点击跳转
解题思路
本题有好多解决方法，可以使用带权中位数写 N=105N = 10^5N=105 ，为了考虑到朴素的模拟退火算法，本题的数据范围被适当降低了。如果学过模拟退火算法做这道题就非常的简单，把模板的评估函数改成计算意向程度的函数即可。
时间复杂度
模拟退火算法的时间复杂度约为 Θ(k×N)\Theta(k \times N)Θ(k×N)。其中 kkk 表示的是在模拟退火过程中计算举例的 F2 函数的调用次数。NNN 表示数据规模。
代码实现
本题的 C++ 代码如下（模拟退火）：
使用加权中位数算法的 C++ 代码：
T7 - 乌龟养殖场
题目链接跳转：点击跳转
前置知识：
1. 了解过基本的动态规划。
2. 熟练掌握二进制的位运算。
> 至于为什么放了一道模版题，原因是因为需要凑到八道题目，实在凑不到了，找了一个难度适中的。
题解思路
这是一道典型的状压动态规划问题。设 dpi,jdp_{i, j}dpi,j 表示遍历到第 iii 行的时候，当前行以 j(base2)j_{(base2)}j(base2) 的形式排列乌龟可以构成的方案数。
对于每一行的方案，我们可以用一个二进制来表示。例如二进制数字 101001010010100，表示有一个横向长度为 555 的场地中，第 1,31, 31,3 号位置分别放置了一只小乌龟。因此，每一种摆放状态都可以用一个二进制数字来表示。我们也可以通过遍历的方式来遍历出二进制的每一种摆放状态。
首先，我们预处理出横排所有放置乌龟的合法情况。根据题意，两个乌龟不能相邻放置，因此在二进制中，不能有两个 111 相邻。如何预处理出这种情况呢？我们可以使用位运算的方法：
如果存在一个二进制数字有两个 111 相邻，那么如果我们对这个数字 xxx 进行位运算操作 (x << 1) & x 的结果或 (x >> 1) & x 的结果必定大于等于 111。我们通过把这种情况排除在外。同时，我们还需要注意有些格子中不能放置乌龟。这一步也可以通过二进制的方法预处理掉，如果网箱在第 iii 一个格子中不能放置乌龟，那么在枚举所有方案数的时候直接忽略掉第 iii 位为 111 的情况即可。
接下来如何保证上下两行的乌龟不冲突？假如上一行的摆放状态是 yyy，当前行的摆放状态为 jjj，如果 i & j 的结果大于等于 111，也可以证明有两个数字 111 在同一位置上。因此我们也需要把这种情况排除在外。
综上所述，我们可以得出状态转移方程：dpi,j=dpi,j+dpi−1,kdp_{i, j} = dp_{i, j} + dp_{i-1, k}dpi,j =dpi,j +dpi−1,k 。其中，jjj 和 kkk 表示所有横排合法的方案。答案就是 ANS=∑j=02M−1dpN,j\mathtt{ANS} = \sum_{j=0}^{2^M-1}{dp_{N, j}}ANS=∑j=02M−1 dpN,j 。
状态的初始化也很简单，另 dp0,0=1dp_{0, 0} = 1dp0,0 =1 ，表示一只乌龟都不放有一种摆放方案。
时间复杂度
通过观察上述代码，在枚举所有状态和转移状态的时候有三层循环，分别是枚举当前行、枚举当前行的合法摆放情况以及枚举上一行的摆放情况。因此总时间复杂度约为 O(n×2M×2M)=O(n×2M2)=O(n×4M)O(n \times 2^M \times 2^M) = O(n \times 2^{M^2}) = O(n \times 4^M)O(n×2M×2M)=O(n×2M2)=O(n×4M)。但由于合法的摆放数量远远少于 2M2^M2M，因此实际情况下程序运行的速度会快许多。
代码实现
本题的代码实现如下。在输出的时候需要减一，因为不放置也是一种合法情况，根据题目要求需要把这一合法情况排除。
本题的 Python 代码如下，Python 可以通过本题的所有测试点：
再提供一个暴力解法用于对拍：
T8 - 数据中心能耗分析
题目链接跳转：点击跳转
本文仅针对对线段树有一定了解且并且有着较高的程序设计能力的选手。本文的前置知识如下：
1. 线段树的构造与维护 - 可以参考文章 浅入线段树与区间最值问题。
2. 初中数学 - 完全平方和公式和完全立方和公式。
3. 取模 - 之如何保证对所有整数取模后的结果为非负整数 - 可以参考本题的 说明/提示 部分。
> 原本出题的时候我并不知道这道题在许多 OJ 上是有原题的，so sad（下次再改进）。
题目本身应该非常好理解，就是给定一个数组，让你设计一个程序，对程序进行区间求立方和和区间修改的操作。但本题的数据量比较大，N,MN, MN,M 最大可以达到 10510^5105，对于每一次修改和查询都是 O(N)O(N)O(N) 的时间复杂度，显然用暴力的方法时间复杂度绝对会超时，最高会到 O(N2∗M)O(N^2 * M)O(N2∗M) （大概需要 115115115 天的时间才可以搞定一个测试点）。当看到区间查询和维护操作的时候，不难想到用线段树的方法，在线段树中，单次操作的时间复杂度约为 O(log2N)O(log_2 N)O(log2 N)，即使当 NNN
非常大的时候线段树也可以跑得飞起。
解题思路
不得不说，这是一道比较恶心的线段树区间维护的题目。不光写起来比较费劲，而且维护操作运算量比较大。稍有不慎就会写歪（因此写这道题的时候要集中注意力，稍微一个不起眼的问题就容易爆 000）。
本题的主要难点就是对一个区间内进行批量区间累加的操作。很容易就想到跟完全立方公式的联系：(a+b)3=a3+3a2b+3ab2+b3(a+b)^3 = a^3 +3a^2b + 3ab^2 + b^3(a+b)3=a3+3a2b+3ab2+b3。区间累加操作也只不过是对区间的所有数字都进行该操作，并对所有操作的结果求和就是该区间进行操作后的立方和。化简可得：
ANS=∑i=1n(ai+x)3=(a1+b)3+(a2+b)3+⋯+(an+b)3=(a13+3a12b+3a1b2+b3)+(a23+3a22b+3a2b2+b3)+⋯+(an3+3an2b+3anb2+b3)=(a13+a23+⋯+an3)+3b(a12+a22+⋯+an2)+3b2(a1+a2+⋯+an)+nb3=∑i=1nai3+3b∑i=1nai2+3b2∑i=1nai+nb3\begin{align} \mathtt{ANS} &= \sum_{i=1}^{n}{(a_i+x)^3}\\ &= (a_1+b)^3+(a_2+b)^3+ \cdots + (a_n+b)^3 \\
&= (a_1^3 + 3a_1^2b + 3a_1b^2 + b^3) + (a_2^3 + 3a_2^2b + 3a_2b^2 + b^3) + \cdots + (a_n^3 + 3a_n^2b + 3a_nb^2 + b^3) \\ &= (a_1^3 + a_2^3 + \cdots + a_n^3) + 3b(a_1^2 + a_2^2 + \cdots + a_n^2) + 3b^2(a_1 + a_2 + \cdots + a_n) + nb^3 \\ &= \sum_{i=1}^{n}{a_i^3} + 3b\sum_{i=1}^{n}{a_i^2} +
3b^2\sum_{i=1}^{n}{a_i} + nb^3 \end{align} ANS =i=1∑n (ai +x)3=(a1 +b)3+(a2 +b)3+⋯+(an +b)3=(a13 +3a12 b+3a1 b2+b3)+(a23 +3a22 b+3a2 b2+b3)+⋯+(an3 +3an2 b+3an b2+b3)=(a13 +a23 +⋯+an3 )+3b(a12 +a22 +⋯+an2 )+3b2(a1 +a2 +⋯+an )+nb3=i=1∑n ai3 +3bi=1∑n ai2 +3b2i=1∑n ai +nb3
综上所述，我们只需要用线段树维护三个字段，分别是区间的立方和、区间的平方和以及区间和。在维护平方和的过程中与维护立方和类似，根据完全平方公式 (a+b)2=a2+2ab+b2(a+b)^2 = a^2 + 2ab + b^2(a+b)2=a2+2ab+b2。经过累加和化简可得：
ANS=∑i=1n(ai+x)2=(a1+b)2+(a2+b)2+⋯+(an+b)2=(a12+2a1b+b2)+(a22+2a2b+b2)+⋯+(an2+2anb+b2)=(a12+a22+⋯+an2)+2b(a1+a2+⋯+an)+nb2=∑i=1nai2+2b∑i=1nai+nb2\begin{align} \mathtt{ANS} &= \sum_{i=1}^{n}{(a_i+x)^2}\\ &= (a_1+b)^2 + (a_2+b)^2 + \cdots + (a_n+b)^2 \\ &= (a_1^2 + 2a_1b + b^2) + (a_2^2 + 2a_2b + b^2)
+ \cdots + (a_n^2 + 2a_nb + b^2) \\ &= (a_1^2 + a_2^2 + \cdots + a_n^2) + 2b(a_1 + a_2 + \cdots + a_n) + nb^2 \\ &= \sum_{i=1}^{n}{a_i^2} + 2b\sum_{i=1}^{n}{a_i} + nb^2 \end{align} ANS =i=1∑n (ai +x)2=(a1 +b)2+(a2 +b)2+⋯+(an +b)2=(a12 +2a1 b+b2)+(a22 +2a2 b+b2)+⋯+(an2 +2an b+b2)=(a12 +a22 +⋯+an2
)+2b(a1 +a2 +⋯+an )+nb2=i=1∑n ai2 +2bi=1∑n ai +nb2
以上三个字段可以在构造线段树的时候一并初始化，之后的每次更新直接修改懒标记就可以了。一切都交给 push_down() 函数。在每次区间查询和修改之前都进行懒标记下放操作，对区间进行维护。具体维护操作如下：
注意事项
1. 请注意取模，为了保证答案正确性，请在每一步操作的时候都对结果取模。
2. 开 long long，不然的话只能过前三个测试点（出题人还是挺好的，留了三个小的测试点骗粉）。
3. 在维护立方和、平方和以及和的时候，请注意维护的顺序。应当先维护立方和，再维护平方和，最后再维护区间总和。
4. 注意线段树数组的大小，应当为 4×N4 \times N4×N。
5. 建议使用读入优化，直接使用 cin 的效率比 std 慢约 100%100\%100% 。
时间复杂度
线段树单次查询和修改的复杂度约为 O(log2N)O(log_2 N)O(log2 N)，初始化的时间复杂度为 Θ(N)\Theta(N)Θ(N)，因此本代码的整体时间复杂度可以用多项式 Θ(N+M⋅log2(N))\Theta(N + M \cdot log_2(N))Θ(N+M⋅log2 (N)) 来表示，整体代码的时间复杂度就为 O(M⋅log2(N))O(M \cdot log_2(N))O(M⋅log2 (N))。在极限数据下，程序只需要 160ms160ms160ms 就可以完成暴力一整年所需的工作。
代码实现
1. 代码使用了宏定义，方便后期进行调式。
2. 以下代码与普通的线段树无太大区别，但请着重关注 push_down() 下放操作。
以下是本题的 Python 代码，但由于 Python 常数过大，没有办法通过所有的测试点：
有帮助，赞一个