算法周赛round30

T1

本题考察字符串。

如果读入的不等式中有大于的也有小于的会比较复杂，因此我们应当先把不等号的方向统一。我们这里不妨都统一成大于号。

string a, b, c;
cin >> a >> b >> c;
if (a[1] == '<') swap(a[0], a[2]);
if (b[1] == '<') swap(b[0], b[2]);
if (c[1] == '<') swap(c[0], c[2]);

接着考虑三个砝码重量的相对大小。我们不妨考虑以下三个情况：

A>B
A>C
B>C

和

A>B
B>C
C>A

和

A>B
A>C
A>B

第一种情况是可以推断出相对重量大小：$C<B<A$。第二种情况会出现矛盾（A 大于 B，B 大于 C，理论上 A 要大于 C，但是测出了 C 大于 A，因此是矛盾的）。第三种情况无法推断出 B 和 C 的相对重量大小。

更进一步地说，能够推断出相对大小的形式只有以下三种（假设最重的是 A）：

A>B
A>C
B>C

或

A>B
B>C
A>C

或

A>B
A>C
B>C

分成三种情况，分别判断即可。不属于三种情况的，判断为矛盾。

if (a[0] == b[0]) cout << c[2] << c[0] << a[0] << endl;
else if (b[0] == c[0]) cout << a[2] << a[0] << b[0] << endl;
else if (a[0] == c[0]) cout << b[2] << b[0] << c[0] << endl;
else cout << "Impossible" << endl;

---

T2

这是一个数学直觉题（多尝试）。

可以发现令 $x=n,y=n+1,z=n(n+1)$ 时永远成立。

---

T3

本题考察贪心。

首先特判特殊情况，当 $n=1$ 时，输出 $0$。对于其他情况，不妨将读入的住所的坐标 $x_i$ 升序排序，使得 $x_1\leq x_2\leq ...\leq x_n$。

拜访轨迹有两种可能：

• 先往右走一部分，然后调头去拜访左边的。
  • 先往右走到 $x_n$ 的位置，然后调头去拜访到 $x_2$ 即可。
  • 先往右走到 $x_{n-1}$ 的位置，然后调头去拜访到 $x_1$ 即可。
• 先往左走一部分，然后调头去拜访右边的。
  • 先往左走到 $x_1$ 的位置，然后调头去拜访到 $x_{n-1}$ 即可。
  • 先往左走到 $x_{2}$ 的位置，然后调头去拜访到 $x_n$ 即可。

情况一的两种移动距离分别为 $|x_n-x_0|+|x_n-x_2|$ 和 $|x_{n-1}-x_0|+|x_{n-1}-x_1|$。

情况二的两种移动距离分别为 $|x_1-x_0|+|x_1-x_{n-1}|$ 和 $|x_2-x_0|+|x_n-x_{2}|$。

答案在这些值中取 $\min$ 即可。

时间复杂度：$O(n\log n)$。

---

T4

本题考察双指针、滑动窗口。

首先预处理出字符串有多少个不同的字符记为 $tot$。

接下来枚举 $l$，双指针移动 $r$，在移动 $r$ 时维护目前 $[l,r]$ 中有多少个不同的字符记为 $cnt$。

当 $cnt=tot$ 时，说明 $[l,r]$ 中有 $tot$ 个不同的字符，此时 $r-l+1$ 就是一个符合要求的答案。

当 $l\gets l+1$ 时，判断是否要更新 $cnt$。（如果 $s_l$ 是唯一的字符，则 $cnt$ 需要减一。）

时间复杂度：$O(n)$。

\[ \begin{array}{ll} 1 & r \gets 0 \\ 2 & \textbf{for } l \gets 1 \textbf{ to } n \\ 3 & \qquad \textbf{while } (r+1 \le n)\ \textbf{and}\ (cnt < tot) \\ 4 & \qquad\qquad r \gets r + 1 \\ 5 & \qquad\qquad \textbf{if not }(mp\text{ contains } s[r]) \\ 6 & \qquad\qquad\qquad cnt \gets cnt + 1 \\ 7 & \qquad\qquad mp[s[r]] \gets mp[s[r]] + 1 \\ 8 & \qquad \textbf{if } cnt = tot \\ 9 & \qquad\qquad ans \gets \min(ans, r - l + 1) \\ 10 & \qquad mp[s[l]] \gets mp[s[l]] - 1 \\ 11 & \qquad \textbf{if } mp[s[l]] = 0 \\ 12 & \qquad\qquad cnt \gets cnt - 1 \\ 13 & \qquad\qquad \text{erase } mp[s[l]] \\ \end{array} \]

---

T5

注意到 $a_i + a_j \le 2\times 10^9 \le 2^{31}$，因此只需考虑指数 $x \in [1,30]$。

枚举每个 $j \in [1,n]$，并对每个 $x\in[1,30]$ 计算对应的常数 $v = 2^x$。问题转化为统计满足

\[ i < j,\quad a_i + a_j = v \]

的数对数量。

对固定的 $j$，需要查询前缀区间 $[1, j-1]$ 中值为 $v - a_j$ 的元素个数。遍历过程中维护一个哈希表记录各数值出现次数，查询时直接在表中查找 $v - a_j$ 的出现次数即可。

由于值域较大，使用 unordered_map 存储频次。整体时间复杂度为 $O(31n)$。实现时需关注常数优化以通过时间限制。

\[ \begin{array}{ll} 1 & \texttt{map<int, int> cnt} \\ 2 & \textbf{for } i \gets 1 \textbf{ to } n \\ 3 & \qquad \textbf{for } j \gets 1 \textbf{ to } 30 \\ 4 & \qquad\qquad v \gets 2^j \\ 5 & \qquad\qquad \textbf{if } \text{cnt contains } (v - A[i]) \\ 6 & \qquad\qquad\qquad ans \gets ans + \text{cnt}[v - A[i]] \\ 7 & \qquad \text{cnt}[A[i]] \gets \text{cnt}[A[i]] + 1 \\ \end{array} \]

---

T6

为了方便处理，不妨先将题目中的 $a_i,b_i$ 从小到大进行排序。接着考虑如何计算 $r$。

一个思路

考虑二分距离 $r$，尝试转换为判定当前距离下信号塔能否将信号覆盖每一个城市。

这样做是可行的。具体实现如下：

• 枚举所欲的信号塔 $b_1\sim b_n$。
• 双指针移动 $j$ 维护城市，若满足 $b_i-r\leq a_j\leq b_i+r$，则将 $j$ 移动到下一个城市。

双指针移动过程中，如果出现了 $j=n$，则说明所有城市被覆盖。返回 true 否则 false。

另一个思路

不妨换个思路，考虑对于每个城市（坐标为 $a_i$）查找最近的信号塔。我们首先二分查找，使用 lower_bound 函数找到第一个坐标不小于 $a_i$ 的信号塔 $b_j$，那么距离这个城市最近的信号塔不是 $b_{j−1}$ 就是 $b_j$，在两者中找到最近的信号塔即可。最后的答案是在所有的最近距离中取最大值。

注意判断 $j,j-1$ 是否越界。