Codeforces Round #755 (Div. 2) 解题报告

这里是 Codeforces Round #755 (Div. 2) 的解题报告，由于本场 A - C 题和 D - F 题的难度差距过大，故直接从 D 题写起 qwq

CF1584D. Guess the Permutation

Description

给定一个长度为 \(n\) 的排列 \(\{a_n\}\)，初始时有 \(a_i = i\)。

现在选择三个正整数 \(i, j, k\)，其中 \(i < j - 1, j < k \le n\)，然后将 \(a_{i \cdots j - 1}, a_{j \cdots k}\) 这两个子序列翻转。现在你需要通过以下方式询问，来确定这三个数：

每次选择一个区间 \([l, r]\,(l \le r)\)，询问这个区间的逆序对数。一共有 \(t\) 组数据，每组最多可询问 40 次。

数据范围：\(1 \le t \le 100, 4 \le n \le 10^9.\)

Solution

很容易想到通过二分来寻找这三个数的位置。对于整个序列来说，只有 \([i, k]\) 这个区间对逆序对数有贡献。所以显然对于左端点为 1 的区间，区间 \([1, k]\) 到区间 \([1, n]\) 的所有区间的逆序对数均为 \(\dbinom{j - i}{2} + \dbinom{k - j + 1}{2}\)，而对于右端点比 \(k\) 小的所有区间其逆序对数一定比此值小，所以根据这个性质，我们可以二分出 \(k\)。

但是考虑到 \(\lceil \log_2(10^9) \rceil = 30\)，所以我们只有一次二分的机会。我们进而发现，对于 \([j, k]\) 这个区间，\(a_k\) 这个数对区间逆序对数的贡献为 \(k - j\)，所以 \([j, k - 1]\) 这个区间的逆序对数比 \([j, k]\) 这个区间的逆序对数少 \(k - j\)。所以我们只需询问两次就可以得到 \(k - j\)，进一步我们得到 \(j\)。我们知道 \(j\) 以后可以通过同样方法进行两次询问得到 \(i\)，显然这样我们只需要最多 34 次询问就可求出答案。

Code

View on github

CF1584E. Game with Stones

Description

有 \(n\) 堆石子，其中第 \(i\) 堆石子有 \(a_i\) 个石子。每一次你都可以选择还未被取完的相邻两堆石子，从这两堆石子各取走一个石子。注意如果一堆石子被取完，那么和这堆石子相邻的两堆石子仍然不被认为是相邻的。当你恰好能按照上述方法将 \(n\) 堆石子全部取完，那么你就赢得这场游戏。我们称一个序列是可以取胜的，当且仅当以这个序列组成的石子堆数量序列进行游戏可以取胜。对于给定的 \(\{a_n\}\)，求出其有多少个连续的子序列是可以取胜的。一共 \(t\) 组数据。

数据范围：\(1 \le t \le 3 \times 10^5, 1 \le n \le 3 \times 10^5, 0 \le a_i \le 10^9.\)

Solution

我们先考虑如何判断一个序列是可以取胜的。我们发现最容易导致我们不能取胜的是第一堆石子，如果第二堆石子被取完而第一堆石子没有被取完则我们不可能赢得这个游戏。所以我们先取完第一堆石子 \(a_1\)，这时第二堆石子就变成了 \(a_2 - a_1\)，这时我们发现原问题就变成了去掉第一堆石子的子问题。为了更形式化的描述这个判定性问题，我们设 \(d_i\) 表明依次取完前面的石子后，第 \(i\) 堆石子剩余的石子数目。根据定义，显然有 \(d_i = a_i - d_{i - 1}\,(i > 1, d_1 = a_1)\)，进而有 \(d_i = a_i - a_{i - 1} + a_{i - 2} - \cdots + (-1)^{i - 1} a_1\)。而对于一个可以取胜的序列，则需要满足 \(\forall i \in [1, n - 1], d_i \ge 0, d_n = 0\)。但是对于此问题中，石子堆并不是从第 1 堆开始，所以我们还要考虑从第 \(k\) 堆开始的 \(d\) 序列。我们可以设 \(d_{k, i}\) 表明从第 \(k\) 堆为开始，依次取完 \(i - 1\) 堆后，第 \(i\) 堆的石子数目。显然我们有 \(d_{k, i} = d_{1, k + i - 1} + (-1)^{i - 1}d_{1, k - 1}\)。而若 \(d_{k, i} \ge 0\)，则 \(d_{1, k + i - 1} \ge (-1)^i d_{1, k - 1}\)，对于相等的情况同理。

综上所述，所以我们可以计算出第 \(i\) 个位置的 \(d_i\) 后，使用 map 维护前面有多少个合法的位置 \(j\) 满足 \(d_i = (-1)^{i - j}d_j\)，而且容易发现合法的位置是有单调性的，所以我们可以根据奇偶维护 map 中元素的合法性。由于不知道如何具体描述，具体实现可以看代码。

Code

View on github

CF1584F. Strange LCS

Description

给定 \(n\) 个有大写字母和小写字母组成的字符串 \(s_1, s_2, \cdots, s_n\)，每个字母最多在同一字符串中出现两次。求这 \(n\) 个字符串的最长公共子序列，\(t\) 组数据。

数据范围：\(1 \le t \le 5, 2 \le n \le 10.\)

Solution

考虑到 \(n\) 很小，显然可以考虑 dfs，使用 map 记录每个字符串考虑到的位置和该状态下的最长公共子序列。这个爆搜很好实现，因为我们有强大的 STL。

考虑此算法的时间复杂度，每次搜索都要枚举最长公共子序列的下一个字符并判断是否可行所需要花费的时间为 \(O(n\left\vert \Sigma \right\vert)\)。由于每个字符只会在同一字符串中出现两次，则合法的状态的数量为 \(O(2^n \left\vert \Sigma \right\vert)\)。故总时间复杂度为 \(O(n \cdot 2^n \cdot \left\vert \Sigma \right\vert^2)\)。

Code

View on github