跳转至

算法周赛round25

T1

本题考察计数数组。

注意到数据范围，$1\leq t\leq 4$。因此，$10^t$ 在 $10\sim 10000$ 的范围内，特征值的后 $t$ 位范围为 $[0,9999]$。

可以使用计数数组 int cnt[10000] 来统计 $0～9999$ 范围内出现的次数。

  • 对于输入的每个数字 $x$，定义 $P=10^t$。则令 $x\gets x\bmod P$ 则可以直接获取后 $t$ 位数字。

最后遍历计数数组，统计其中不为 $0$ 的个数，即为答案。（cnt[i] != 0 说明 $i$ 出现了，因此答案加 $1$）

时间复杂度：$O(n+v)$，其中 $v=10^t$。

T2

本题考查贪心思维。

$b=0$ 时

  • 此时答案为 $n$。

$b=1$ 时

  • 此时显然每赢 $a$ 次就要输 $1$ 次。因此每 $a+1$ 局游戏就要获胜 $a$ 次。

  • 因此答案为

    \[ \lfloor \dfrac{n}{a+1}\rfloor\times a+n\bmod (a+1) \]

一般情况

由于最长连胜不超过 $a$、最长连败不超过 $b$，因此最佳的游戏过程可以构造为：

\[ \underbrace{1\ldots1 }_{a 个}\ \underbrace{0\ldots0 }_{b 个}\ \underbrace{1\ldots10 }_{a+1 个}\ \ldots \underbrace{1\ldots10 }_{a+1 个}\ \underbrace{1\ldots }_{余下的} \]

因此答案为：

\[ a+\lfloor \dfrac{n-a-b}{a+1}\rfloor\times a+(n-a-b)\bmod (a+1) \]

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

T3

本题考查思维和结论。

显然，我们不可能得到任何比 $\min_{i=1}^n a_i$ 更小的数，也不可能得到比 $\max_{i=1}^n a_i$ 更大的数。

实际上，其余所有的 $x$ 都可以得到。一个可行的构造方法是：我们可以选择两个不同的下标 $i$ 和 $j$，使得 $a_i \le x$ 且 $a_j \ge x$。然后在每一步操作中，要么选择一个值较小的数，使结果更接近 $a_i$，并把这两个数替换成 $a_i$；要么选择一个值较大的数，使结果更接近 $a_j$，并把这两个数替换成 $a_j$。最终只会剩下 $a_i$ 和 $a_j$，此时我们就可以把它们替换成 $x$ 来得到 $x$。

因此分别求出最小值和最大值，然后判断即可。

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

T4

子任务 $2$

定义三个前缀和 $s1[i],s2[i],s3[i]$，分别表示 $1$ 到 $i$ 中 $\texttt{J,O,I}$ 三个字母的个数。

枚举所有子串 $[i,j]$。使用前缀和 $O(1)$ 查询子串 $[i,j]$ 中 $\texttt{J,O,I}$ 的个数，并判断是否三个字母的个数都相等。

即判断：

\[ s1[j]-s1[i-1]=s2[j]-s2[i-1]=s3[j]-s3[i-1] \]

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

子任务 $3$

对于一个子串 $[i,j]$ 如果其满足三个字母的次数相同。整理条件可以得到：

\[\begin{cases} s1[j]-s1[i-1]=s2[j]-s2[i-1]\\ s2[j]-s2[i-1]=s3[j]-s3[i-1] \end{cases}\]

进一步可以化简为：

\[\begin{cases} s1[j]-s2[j]=s1[i-1]-s2[i-1]\\ s2[j]-s3[j]=s2[i-1]-s3[i-1] \end{cases}\]

定义 $a[i]=s1[i]-s2[i]$ $b[i]=s2[i]-s3[i]$，则进一步表示为：

\[\begin{cases} a[j]=a[i-1]\\ b[j]=b[i-1] \end{cases}\]

定义 pair<int, int> A[N] 其中 A[i].first 表示 $a[i]$，A[i].second 表示 $b[i]$。

则问题等价于找到一个最长的区间 $[i,j]$ 满足 $A[i - 1] = A[j]$。

考虑枚举 $j$，使用 map<pair<int, int>, int> last 记录 $A[i]$ 第一次 出现的位置。

枚举 $j$ 时，若满足 last.count(A[j]) 说明 $A[j]$ 第一次 出现的位置是 last[A[j]]。

否则，则 $A[j]$ 第一次 出现的位置是 $j$。更新 last[A[j]] 为 $j$。

则 $j-last[A[j]]$ 即为 $[i,j]$ 的长度。

特别地：初始化 last[{0, 0}] = 0。

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

T5

知识点：动态规划。

子任务 $1$

考虑二进制枚举。每个糖果选或不选，最后检查一下当前状态是否满足：任意的连续 $k$ 个糖果最多只能选择 $2$ 个即可。

时间复杂度：$O(2^n\cdot n)$。

子任务 $2$

需要状压 DP 略。

子任务 $3$

考虑 DP。

定义 $dp_i$ 表示前 $i$ 个糖果的最大价值。如果不选择第 $i$ 个糖果，则 $dp_i = dp_{i-1}$。如果选择第 $i$ 个糖果，发现无法有效转移，主要是不确定上一个糖果的位置。

即使定义 $dp_i$ 表示以 $i$ 结尾的糖果的最大价值，也无法转移。因为无法判断是否存在某个长度为 $k$ 的区间选择了超过 $2$ 个糖果。

可以发现核心就是要知道上一个糖果的位置，而 $n\leq 3000$，因此重新设计状态如下：

\[ dp_{i,j} = \texttt{以 $i$ 结尾且上一个选择的糖果位置是 $j$ 的最大价值} \]

初始化：$dp_{i,j}=a_i+a_j$ 其中 $j\in [0,i-1]$。

则答案就是 $\max_{1\leq j<i\leq n} dp_{i,j}$。

转移自然是枚举上上一个糖果的位置 $p$，需要满足：

  • $0\leq p<j$
  • $i-p+1>k\rightarrow p\leq i-k$。该条件保证了 $i,j,p$ 三个糖果之间的距离大于 $k$。

即

\[ dp_{i,j}=\max(dp_{i,j},dp_{j,p}+a_i)\quad, 0\leq p\leq min(j-1,i-k) \]

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

子任务 $4$

尝试优化转移，可以发现转移其实就是获取了 $dp_{j,0\sim up}$ 其中 $up=\min(j-1,i-k)$ 的最大值。

也就是前缀最大值。因此维护

\[ \texttt{mx}[i][j] = \max(dp[i][0], dp[i][1], \ldots, dp[i][j]) \]

即可实现 $O(1)$ 转移。也就是

\[ dp[i][j]=\texttt{mx}[j][up]+a[i] \]

具体实现

  • 初始化：$dp[i][j]=a[i]+a[j]$。其中 $i\in [1,n]$，$j\in [0,i-1]$。
  • 枚举所有状态：$i,j$。其中 $i\in [1,n]$，$j\in [1,i-1]$。
    • 令 $up=\min(j-1,i-k)$。
    • 当 $up\geq 0$ 时，则 $dp[i][j]=\max(dp[i][j],\texttt{mx}[j][up]+a[i])$。
    • 更新 $\texttt{mx}[i][j]=max(\texttt{mx}[i][j-1],dp[i][j])$。
  • 遍历所有状态找到最优解 $ans$。

时间和空间复杂度均为：$O(n^2)$。