算法周赛round34

T1

题意

三个人：小 s、小 a、小 b 玩乒乓球，共玩 $n$ 局。

• 第 $1$ 局：小 a 和小 b 打，小 s 旁观（不上场）。
• 每局结束后：败者和旁观者交换位置，所以下一局的对阵双方是“本局胜者 + 本局旁观者”。

小 s 能控制每局胜负。问他最多、最少能上场多少局。

---

思路

把“是否上场”按局号来观察。

• 第 $1$ 局小 s 一定旁观，所以第 $1$ 局不上场。
• 由于规则是“胜者 + 旁观者”打下一局，所以只要某一局小 s 在旁观，下一局他必定上场。

接着看小 s 上场时他可以怎么操作：

• 求最多上场局数

从第 $2$ 局开始，小 s 必定上场一次（因为第 $1$ 局他旁观）。

如果小 s 每次上场都让自己获胜，那么下一局对阵是“胜者（小 s）+旁观者”，小 s 仍然会上场。

因此他可以从第 $2$ 局一直连打到第 $n$ 局，上场局数为： $n-1$。

• 求最少上场局数

如果小 s 想尽量少上场，那么他在每次上场时都让自己输：

• 小 s 输了会变成下一局的旁观者，所以能跳过下一局；
• 但由于“旁观者下一局必上场”，他会在再下一局被迫上场。

于是形成节奏：第 2 局上场，第 3 局旁观，第 4 局上场，第 5 局旁观……

也就是小 s 在所有偶数局上场，最少上场次数为从 $2$ 到 $n$ 的偶数个数： $$\text{min}=\left\lfloor \frac{n}{2}\right\rfloor$$

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

---

T2

题意

给定一个长度为 $n$ 的正整数序列 $a$，需要构造一个 $1\sim n$ 的排列 $b$，使得所有乘积

\[ a_i \times b_i \quad (1\le i\le n) \]

两两不同。

如果可以构造，输出任意一个满足条件的排列 $b$； 如果无法构造，输出 -1。

---

思路

题目要求的是：

避免出现 $a_i \times b_i = a_j \times b_j\ (i\neq j)$

一个非常自然、直观且一定可行的构造思路是：

小数配小数，大数配大数

为什么这样一定可行？

1. 将下标按 $a_i$ 的大小排序：
   • $a$ 小的在前
   • $a$ 大的在后
2. 将 $b$ 取为 $1\sim n$，按顺序分配给排好序的 $a$

这样得到的乘积序列为：

\[ a_{(1)}\times 1,\ a_{(2)}\times 2,\ \dots,\ a_{(n)}\times n \]

由于：

• $a_{(i)} \le a_{(j)}$ 且 $i<j$
• 同时 $i<j$

可以保证： $$ a_{(i)}\times i < a_{(j)}\times j $$

因此所有乘积严格递增，一定互不相同。

---

构造方法

1. 记录每个 $a_i$ 和它的原始下标
2. 按 $a_i$ 从小到大排序
3. 排序后的第 $i$ 个元素分配 $b=i$
4. 按原下标还原输出 $b$

注意：

题目保证 $a_i \ge 1$，因此该构造在所有数据范围内都成立，一定有解，无需输出 -1。

---

具体实现

• 使用 pair<int, int> a[N] 存储 $(a_i, i)$
• 排序后构造 $b$。令 b[a[i].second] = i。记录原本 $a$ 的第 $i$ 个元素在 $b$ 中的位置。
• 输出 $b$。
• 时间复杂度 $O(n\log n)$
• 空间复杂度 $O(n)$

---

T3

题意

有 $n$ 件商品，第 $i$ 件价格 $v_i$、性价比 $w_i$。 初始时小 Y 会买下 性价比最大的所有商品。

之后有 $m$ 次事件：

1. 新增商品（新编号为 $n+i$），给出价格 $x_i$ 和性价比 $y_i$；
2. 修改编号为 $x_i$ 的商品的性价比为 $y_i$。

注意：买下的商品 不会卖出。

每次事件后：

• 令 $L$ 为「已买商品」中 最低 的性价比；
• 小 Y 会把所有 未买 且性价比 $\ge L$ 的商品全部买下。

输出每次事件后总花销。

---

思路

核心就是维护两件事：

• 已买商品集合：需要能随时得到最低性价比 $L$ 用 set<pair<w, id>> bought 存已买商品（按 $w$ 排序），则

\[ L = \min w = \text{bought.begin()->first} \]

• 未买商品集合：需要快速找到所有 $w \ge L$ 并把它们全部买下 用 set<pair<w, id>> unbought 存未买商品（同样按 $w$ 排序）。 每次事件后，从

\[ it = \text{lower_bound}(\{L,0\}) \]

到 end() 的所有元素都满足 $w \ge L$，逐个搬到 bought，并累加花费。

关键性质： 买入的都是 $w \ge L$ 的商品，因此 不会让已买集合的最小值变小，也不会产生连锁反复购买；每个商品最多从 unbought 搬到 bought 一次，总复杂度可控。

---

具体实现

• 初始：找最大性价比 $w_{\max}$，把所有 $w_i = w_{\max}$ 的买下，其余放入未买集合。
• 事件：
  • 新增：插入 unbought
  • 修改：看该商品当前在 bought 还是 unbought，从对应集合删旧键、插入新键
• 计算 $L$，然后把 unbought 中所有 $w \ge L$ 的商品批量买下
• 输出当前总花费

---

// 已买/未买集合：按 (w, id) 排序
set<pair<int, int>> bought, unbought;
// 初始：买下性价比最大的所有商品
int wmax = w[1];
for (int i = 2; i <= n; i++)
    wmax = max(wmax, w[i]);
long long sum = 0;
for (int i = 1; i <= n; i++)
{
    if (w[i] == wmax)
    {
        bought.insert({w[i], i});
        vis[i] = 1; // 标记已买
        sum += v[i];
    }
    else
    {
        unbought.insert({w[i], i});
    }
}
for (int i = 1; i <= m; i++)
{
    int op;
    int x, y;
    cin >> op >> x >> y;
    if (op == 1)
    {
        // 新增商品，编号为 n + i
        v[n + i] = x;
        w[n + i] = y;
        vis[n + i] = 0; // 标记未买
        unbought.insert({w[n + i], n + i});
    }
    else
    {
        // 修改编号为 x 的商品性价比为 y
        if (vis[x])
        {
            bought.erase({w[x], x});
            w[x] = y;
            bought.insert({w[x], x});
        }
        else
        {
            unbought.erase({w[x], x});
            w[x] = y;
            unbought.insert({w[x], x});
        }
    }
    // 计算当前 L（已买商品最低性价比）
    int L = bought.begin()->first;
    // 买下所有未买且 w >= L 的商品
    auto it = unbought.lower_bound({L, 0});
    while (it != unbought.end())
    {
        int id = it->second;
        sum += v[id];
        vis[id] = 1;
        bought.insert({w[id], id});
        it = unbought.erase(it); // 获取删除以后的下一个迭代器
    }
    cout << sum << "\n";
}

---

T4

题意

把输入的字符矩阵解码成数值矩阵 $a$（大小 $h\times w$）。我们要在矩阵里选一个“潜在潜艇图像”，由三段组成：

• 艇身：在同一行 $y_1$ 上，从 $x_1$ 到 $x_2$ 的一段水平连续格子（$x_1<x_2$）。
• 指挥塔：在列 $x_3$ 上，从 $y_1$ 往上到 $y_2$ 的一段竖直连续格子（$x_1\le x_3 < x_2$）。
• 尾部：在列 $x_4$ 上，从 $y_3$ 到 $y_4$ 的一段竖直连续格子，且覆盖艇身所在行（$x_3<x_4\le x_2,\ y_3\le y_1\le y_4$）。

潜艇图像的价值是这些格子对应数值的总和，要求最大值。

---

思路

把潜艇“钉”在两处交点来想最方便：

• 指挥塔与艇身交点：$(i,j)$
• 尾部与艇身交点：$(i,k)$，且必须 $j<k$（保证艇身长度至少 $2$）

于是潜艇由 $5$ 块组成：

1. 行 $i$ 上的艇身中段：从 $j$ 到 $k$ 的区间和
2. 行 $i$ 上以 $j$ 结尾的向左最大子段和（艇身左延伸）
3. 行 $i$ 上以 $k$ 开始的向右最大子段和（艇身右延伸）
4. 列 $j$ 上以 $(i,j)$ 结尾的向上最大子段和（指挥塔向上延伸）
5. 列 $k$ 上包含 $(i,k)$ 的“上下都可延伸”的最大竖直和（尾部）

这四个方向的“包含当前格子”的最大子段和可以用 DP 一次扫出来：

• $u[i][j]$：以 $(i,j)$ 结尾向上的最大和

\[ u[i][j]=a[i][j]+\max(0,u[i-1][j]) \]

• $d[i][j]$：以 $(i,j)$ 开始向下的最大和

\[ d[i][j]=a[i][j]+\max(0,d[i+1][j]) \]

• $l[i][j]$：以 $(i,j)$ 结尾向左的最大和

\[ l[i][j]=a[i][j]+\max(0,l[i][j-1]) \]

• $r[i][j]$：以 $(i,j)$ 开始向右的最大和

\[ r[i][j]=a[i][j]+\max(0,r[i][j+1]) \]

并且行前缀和 $s[i][j]$ 用来算艇身中段：

\[ \text{mid}(i,j,k)=s[i][k]-s[i][j-1] \]

---

从 $O(hw^2)$ 降到 $O(hw)$

固定尾部交点 $(i,k)$，我们要在所有 $j<k$ 里取最大：

把总和（注意要减去重复计算的交点格子）整理后可写成：

\[ \text{Ans}(i,k)=\underbrace{s[i][k]+r[i][k]+u[i][k]+d[i][k]-3a[i][k]}*{\text{只与 }(i,k)\text{有关}} +\max*{j<k}\underbrace{\Big(u[i][j]+l[i][j]-2a[i][j]-s[i][j-1]\Big)}_{\text{只与 }(i,j)\text{有关}} \]

因此我们只要对每一行 $i$，从左到右扫 $k$，维护

\[ mx=\max_{j<k}\Big(u[i][j]+l[i][j]-2a[i][j]-s[i][j-1]\Big) \]

就能 $O(1)$ 更新答案，实现总复杂度 $O(hw)$。

---