Codeforces Round #667(Div.3) 解题报告

期末考试考完了,开始复健运动辣~

(不过退化到这个地步了也该好好练习了)

比赛链接(1409)

A – Yet Another Two Integers Problem

赤裸裸的签到题……

B – Minimum Product

好昨晚卡这个题卡了半天……(半天 $=$ 半小时)

这个题就是考虑各种情况,只考虑 $a\le b$ 的情况,那么第一种就是只减少 $a$,减少完了如果还有剩的操作次数再去减 $b$。这种情况很好考虑,而麻烦的就是下面这种:

首先减少 $b$ 这一堆,直到减少到 $max(a,y)$ 为止,这个时候 $b$ 这一堆要么和 $a$ 相同,这时就看 $a-x$ 和 $b-y$ 谁大,哪边大就优先减谁;而还有一种就是 $b$ 减完了只剩 $a$,那就只对这一堆操作就行。

(一定要想清楚,不然就想我昨晚搞了半个多小时……)

C – Yet Another Array Restoration

这就是一个很简单的构造,因为 $x$ 和 $y$ 之间一定满足 $y=x+k\times d$,并且 $k,d$ 都是整数,那么因为 $x$ 和 $y$ 都特别小,直接枚举 $k$ 或者 $d$,之后再模拟复原整个序列,更新最大值的同时更新答案就可以了。

D – Decrease the Sum of Digits

这题再次暴露我的代码能力多么拉跨(

从低位开始往高位考虑,设前缀和 $sum(n)$ 从最高位开始前 $n$ 位的数字之和,然后从低位开始枚举。因为要消掉一些数字,那就只能让某一位之后全部变成 $0$ 就行。

于是就可以枚举消除后 $m$ 位,并且要注意第 $m+1$ 位的数字会 $+1$,并且如果第 $m+1$ 位数字是 $9$ 的话这一位实际上也被消除了,所以考虑的时候注意遇到第 $m+1$ 位数字是 $9$ 的话就直接跳过就行。

细节有一点多,总之还是要想清楚再写(

E – Two Platforms

赛后过题我最拿手了

很明显,这 $n$ 个点的 $y$ 坐标没有任何作用,因为都要往下掉的,所以输入的时候直接全部去掉就行。

然后就是考虑怎么放着两块板。显然,这两块板没有重叠的时候是最优的,并且每一块板的某个端点一定是某个点的 $x$ 坐标,方便起见,我们就设左端点是这样的。

那么就可以考虑枚举其中一块板的位置,如何快速求出另一块板的位置使得其贡献最大。显然,我们可以把所有 $x$ 离散化之后做一个前缀和,然后做一个后缀最大值。这个最大值就是在第 $i$ 个坐标及之后一块板能产生的最大贡献(即能接收到的最多的点的数量),这一步可以采用二分的方法,找到这个端点往右延伸长度 $k$ 之后对应的位置之间的区间和。

然后就可以 $\mathcal{O}(n)$ 的时间扫一遍就行。

总的时间复杂度为 $\mathcal{O}(n\log^2n)$。当然写法很好的话可以优化到 $\mathcal{O}(n\log n)$.

F – Subsequences of Length Two

(要好好练习读题啊啊啊啊,完全没看到 $t$ 串只有俩字母的条件,吐了)

直接上 $dp$ 吧,这题一看就是个 $dp$~

设 $dp(i,j,y)$ 表示 $s$ 串前 $i$ 个字母,用了 $j$ 次操作,$t_0$ 这个字母在 $s$ 串前 $i$ 个字母中有 $y$ 个。

实际上,这个题可以把 $s$ 串分成三种字母组成的:$t_0,t_1$ 和其他字母。也就是说转移的时候我们只需要考虑这几种情况就行。

  1. 不改变第 $i$ 位的字母。这种情况下,考虑第 $i$ 位为其他字母,$t_0,t_1$ 就有好几种情况。整合一下其实方程很简单:$dp(i+1,j,y+(s_i==t_0)) = \max\{dp(i+1,j,y+(s_i==t_0)),dp(i,j,y)+((s_i==t_1)?y:0)\}$.
  2. 改变第 $i$ 位的字母为 $t_0$,那么只有在 $t_0==t_1$ 的时候才会产生贡献,于是方程可以写成 $dp(i+1,j+1,y+1) = \max\{dp(i+1,j+1,y+1),dp(i,j,y)+((t_0==t_1)?y:0)\}$.
  3. 改变第 $i$ 位的字母为 $t_1$,那么就看前面有几个 $t_0$ 就会产生多少贡献,并且如果 $t_0==t_1$,那么改变后 $t_0$ 的数量也会 $+1$,于是方程可以写成 $dp(i+1,j+1,y+(t_0==t_1))=\max\{dp(i+1,j+1,y+(t_0==t_1),dp(i,j,y)+y\}$.

最后答案就是 $\max\limits_{0\le j \le k,0\le y \le n}\{dp(n,j,y)\}$.

 

发表评论