AtCoder Beginner Contest 266 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abcd 都没什么可说的

[ABC266E] Throwing the Die

题面

你有一个普通均匀的正方体骰子,六个面写有 1,2,3,4,5,6。你在玩一个游戏,每次丢骰子之后,你可以:

给定 N,计算如果你希望最后一次投掷时朝上面的期望最大,那么这个期望是多少。

Solution

十分显然且简单的 期望DP。令 dp(i) 表示最多可以丢 i 次的答案,显然转移:

dp(i)=j=16dp(i1)6×[dp(i1)j]+j6×[dp(i1)<j]

答案即 dp(n)

Code

[ABC266F] Well-defined Path Queries on a Namori

题面

给定一张有 N 个点、N 条边的简单连通无向图和 Q 次询问,对于每次询问,给定 xi,yi,表示两点的编号,请你回答第 xi 个点和第 yi 个点之间是否有且仅有一条简单路径。

如果路径上的各顶点均不重复,则称这样的路径为简单路径。

Solution

思路比较容易想到。

根据定义显然为基环树,考虑发现若两点在树上路径经过环那么有多条,反之有且仅有一条。

最开始的思路是断环然后树剖加线段树查有没有环上的点,但是想了一下好像不用这么麻烦。

直接对环标记,对环上每个点进行染色并从非环边搜索下去继续染色,这样如果查询两个点颜色不同的需跨环,反之则不用,跑一下即可。

复杂度应该是 O(n+m+q) 的。

Code

[ABC266G] Yet Another RGB Sequence

题面

求符合要求的字符串个数,对 998244353 取余。

满足要求的字符串 s 具备以下特性:

  1. srgb 构成。
  2. s 中有 RrGgBbkrg

Solution

大概就是我们根据组合意义去考虑,一种思路是先从 RG 中各去掉 k 个,再考虑。

一种思路是考虑先插入 gb,然后找 k 个连接成 rg,再将剩余的 r 插入。两种思路的式子本质相同,最终得到的式子为:

(G+BG)×(Gk)×(Rk+B+kRk)

这东西复杂度显然是 O(n) 的。

然后还有二项式反演的思路,类似于前者去掉 k 的做法,然后做一遍多重集排列,再用二项式反演将 k 加上去掉 k+1 加上 k+1 然后 ,发现这玩意就是个二项式,用二项式反演做一下即可,复杂度差不多。

Code

[ABC266Ex] Snuke Panic (2D)

题面

二维平面直角坐标系中,你初始位于 (0,0),每个时刻可以任意向上,左,右走一步,即步进 1 的距离。存在 n 条收益,当你在 Ti 时刻走到坐标 (Xi,Yi) 的话就能够获得收益 Ai,你需要最大化收益,输出最大值。

Solution

类比 ABC266D 考虑朴素 DP,显然我们可以认为对于无收益的点是无意义的,所以我们可以采用离散化的思想,令 dp(i) 表示到 i 条收益的点时的最大收益,转移显然:

dp(i)=maxj{dp(j)}+Ai

这里的 j 需要满足:

tj<ti
yj<yi
|xixj|+yiyjtitj

显然 tj<ti 是无效的限制,对于最后一个因为绝对值的存在可以拆成两个限制,同时关键点在于,若用 CDQ 解决那么我们不能有或起来的条件,故不难发现可以拆成如下两个条件:

xixj+yiyjtitj
xjxi+yiyjtitj

移项一下:

tjxjyjtixiyi
tj+xjyjti+xiyi

于是就变成了经典的三位偏序问题,我们将 y 排序解决,然后将最后的对于 x,y 的限制用树套树解决即可,或用 CDQ 亦可。

这里我们考虑使用 BIT套BIT,即 二维BIT 解决。

注意虽然 BIT 是不支持区间 max 的,但支持前缀 max

同时注意需要对其全部离散化。

还有一个细节就是在 BIT 里维护的下标是离散化后的值,值则为对应的 dp

然后还有一个很重要的细节就是对于 ti<xi+yi 的我们应该直接将其丢弃,不能作为转移。

还没完,还有一个细节,就是排序的时候不能只排 y,对于 y 相同的还需要继续排 txyt+xy

Code

UPD

update-2023_01_12 初稿