Codeforces Round #711 Bananas in a Microwave 阅读理解题

题意

此题的难点主要在于题意……以下内容全为意译。

你有$m$根香蕉,你的目的是在n次操作后,问每根香蕉最早可能被操作的时间。(其中假设有一根0号香蕉,已经被处理过了,之后不用输出这个香蕉。也就是$k=0$。)

每次操作,给你一个$t$表示步骤的类型,给你一个$x$后面步骤里有用。给你一个$y$,表示当前操作内可以执行最多$y$次下述步骤。

步骤有两类:

  1. 第一类,选择一个已经操作过的香蕉$k$,可以操作第$\lceil{k+x}\rceil$号香蕉。
  2. 第二类,选择一个已经操作过的香蕉$k$,可以操作第$\lceil{k\cdot{x}}\rceil$号香蕉。

题解

就一个很水的DP。

定义$next$是根据$t$计算得到相应的下标。如$\lceil{i+x}\rceil$和$\lceil{i\cdot{x}}\rceil$。

对于第$cas$次操作,如果$ans[i]\neq{-1}$且$used[i]<y$,我们有$ans[next]=cas$且$used[next]=used[i]+1$。(注意每次操作$used$都会被重置)

扫描和更新$ans$与$used$。扫描的顺序是从左往右还是从右往左取决于$next$和$i$的大小关系。

没了。难点全在题意理解上。

代码

Submission #113021399 - Codeforces
Codeforces. Programming competitions and contests, programming community