Bananas in a Microwave | Codeforces 1498D

发表于 分类于 本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目链接

有一个变量 \(k\) 初始为 \(0\)。

对于时刻 \(i=1,2,3,\cdots,n\)，给定 \(t_i,x_i,y_i\)，且执行以下操作：

  • 若 \(t_i=1\)，选择 \(a \in [0,y_i]\)，执行 \(a\) 次 \(k=\lceil k + x_i \rceil\)。
  • 若 \(t_i=2\)，选择 \(a \in [0,y_i]\)，执行 \(a\) 次 \(k=\lceil k \cdot x_i \rceil\)。

其中 \(x_i\) 是实数。

对于每个 \(j \in [1,m]\)，求可能的最小时刻使得 \(k=j\)。

\(n \le 200,y_i \le m \le 10^5\)

对于 \(t_i=1\)，有 \(0 < x_i \le m\)，对于 \(t_i=2\)，有 \(1 < x_i \le m\)。

对于每个时刻 \(i\)，维护数组 \(ok_j\) 表示经过前 \(i\) 个时刻能否使 \(k=j\)。

设 \(next_j=\begin{cases}\lceil j + x_i \rceil&(t_i=1)\\\\\lceil j \cdot x_i \rceil&(t_i=2)\end{cases}\)。

因为 \(\forall j \ne k,next_j \ne next_k\)，所以 \(j \rightarrow next_j\) 连边后形成若干条链。

假设一条链上的结点分别为 \(v_1,v_2,v_3,\cdots,v_s\)

对于 \(v_j\)，如果 \(\exist k \in [j-y_i,j)\)，满足 \(ok_k=1\)，那么在第 \(i\) 时刻 \(k\) 可以等于 \(v_j\)。

对每条链扫描一遍即可求出在第 \(i\) 时刻 \(k\) 可以等于哪些值。

复杂度 \(O(nm)\)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define upd(a, b) (a = min(a, b))

using namespace std;
typedef long long ll;
const int N = 1e5, M = N + 5;
int n, m, f[M], nxt[M], vis[M], ok[M];
int main() {
    mem(f, -1);
    int t, y; ll x;
    cin >> n >> m;
    f[0] = 0;
    rep(k, 1, n) {
        scanf("%d%lld%d", &t, &x, &y);
        if(t == 1) {
            x = (x + N - 1) / N;
            rep(i, 0, m) nxt[i] = min(i + x, m + 1ll);
        } else {
            nxt[0] = m + 1;
            rep(i, 1, m) nxt[i] = min((i * x + N - 1) / N, m + 1ll);
        }
        mem(vis, 0);
        rep(i, 0, m) if(!vis[i]) {
            vector <int> v;
            for(int j = i; j <= m; j = nxt[j]) vis[j] = 1, v.push_back(j);
            int cnt = 0;
            For(j, 0, v.size()) {
                if(cnt) ok[v[j]] = 1;
                cnt += f[v[j]] != -1;
                if(j >= y) cnt -= f[v[j - y]] != -1;
            }
        }
        rep(i, 0, m) if(!~f[i] && ok[i]) f[i] = k;
    }
    rep(i, 1, m) printf("%d ", f[i]);
    return 0;
}