C20250021's blog
Day 2
C20250021 LV 10 @ 2024-1-30 14:32:17

早上照样7:30出门，8:10分到机房。

dp专题，最喜欢的一集。

昨天的位置被一个 xxs 占了，只好换去其他位置。

思路好想代码恶心，E题写了一个伪代码对着调了 30min，发现是我输出不是输出最大值，直接开爬。

F题写完了但已知调不出来，交了16次（），赛后xkm给了我一组 hack才调出来。

J题有点恶心，最后发现竟然不用建树，而且线段树还写错了，调了30min（）

简要题解：

A

原题

没啥好讲的。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10 + 5;
int n, a[MAXN][MAXN];
int x, y, z;
int dp[MAXN][MAXN][MAXN][MAXN];
signed main() {
    cin >> n;
    while (cin >> x >> y >> z && x != 0) a[x][y] = z;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                for (int l = 1; l <= n; l++) {
                    dp[i][j][k][l] = max({ dp[i - 1][j][k - 1][l], dp[i][j - 1][k][l - 1],
                                           dp[i][j - 1][k - 1][l], dp[i - 1][j][k][l - 1] }) +
                                     a[i][j];
                    if (i != 1 && j != l)
                        dp[i][j][k][l] += a[k][l];
                }
            }
        }
    }
    cout << dp[n][n][n][n];
}

B

有N个相同的球，M个不同的盒子，每个盒子最多放K个球


请计算将这N个球全部放入盒子中的方案数模1000007后的结果

注:一个盒子可以不放球

$dp[i][j]$ 表示将 $j$ 个球放入 $m$ 个盒子里不同的方案，转移很简单。

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 5e3 + 5;
const int MOD = 1000007;
int n, m, k;
int dp[MAXN][MAXN];
signed main() {
    cin >> n >> m >> k;
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        dp[i][0] = 1;
        dp[0][i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        int res = i;
        for (int j = 1; j <= n; j++) {
            dp[i][j] = res;
            res = (res + dp[i - 1][j + 1]) % MOD;
            if (j >= k)
                res = (res - dp[i - 1][j - k] + MOD) % MOD;
        }
    }
    cout << dp[m][n] % MOD;
}

C

原题烽火传递。

可以用线段树，树状数组，单调队列，堆优化。

#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 1e6;
int n, m, r, value[SIZE], heap[SIZE], pos[SIZE], home[SIZE], opt[SIZE];
void swap(int i, int j) {
    int tmp;
    pos[home[i]] = j;
    pos[home[j]] = i;
    tmp = heap[i];
    heap[i] = heap[j];
    heap[j] = tmp;
    tmp = home[i];
    home[i] = home[j];
    home[j] = tmp;
}
void add(int k) {
    int i;
    r++;
    heap[r] = opt[k];
    pos[k] = r;
    home[r] = k;
    i = r;

    while ((i > 1) && (heap[i] < heap[i / 2])) {
        swap(i, i / 2);
        i /= 2;
    }
}
void remove(int k) {
    int i, j;
    i = pos[k];
    swap(i, r);
    ;
    r--;

    if (i == r + 1)
        return;

    while ((i > 1) && (heap[i] < heap[i / 2])) {
        swap(i, i / 2);
        i /= 2;
    }

    while (i + i <= r) {
        if ((i + i + 1 <= r) && (heap[i + i + 1] < heap[i + i]))
            j = i + i + 1;
        else
            j = i * 2;

        if (heap[i] > heap[j]) {
            swap(i, j);
            i = j;
        } else
            break;
    }
}

int main() {
    int i;
    cin >> n >> m;

    for (i = 1; i <= n; i++) cin >> value[i];

    r = 0;

    for (i = 1; i <= m; i++) {
        opt[i] = value[i];
        add(i);
    }

    for (i = m + 1; i <= n; i++) {
        opt[i] = value[i] + heap[1];
        remove(i - m);
        add(i);
    }

    cout << heap[1] << endl;
    return 0;
}

D

多重背包。

两种做法。

第一种二进制拆分，没什么好说的。

第二种单调队列，注意还要塞个0进队列。

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 2e4 + 5;
const int MOD = 1000007;
int n, V;
int v[MAXN], w[MAXN];
int dp[MAXN];
signed main() {
    cin >> V >> n;
    int cnt = 0;
    //	for(int i = 1; i <= n; i++)cin >> s[i] >> v[i] >> w[i];
    for (int i = 1, a, b, s; i <= n; i++) {
        cin >> s >> a >> b;
        int k = 1;
        while (k <= s) {
            v[++cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k *= 2;
        }
        if (s) {
            v[++cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    for (int i = 1; i <= cnt; i++) {
        for (int j = V; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V];
}

E

容易得到每一次答案是 $[a_i-k, a_i+k]$ 这一段区间的 dp 最大值，使用线段树维护即可。

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 1e6 + 5;
const int MOD = 1000007;

int n, k;
int tmp[MAXN], lazy[MAXN], a[MAXN], dp[MAXN];

#define ls (id << 1)
#define rs (id << 1 | 1)
int tr[MAXN];
void push_up(int id) { tr[id] = max(tr[ls], tr[rs]); }
void build(int id, int l, int r) {
    //	lazy[id] = 0;
    if (l == r) {
        tr[id] = dp[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(id);
}
int query(int id, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr)
        return tr[id];
    //	push_down(id, l, r);
    int ans = 0, mid = (l + r) >> 1;
    if (ll <= mid)
        ans = max(ans, query(ls, l, mid, ll, rr));
    if (rr > mid)
        ans = max(ans, query(rs, mid + 1, r, ll, rr));
    return ans;
}
void update(int id, int l, int r, int pos, int val) {
    if (l == r) {
        tr[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        update(ls, l, mid, pos, val);
    else
        update(rs, mid + 1, r, pos, val);
    push_up(id);
}
signed main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        tmp[i] = a[i];
        dp[i] = 1;
    }
    sort(tmp + 1, tmp + 1 + n);
    int m = unique(tmp + 1, tmp + 1 + n) - tmp - 1;
    build(1, 1, m);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = lower_bound(tmp + 1, tmp + 1 + m, a[i] - k) - tmp;
        int r = upper_bound(tmp + 1, tmp + 1 + m, a[i] + k) - tmp - 1;
        int x = lower_bound(tmp + 1, tmp + 1 + m, a[i]) - tmp;
        dp[i] = query(1, 1, m, l, r) + 1;
        update(1, 1, m, x, dp[i]);
    }
    cout << query(1, 1, m, 1, m) - 1;
}

F

给定三元组 $(a_i, b_i, c_i)$ ，求 $p_i$ 使得 $a_{p_i}\ge a_{p_{i - 1}}, b_{p_i}\ge b_{p_{i - 1}}$ ，且 $\sum c_{p_i}$ 最大。

二位偏序求三维题。

考虑维护第一维 $a$ ，用线段树维护当前 dp 最大值，使用线段树维护即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 5;
const int MOD = 1000007;
const int INF = 0x3f3f3f3f;

struct node {
    int v, l, r, num;
} a[MAXN], b[MAXN];
int n, c[MAXN], now;
int tr[MAXN];
int lowbit(int x) { return x & (-x); }
void update(int now, int val) {
    int id = now;
    while (id <= c[0]) {
        tr[id] = max(tr[id], val);
        id += lowbit(id);
    }
}
int query(int now) {
    int res = 0;
    int id = now;
    while (id) {
        res = max(res, tr[id]);
        id -= lowbit(id);
    }
    return res;
}

bool cmp1(node x, node y) { return (x.l == y.l ? x.r < y.r : x.l < y.l); }
bool cmp2(node x, node y) { return x.r < y.r; }
signed main() {
    cin >> n;
    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y >> a[i].v;
        a[i].l = x;
        a[i].r = y;
        a[i].num = i;
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1, cmp2);
    c[1] = ++c[0];
    a[b[1].num].r = c[1];
    for (int i = 2; i <= n; i++) {
        if (b[i].r != b[i - 1].r)
            ++c[0];
        c[i] = c[0];
        a[b[i].num].r = c[i];
    }
    sort(a + 1, a + n + 1, cmp1);
    for (int i = 1; i <= n; i++) {
        now = query(a[i].r);
        update(a[i].r, now + a[i].v);
    }
    cout << query(c[0]);
    return 0;
}

G

原题

考虑能拿到馅饼的条件：

|p_i-p_j| \le 2 \times (t_j - t_i)

将绝对值化简移项，得到：

$\begin{cases}p_i-2t_i\le p_j-2t_j(p_i\le p_j)\\p_i+2t_i\ge p_j+2t_j(p_i\ge p_j)\end{cases}$

发现和上面的条件很像，把上面的代码修改一下就过了。

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 2e5 + 5;
const int MOD = 1000007;
struct node {
    int t, p, v;
    int x;
} a[MAXN];
bool cmp(node x, node y) { return x.p - 2 * x.t >= y.p - 2 * y.t; }
int n, w;
int tmp[MAXN], dp[MAXN];
int tr[MAXN];
int lowbit(int x) { return (x & (-x)); }
void update(int x, int val) {
    int now = x;
    while (now <= n) {
        tr[now] = max(tr[now], val);
        now += lowbit(now);
    }
}
int query(int x) {
    int ans = 0;
    int now = x;
    while (now) {
        ans = max(ans, tr[now]);
        now -= lowbit(now);
    }
    return ans;
}
int ans = 0;
signed main() {
    cin >> w >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].t >> a[i].p >> a[i].v;
        tmp[i] = a[i].p + a[i].t * 2;
    }
    sort(tmp + 1, tmp + 1 + n);
    for (int i = 1; i <= n; i++) {
        a[i].x = lower_bound(tmp + 1, tmp + 1 + n, a[i].p + 2 * a[i].t) - tmp;
    }
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        dp[i] = query(a[i].x) + a[i].v;
        update(a[i].x, dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}

H

原题

考虑 $dp[i][j]$ 前 $i$ 条蛇改变 $j$ 次大小后剩下的最小空间。

转移方程：

$$dp[i][j] = min\{dp[i][j], dp[k][j - 1] + max\{a_{k\sim i}\}\ \times (i - k) - \sum\limits_{j=k + 1}^i{a_j} $$

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAXN = 1e3 + 5;
const int MOD = 1000007;
const int INF = 0x3f3f3f3f;

int n, m;
int a[MAXN], pre[MAXN];
int dp[MAXN][MAXN];
signed main() {
    memset(dp, INF, sizeof dp);
    dp[0][0] = 0;
    cin >> n >> m;
    m++;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, m); j++) {
            int maxx = a[i];
            for (int k = i - 1; k >= 0; k--) {
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + maxx * (i - k) - (pre[i] - pre[k]));
                maxx = max(maxx, a[k]);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i <= m; i++) ans = min(ans, dp[n][i]);
    cout << ans;
}

I

单调队列模板题。

不多阐述。

#include <bits/stdc++.h>
using namespace std;
deque<pair<long long, int>> q;
int inm[2005], outm[2005], ing[2005], outg[2005];
long long f[2005][2005];
void updateOut(long long x, int k, int i) {
    while (!q.empty() && q.front().second > k + outg[i]) q.pop_front();

    while (!q.empty() && q.back().first <= x) q.pop_back();

    q.push_back(make_pair(x, k));
}
void updateIn(long long x, int k, int i) {
    while (!q.empty() && q.front().second < k - ing[i]) q.pop_front();

    while (!q.empty() && q.back().first <= x) q.pop_back();

    q.push_back(make_pair(x, k));
}
int main() {
    int n, m, w;
    scanf("%d%d%d", &n, &m, &w);

    for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &inm[i], &outm[i], &ing[i], &outg[i]);

    for (int i = 0; i < 2005; i++)
        for (int j = 0; j < 2005; j++) f[i][j] = -2e16;

    for (int i = 1; i <= w + 1; i++)
        for (int k = 1; k <= i; k++)
            for (int j = 0; j <= ing[k]; j++) f[i][j] = max(f[i][j], (long long)j * inm[k] * -1);

    long long res = 0;

    for (int i = w + 2; i <= n; i++) {
        q.clear();

        for (int k = m; k >= 0; k--) {
            updateOut(f[i - w - 1][k] + k * outm[i], k, i);
            f[i][k] = max(f[i - 1][k], q.front().first - k * outm[i]);
        }

        q.clear();

        for (int k = 0; k <= m; k++) {
            updateIn(f[i - w - 1][k] + k * inm[i], k, i);
            f[i][k] = max(f[i][k], q.front().first - k * inm[i]);
            res = max(res, f[i][k]);
        }
    }

    cout << res << endl;
}

J

恶心至极。

线段树维护当前 dp 最大值， dp 表示在哪里开始喝饮料，使得总和最大。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 5e5;
int seg_tree[(MAXN << 2) + 5];
int Lazy[(MAXN << 2) + 5];
int ans = 0;
int n, w[MAXN + 5], dp[MAXN + 5], lst[MAXN + 5];
vector<int> vec[MAXN + 5];
void push_up(int root) { seg_tree[root] = max(seg_tree[root << 1], seg_tree[root << 1 | 1]); }
#define ls (root << 1)
#define rs (root << 1 | 1)
void push_down(int root) {
    seg_tree[ls] += Lazy[root];
    Lazy[ls] += Lazy[root];
    seg_tree[rs] += Lazy[root];
    Lazy[rs] += Lazy[root];
    Lazy[root] = 0;
}
int query(int root, int L, int R, int LL, int RR) {
    if (L > RR || R < LL)
        return -1e18;
    if (LL <= L && R <= RR)
        return seg_tree[root];
    int mid = (L + R) >> 1;
    return max(query(ls, L, mid, LL, RR), query(rs, mid + 1, R, LL, RR));
}
void update(int root, int L, int R, int LL, int RR, int val) {
    if (L > RR || R < L
        return;
    if (LL <= L && R <= RR) {
        seg_tree[root] += val;
        if (L < R)
            Lazy[root] += val;
        return;
    }
    if (Lazy[root])
        push_down(root);
    int mid = (L + R) >> 1;
    update(root << 1, L, mid, LL, RR, val);
    update(root << 1 | 1, mid + 1, R, LL, RR, val);
    push_up(root);
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        for (int j = 1, y; j <= x; j++) {
            cin >> y;
            vec[y / 2].push_back(i);
        }
    }
    memset(dp, -0x3f, sizeof dp);
    dp[1] = 0;
    for (int i = 2; i <= MAXN; i++) {
        for (int v : vec[i - 1]) {
            update(1, 1, MAXN, lst[v] + 1, i - 1, w[v]);
            lst[v] = i - 1;
        }
        dp[i] = max(dp[i], query(1, 1, MAXN, 1, i - 1));
        ans = max(ans, dp[i]);
        update(1, 1, MAXN, i, i, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

中午回家吃了一个菌菇牛肉自热饭，非常好吃。

下午依旧是2:10分到机房，闲着无聊直接开 genshin，但是免费时长只有 30min（）

帮昨天那一个老哥又挑了几道题，吧昨天考试题补了一下就下课了。

下课去了夫子庙，做了一趟南京的地铁（3号线从鸡鸣寺往秣周东路做4站到夫子庙站），骑了个车到夫子庙。

去里面逛了一下，看到了竹筒奶茶，但是30￥，没买。

在附近找到一个鸭血粉，非常好吃，我打算去买一根烤肠，结果发现有一家店一根烤肠15元:(

最后在 “喜姐炸串” 买了一个烤肠，才 5 块钱:)

又坐地铁，先做1号线7个站到南京站，再做一个站就到一个（忘记了叫什么的地方），然后在附近找了一个超市，买了云吞，面，饭，油，盐等一些东西。然后㕛骑了个车回公寓。

煮了个云吞，好吃喵。

然后开始打 CF。

不开 V*N 的话等了 30min 没有加载出来，开了就加载出来了/yun

T1一眼秒，T2构造想了一会，结果卡了30min交不上去，期间写了C，但是没过，D单调队列优dp写完了交出上去，凌晨1:00才睡。

Day 2

A

B

C

D

E

F

G

H

I

J

Status

Development

Support

Day 2

A

B

C

D

E

F

G

H

I

J

Status

Development

Support

Don't have an account?

SIGN IN