DDOSvoid's Blog

CF 1498D Bananas in a Microwave

发表于 分类于
本文字数： 906 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1498/problem/D

Solution

首先我们有一个 $O(nm^2)$ 的类似背包的做法

注意到每次转移可以看做是从所有点 $s$ 以相同的方法跳 $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
#include <iostream>
#include <algorithm>
#define maxn 210
#define maxm 100010
#define ll long long
using namespace std;

int n, m, t[maxn], y[maxn];

ll x[maxn];

bool f[maxm]; int ans[maxm];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> t[i] >> x[i] >> y[i];
    f[0] = 1; for (int i = 1; i <= m; ++i) ans[i] = -1;
    for (int i = 1; i <= n; ++i)
        for (int j = m; ~j; --j) {
            if (!f[j]) continue;
            ll s = j;
            for (int k = 1; k <= y[i]; ++k) {  
                if (t[i] == 1) s = s + (x[i] + 99999) / 100000;
                else s = (s * x[i] + 99999) / 100000;
                if (s > m || f[s]) break;
                f[s] = 1; ans[s] = i;
            }
        }
    for (int i = 1; i <= m; ++i) cout << ans[i] << " \n"[i == m];
    return 0; 
}