跳转至

算法周赛round28

T1

题目要求

判断每一个队伍名称 $s_i$ 是否存在一个子串，与主办方字典中的某个字符串 $t_j$ 完全相同。

  • 若存在这样的子串 → 输出 Yes
  • 否则输出 No

解题思路

给定条件：

  • $1 \le n,m \le 100$
  • $|s_i| \le 100$
  • $|t_j| \le 100$

数据范围非常小，可以直接暴力判断。

我们只需要判断：

\[ t_j \text{ 是 } s_i \text{ 的子串吗？} \]

在 C++ 中使用：s[i].find(t[j]) != -1 即可判断是否为子串。

实现流程

对每一个队伍名 $s_i$：

  1. 遍历所有字典串 $t_j$
  2. 若发现任意一个满足

$$ t_j \subseteq s_i $$

则本队违规 → 输出 Yes 3. 若所有字典串均不匹配 → 输出 No

由于字符串长度最多为 $100$，总共有 $n \cdot m$ 对组合：

\[ O(n \cdot m \cdot |S|) \le 100 \times 100 \times 100 = 10^6 \]

T2

我们将每条提交记录存入结构体：

struct node 
{ 
    int t, p, s; 
} a[1005];

其中：

  • t：队伍编号
  • p：题目编号
  • s：提交结果（1 = AC，0 = 非 AC）

另外维护两个辅助数组：

  • cnt1[i]：记录队伍 $i$ 最终通过了多少道题
  • cnt2[i][j]：标记队伍 $i$ 是否通过了题目 $j$

问题一：最后一条 AC 记录对应的队伍

定义：

\[ \text{ans1} = -1 \]

从头到尾遍历所有提交记录：

  • 若 a[i].s == 1，则更新 ans1 = a[i].t

由于始终覆盖，因此最终的 ans1 即为 最后一条 AC 对应的队伍。

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

问题二：最后一条有效 AC 记录对应的队伍

“有效 AC” 指的是：同一队伍对同一题目，第一次 AC 才有效。

定义：

\[ \text{ans2} = -1 \]

遍历所有记录：

  1. 当 a[i].s == 1（AC）

  2. 若 cnt2[a[i].t][a[i].p] == 0（此前该题未被该队 AC）

  3. 则这是一次有效 AC

  4. 更新：

    $$ \begin{aligned} &\text{cnt2}[t][p] = 1 \ &\text{cnt1}[t] \gets \text{cnt1}[t]+1 \ &\text{ans2} = t \end{aligned} $$

最终的 ans2 即为最后一次有效 AC 对应的队伍。

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

问题三：未获奖队伍的最后一次有效 AC

已知奖牌数量为 $k$，只有最终 AC 数量 $\ge k$ 的队伍获得奖牌。

为了得到仅包含未获奖队伍的有效 AC：

  1. 遍历一遍记录，已在前面求出了 cnt1[i]（各队最终 AC 数量）

  2. 重置：

memset(cnt2, 0, sizeof(cnt2));
ans3 = -1;

  1. 再次遍历所有记录：

  2. 当 a[i].s == 1

  3. 并且队伍在最终统计中满足：cnt1[a[i].t] < k（未获奖）
  4. 并且该题之前未被此队 AC：cnt2[a[i].t][a[i].p] == 0

则记录一次有效 AC：

$$ \text{cnt2}[t][p] = 1,\quad \text{ans3} = t $$

最终 ans3 即为未获奖队伍的最后一条有效 AC 所对应的队伍。

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

问题四：最后一次让某队通过题数从 $0$ 变为 $1$ 的提交

要求找出最后一次满足：

\[ \text{某队 cnt1 从 } 0 \text{ 变为 } 1 \]

定义：

ans4 = -1
memset(cnt1, 0, sizeof(cnt1));
memset(cnt2, 0, sizeof(cnt2));

遍历所有记录：

  1. 当 a[i].s == 1

  2. 并且该题此前未被 AC：cnt2[t][p] == 0

  3. 则：

$$ \text{cnt2}[t][p] = 1,\quad \text{cnt1}[t]++ $$

  1. 如果更新后满足：

$$ cnt1[t] == 1, $$

说明该队通过题数从 $0$ 变成 $1$，于是记录：$ans4 = t$

最终的 ans4 即为答案。

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

T3

知识点：结构体排序，map。

核心思路

将所有记录按以下规则排序：

  1. 先按照评分（或排名）r 升序排序
  2. 若 r 相同，则按 id 升序排序

排序后依次处理记录，选择晋级队伍。

使用：

map<string, bool> mp;

用于标记已经晋级过的选手名字。

定义变量：

  • cnt = 0：当前累计晋级队伍数量。

每条记录含 3 个名字：s1, s2, s3（例如队员名字）。

排序完成后，依次遍历每条记录：

  1. 若该队伍的任意成员已经晋级过，跳过该记录

也就是当：

  • mp.count(a[i].s1) == true，或者
  • mp.count(a[i].s2) == true，或者
  • mp.count(a[i].s3) == true

满足任意一个，则说明这支队伍中有人已经晋级，不能重复晋级，直接 continue。

  1. 否则选中该队伍

晋级队伍数量加 $1$：

\[ cnt \leftarrow cnt + 1 \]

若 cnt > k，则达到晋级名额上限，立即结束遍历。

若尚未超过：

  • 将 s1, s2, s3 三个名字全部加入 map 标记为晋级
  • 将这支队伍的信息存入结果数组中，留待最后统一输出

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

T4

问题分析

我们有 $N$ 件商品，第 $i$ 件商品有：

  • 定价：$P_i$
  • 种类：$A_i$

促销规则：

  • 第 $j$ 天（$1 \le j \le M$）所有 种类为 $j$ 的商品半价。

每位顾客 $k$：

  • 来访日：$T_k$
  • 购买区间：$[L_k, R_k]$

我们需要计算顾客购买商品的实际花费。

观察与转化

如果没有促销，顾客 $k$ 的花费就是：

\[ \sum_{i=L_k}^{R_k} P_i \]

促销日 $T_k$ 会让 种类为 $T_k$ 的商品半价。

因此总价变为：

\[ \text{Total} = \left( \sum_{i=L_k}^{R_k} P_i \right) - \frac12 \left( \sum_{\substack{i=L_k \le i \le R_k \ A_i = T_k}} P_i \right) \]

于是我们只需要支持两种查询：

  1. 区间 $[l,r]$ 上所有价格之和
  2. 区间 $[l,r]$ 上某种类 $t$ 的所有价格之和

所有商品的前缀和

\[ s[i] = \sum_{j=1}^{i} P_j \]

这样可以 $O(1)$ 求任意区间总价：

\[ \text{sum}(l,r) = s[r] - s[l-1] \]

按商品种类分桶

设：$ve[c] =$ 该种类 $c$ 的所有商品 (按下标升序排列)

每个元素为 (位置, 到此位置价格的前缀和)。

例如 ve[5] 存：

(pos1, price1)
(pos2, price1 + price2)
...

这样就能快速二分查找种类为 c 且下标位于 [l, r] 的商品们的价格之和。

对于顾客 $k$：

  • 基本区间和：
\[ S = s[r] - s[l-1] \]
  • 在 ve[Tk] 中二分找到下标落在 $[l,r]$ 的商品范围：

使用：

  • lower_bound((l, 0)) 找到第一个位置 $\geq l$ 且价格大于等于 $0$。

  • upper_bound((r + 1, 0)) 找到第一个位置 $>r + 1$ 且价格大于 $0$，再减 $1$ 得到 $\leq r$ 的最后一个。

  • 若存在有效区间，则得到该种类在区间内的价格和：

\[ \text{half_sum} = \text{prefix}[R] - \text{prefix}[L-1] \]
  • 最终答案：
\[ \text{ans} = S - \frac{\text{half_sum}}{2} \]

总体复杂度：$O((n + q)\log n)$