http://codeforces.com/gym/103202

H. The Boomsday Project

 

题意：共享单车，每次骑要花费 rr 元。另外还有 nn 种租赁方式，每种方式在购买后 did_i 天内有效，在有效期内能免费骑 kik_i 次，购买需要花费 cic_i 元。给出 mm 条骑车记录，在第 pip_i 天骑了 qiq_i 次，问最少花费。1≤n≤500,1≤m≤105,1≤r≤109,1≤di,ki,ci≤109,0≤pi≤109,0≤qi≤3×105,∑i=1mqi≤3×1051\leq n \leq 500, 1 \leq m \leq 10^5, 1 \leq r \leq 10^9,1 \leq d_i, k_i, c_i \leq 10^9,0 \leq p_i \leq 10^9, 0 \leq q_i \leq 3 \times 10^5, \sum_{i=1}^m q_i \leq 3 \times 10^5

dp

构造一个新的数列，连续 qiq_i 个 pip_i 代表在第 pip_i 天骑了 qiq_i 次。

每种租赁方式就相当于一种块。对于一种租赁方式，有效期一定随着当前日期单调，所以只需要维护右端点位置即可。

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
42
43
44
45
46
47
48
#include <bits/stdc++.h>

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int n, m;
ll r;
int d[1010], b[1010];
ll c[1010];
pii t[N];
int a[N], pt[1010];
ll dp[N];

int main() {
    scanf("%d%d%lld", &m, &n, &r);
    for (int i = 1; i <= m; i++)scanf("%d%d%lld", &d[i], &b[i], &c[i]);
    for (int i = 1; i <= n; i++)scanf("%d%d", &t[i].first, &t[i].second);
    sort(t + 1, t + n + 1);
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= t[i].second; j++)a[++tot] = t[i].first;
    }
    n = tot;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = min(dp[i], dp[i - 1] + r);
        for (int j = 1; j <= m; j++) {
            while (pt[j] - i + 1 <= b[j] && a[pt[j]] - a[i] + 1 <= d[j]) {
                pt[j]++;
                dp[pt[j] - 1] = min(dp[pt[j] - 1], dp[i - 1] + c[j]);
            }
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

 

D. Journey to Un’Goro

 

题意：定义一个字符串的值等于包含奇数个 ‘r’ 的连续子串的个数，问所有只由 ‘r’，‘b’ 构成的字符串中最大的值。并输出值等于最大值的字典序最小的前100个字符串。

dfs剪枝

区间 [i,j][i,j] 中包含奇数个 ‘r’，说明 pre[i−1]pre[i-1] 与 pre[j]pre[j] 异号，pre[i]pre[i] 表示前 ii 个字符中的 ‘r’ 的个数。

显然当 prepre 数组中奇数值与偶数值相差不超过 1 个时最优。由于 prepre 数组长度为 n+1n+1，所以此时分别取 ⌊n+12⌋\lfloor \frac{n+1}{2}\rfloor 与 ⌈n+12⌉\lceil \frac{n+1}{2}\rceil 。

dfs时记录 prepre 中奇数与偶数个数，当超过 ⌈n+12⌉\lceil \frac{n+1}{2}\rceil 时剪枝。

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>

bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

int n;
int ans;
char s[N];

void dfs(int dep, int c0, int c1, int st) {
    if (c0 > (n + 2) / 2 || c1 > (n + 2) / 2)return;
    if (dep > n) {
        printf("%s\n", s + 1);
        ans++;
        if (ans >= 100)exit(0);
        return;
    }
    s[dep] = 'b';
    dfs(dep + 1, c0 + (st ^ 1), c1 + st, st);
    s[dep] = 'r';
    st ^= 1;
    dfs(dep + 1, c0 + (st ^ 1), c1 + st, st);
}

int main() {
    scanf("%d", &n);
    printf("%lld\n", 1ll * (n + 1) / 2 * ((n + 2) / 2));
    dfs(1, 1, 0, 0);
    return 0;
}