直播预告
直播时间：3月9日（周六）下午4点-6点
直播地址： B站ACGO官方账号
直播内容：排位赛#5复盘（欢迎观看大型翻车现场）
主讲人：アイドル老师
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ACGO 第五次排位赛题解
T1、 ACGO社区
题目解析
考虑使用一种数据结构来高效维护用户 AAA 和用户 BBB 之间的关系。
使用 map<int, set<int>> user 来维护每位用户关注的所有其他用户：
user[A] 表示用户 AAA 关注的所有用户的集合。
如果满足条件 user[A] 中存在 BBB 且 user[B] 中存在 AAA 则说明 AAA 和 BBB 目前属于互相关注的状态。
AC代码
复杂度分析
对于每个操作时间复杂度为 O(logN)O(\log{N})O(logN)，总时间复杂度为 O(QlogN)O(Q\log{N})O(QlogN)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2、添加元素让数组变为好数组
提示
A⊕A=0A \oplus A = 0A⊕A=0
题目解析
任意数字与自己异或的结果为 000。
令原数组和为 sumsumsum，异或和为 xsumxsumxsum，那么显然我们可以在数组后添加两个元素：xsumxsumxsum 和 sum+xsumsum+xsumsum+xsum。
这样对于添加元素后的数组的和为 (sum+xsum)×2(sum+xsum) \times 2(sum+xsum)×2，异或和为 sum+xsumsum+xsumsum+xsum，满足题目要求。
AC代码
复杂度分析
遍历一遍数组求得 sumsumsum 和 xsumxsumxsum，时间复杂度 O(n)O(n)O(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3、替换子串使两串相等
题目解析
两种操作本质上就是可以把 sss 中的 'a' 向右移动，'c' 向左移动。
所以把 sss 和 ttt 中的所有字符 'b' 去掉之后，两个字符串应该是相同的。
另外，由于 'a' 不能向左移动，'c' 不能向右移动，所以要检查字符串 sss 和 ttt 中，对应的字符 'a' 和字符 'b' 的下标。
对于字符 'a'，在 sss 中每个字符 'a' 在字符串 ttt 中都应该 有一个下标大于等于 它的 'a' 与之对应；
相对对应的，在 sss 中每个字符 'c' 在字符串 ttt 中都应该 有一个下标小于等于 它的 'c' 与之对应。
AC代码
复杂度分析
检查 sss 和 ttt 去掉所有字符 'b' 之后是否相等时间复杂度为 O(n)O(n)O(n)。
检查 sss 中字符 'a' 和 'b' 相对于在字符串 ttt 中的位置时间复杂度为 O(n)O(n)O(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4、使两方格相等的最少操作次数
题目解析
方格 AAA 的状态可以用 (P,Q)(P, Q)(P,Q) 来表示，其中 P=(P1,P2,…,PH)P = (P_1, P_2, \ldots, P_H)P=(P1 ,P2 ,…,PH ) 是代表 行 原始位置的排列，而 Q=(Q1,Q2,…,QW)Q = (Q_1,Q_2, \ldots, Q_W)Q=(Q1 ,Q2 ,…,QW ) 是代表 列 原始位置的排列。
一开始 P=(1,2,…,H),Q=(1,2,…,W)P = (1, 2, \ldots, H), Q = (1, 2, \ldots, W)P=(1,2,…,H),Q=(1,2,…,W)；交换相邻的行或列相当于交换 PPP 或 QQQ 中相邻的两个元素。
另外，当前方格中 (i,j)(i, j)(i,j) 上的整数可以从 AAA 的初始状态的 (i,j)(i, j)(i,j) 上的整数获得。
例如，对于题目中第一个样例转换的过程，状态 (P,Q)(P, Q)(P,Q) 变化为
P=(1,2,3,4),Q=(1,2,3,4,5)→P=(1,2,3,4),Q=(1,2,3,5,4)→P=(1,3,2,4),Q=(1,2,3,5,4)→P=(1,3,2,4),Q=(1,3,2,5,4). \begin{aligned} &P = (1, 2, 3, 4), Q = (1, 2, 3, 4, 5)\\ \rightarrow &P = (1, 2, 3, 4), Q = (1, 2, 3, 5, 4)\\ \rightarrow &P = (1, 3, 2, 4), Q = (1, 2, 3, 5, 4)\\\rightarrow &P = (1, 3, 2, 4), Q
= (1, 3, 2, 5, 4).\\ \end{aligned} →→→ P=(1,2,3,4),Q=(1,2,3,4,5)P=(1,2,3,4),Q=(1,2,3,5,4)P=(1,3,2,4),Q=(1,2,3,5,4)P=(1,3,2,4),Q=(1,3,2,5,4).
(P,Q)(P, Q)(P,Q) 的总数是 PPP 的排列的数量和 QQQ 的排列的数量的乘积即 H!W!≤5!×5!=14400H!W! \leq 5!\times 5! = 14400H!W!≤5!×5!=14400。
因此，我们对这 H!W!H!W!H!W! 个 (P,Q)(P, Q)(P,Q)，即 (1,2,…,H)(1, 2, \ldots, H)(1,2,…,H)的排列 PPP 和 (1,2,…,W)(1, 2, \ldots, W)(1,2,…,W) 的排列 QQQ 中的每一个，执行以下操作：
* 首先，根据当前的 (P,Q)(P, Q)(P,Q) 和 AAA 构造方格 CCC 并判断和方格 BBB 是否相等。
* 如果相等，求从初始状态到达当前 (P,Q)(P, Q)(P,Q) 的最小操作次数。
如果没有任意一对 (P,Q)(P, Q)(P,Q) 和 AAA 构造出的方格 CCC 与方格 BBB 相同，那么就不可能使方格 AAA 和方格 BBB 相等，输出 −1-1−1。
从初始状态到达当前状态 (P,Q)(P, Q)(P,Q) 所需的最小操作数是以下操作之和：
* 通过重复交换相邻元素从初始序列 (1,2,…,H)(1, 2, \ldots, H)(1,2,…,H) 得到排列 PPP 所需的最少操作次数；
* 通过重复交换相邻元素从初始序列 (1,2,…,W)(1, 2, \ldots, W)(1,2,…,W) 得到排列 QQQ 所需的最小操作次数；
从排列 (1,2,…,N)(1, 2, \ldots, N)(1,2,…,N) 开始，通过重复交换相邻的两个元素得到所需的排列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N)A=(A1 ,A2 ,…,AN ) 所需的运算次数为排列 AAA 中的 逆序对 的数量，即
* 1≤i<j≤N1 \leq i \lt j \leq N1≤i<j≤N，Ai>AjA_i \gt A_jAi >Aj 的 (i,j)(i, j)(i,j) 的个数。
因此，从初始状态到 (P,Q)(P, Q)(P,Q) 所需的操作次数就是 PPP 的 逆序对 的数量与 QQQ 的 逆序对 的数量之和。
AC代码
复杂度分析
枚举所有的 (P,Q)(P, Q)(P,Q) 时间复杂度为 O(H!W!)O(H!W!)O(H!W!)；
构造方格 CCC 并判断是否和 BBB 相等的时间复杂度为 O(HW)O(HW)O(HW)；
求 PPP 的逆序对数量时间复杂度为 O(H2)O(H^2)O(H2)；
求 WWW 的逆序对数量时间复杂度为 O(W2)O(W^2)O(W2)；
因此总的时间复杂度为 O(H!W!×(HW+H2+W2))O(H!W! \times (HW + H^2 + W^2))O(H!W!×(HW+H2+W2))。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5、照片装裱
题目解析
我们可以把所有的照片和相框的宽度和长度放在一块，并按照宽度从大到小排序，如果一个照片和一个相框的宽度相同，则将相框放在前面。
接下来准备一个容器 SSS，并遍历排序后的照片和相框：
* 若当前为相框 (Ci,Di)(C_i, D_i)(Ci ,Di )，则将 DiD_iDi 放入 SSS 中。
* 若当前为照片 (Ai,Bi)(A_i, B_i)(Ai ,Bi )，则从 SSS 中找最小的大于等于 BiB_iBi 的元素，并将其从 SSS 中删除。如果无法找到这样的元素，说明这个照片无法找到一个相框来装裱，答案为 No\tt{No}No。
如果成功遍历完所有的元素，答案为 Yes\tt{Yes}Yes。
如果使用一个普通数组充当容器 SSS，那么以上算法的时间复杂度为 O(NM)O(NM)O(NM)，但是我们可以使用 std::multiset 作为 SSS 来解决这个问题，时间复杂度为： O((N+M)log(N+M))O((N + M)\log{(N + M)})O((N+M)log(N+M))。
AC代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6、方格染色
题目解析
涂黑的一组方格与棋子移动的方法相关，因此只需计算到达每个方格的方案数即可。
若我们忽略解法的复杂度我们可以使用以下这种动态规划的方法来解决这个问题：
当 AiA_iAi 较大时，对 jjj 的迭代不会重复很多次，所以这种方法似乎是合理的，但如果以 Ai=[1,1,…,1]A_i=[1,1,\dots,1]Ai =[1,1,…,1] 为例，则需要花费 O(N2)O(N^2)O(N2) 的时间，所以这种算法无法通过本题。
考虑在 AiA_iAi 相同的情况下集体更新。具体来说，在从 iii 开始的转换过程中，如果存在 jjj 使得 Ai=AjA_i=A_jAi =Aj ，那么之后在 jjj 的循环过程中将它们全部相加。
时间复杂度
上述方法可以在 O(NN)O(N\sqrt N)O(NN ) 的时间复杂度内完成。
如果每个 AiA_iAi 在更新的过程中全部重复掉，那么对于每个 AiA_iAi 只需要将其移动一次，之后让 AjA_jAj 代替 AiA_iAi 更新。
最坏的情况是没有 "一起更新"，并且 AiA_iAi 的值尽可能的小。
在这种情况下，AAA 就像这个样子 [1,2,2,3,3,3,4,⋯ ][1, 2, 2, 3, 3, 3, 4, \cdots][1,2,2,3,3,3,4,⋯]，而那么 jjj 的调用次数为：
N1+N2+N2+N3+N3+N3+N4+⋯\frac{N}{1} + \frac{N}{2} + \frac{N}{2} + \frac{N}{3} + \frac{N}{3} + \frac{N}{3} + \frac{N}{4} + \cdots 1N +2N +2N +3N +3N +3N +4N +⋯
即：
N×(1+2×12+3×13+4×14+⋯+M×1M+⋯)N \times \big(1 + 2 \times \frac{1}{2} + 3 \times \frac{1}{3} + 4 \times \frac{1}{4} + \cdots + M \times \frac{1}{M} + \cdots\big) N×(1+2×21 +3×31 +4×41 +⋯+M×M1 +⋯)
上式中 1+2+3+4+⋯+M=M×(M+1)2=N1 + 2 + 3 + 4 + \cdots + M = \frac{M \times (M + 1)}{2} = N1+2+3+4+⋯+M=2M×(M+1) =N 所以 O(M)=O(N)O(M) = O(\sqrt{N})O(M)=O(N )
那么我们可以由上式得到：
O(N×(1+1+1+⋯+1⏞M+⋯))=O(NN)O \big(N \times \big( \overbrace{1 + 1 + 1 + \cdots + 1}^{M} + \cdots\big)\big) = O(N\sqrt{N}) O(N×(1+1+1+⋯+1 M +⋯))=O(NN )
故整体算法时间复杂度为 O(NN)O(N\sqrt{N})O(NN )。
AC代码
