Bananas in a Microwave | Codeforces 1498D

题目链接

有一个变量 \(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;
}