头像

垫底抽风




离线:22小时前


最近来访(4035)
用户头像
challow
用户头像
donghannuo
用户头像
acwing_933
用户头像
蒟弱
用户头像
ljz
用户头像
养生人
用户头像
yxc
用户头像
Maple28
用户头像
看不穿的宇宙
用户头像
cw12
用户头像
这可不好说
用户头像
栀梦
用户头像
钻石镐
用户头像
the_Octopus
用户头像
qa
用户头像
Rain丶bow
用户头像
ShanLin
用户头像
fxx_cwdy
用户头像
假装有个名字
用户头像
YimingLi

新鲜事 原文

垫底抽风
1个月前
这波,T3结论,我直接猜,交上去,过了!!! 大概算是这辈子运气最好的一次。


新鲜事 原文

垫底抽风
1个月前
https://www.acwing.com/file_system/file/content/whole/index/content/1433451/ 哈哈,我懒得写了。复制一份过来水一水。



垫底抽风
2个月前

题目链接

题目描述

在数轴上有 $n$ 个蜡烛,编号从 $1$ 到 $n$。

第 $i$ 个蜡烛在位置 $X _ i$,长度为 $A _ i$,并且处于燃烧状态。

蜡烛每燃烧一秒,长度减 $1$,即若某个燃烧状态的蜡烛长度为 $A$,那么它下一秒长度为 $A - 1$。

当某个蜡烛长度为 $0$ 时,它变为熄灭状态。熄灭的蜡烛长度不再改变。

初始时,时刻为 $0$,高桥在数轴上 $0$ 的位置。

每秒钟,高桥可以向左或向右移动一个位置,即如果高桥现在在位置 $p$,下一秒他可以移动到 $p + 1$ 或者 $p - 1$。

如果某个时刻,高桥所在位置有一个蜡烛,那么高桥可以选择熄灭这个蜡烛。如果高桥所在位置有多个蜡烛,高桥可以把它们都熄灭。熄灭的时间忽略不计。

你需要通过调整高桥的移动方式,使得经过 $10 ^ {100}$ 秒后,所有蜡烛长度的和的最大。

求出这个最大值。

数据范围

$1 \leq N \leq 300$
$-10 ^ 9 \leq X _ i \leq 10 ^ 9$
$1 \leq A _ i \leq 10 ^ 9$

输入样例1

3
-2 10
3 10
12 10

输出样例1

11

输入样例2

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

输出样例2

4999999994

Solution

(区间DP) $O(n ^ 3)$

$10 ^ {100}$ 秒的时间是足够长的,以至于此时一定所有蜡烛都熄灭。所以将这个时间视为无穷大。

考虑将蜡烛燃烧看成永久的,即如果高桥不熄灭,蜡烛永远燃烧,它的长度可以为负数。

那么原问题的答案,与以下问题的答案相等:

  • 高桥首先选择任意多个蜡烛,(有目的性地)移动过去熄灭这些蜡烛)。
  • 通过调整高桥的走位和高桥选的蜡烛,使得最后这些蜡烛长度的和最大。

为什么相等?

首先新问题的答案一定不超过原问题答案,因为在修改后的问题中,蜡烛永远燃烧,并且高桥选择其中一些蜡烛熄灭。

同时,对于原问题的任何一组合法解,在新问题中,高桥可以按照原问题进行移动,并且选择在原问题中熄灭的蜡烛,得到一组和原问题答案相等的解。

所以原问题最优解等于新问题最优解。

新问题是更好解决的,因为不需要考虑蜡烛自行熄灭的情况。以下考虑解决新问题。

维护每秒钟所有蜡烛的长度是很难的,但每秒蜡烛长度减少的总量是很容易维护的。

事实上只需要维护如下信息,就可以准确维护(高桥选择的)蜡烛总长度。

  • 每秒内,在高桥所选择的所有蜡烛中,未被高桥熄灭的蜡烛数量。

因为初始时高桥选择的蜡烛总长度是可以算的,对于每秒,只有未被高桥熄灭的蜡烛长度减 $1$。

同时,注意到高桥所走的路线只可能是一段(包含 $0$ 的)连续的区间。

回想一下数据范围,这启发我们考虑区间$\text{DP}$。

先将所有数据按 $X$ 排序,这不影响答案。

这时有 $X _ 1 \leq X _ 2 \leq \cdots \leq X _ i \leq \cdots \leq X _ j \leq \cdots \leq X _ n$。

考虑令 $f[i][j][k]$ 表示高桥已经走过 $[X _ i, X _ j]$(即以某种走位熄灭该区间内所有蜡烛),且在高桥所选的所有蜡烛中有 $k$ 个未被熄灭,所被熄灭的蜡烛的长度和的最大值。

无法转移。这是因为我们不确定高桥所在的位置,以至于不知道高桥接下来移动时所经过的距离。

注意到高桥走过 $[X _ i, X _ j]$ 后,一定在区间的边界上,因此将 $f[i][j][k]$ 拆成两个状态进行表示:

$f[i][j][k][0 / 1]$ 表示高桥已经走过 $[X _ i, X _ j]$(即以某种走位熄灭该区间内所有蜡烛),且在高桥所选的所有蜡烛中有 $k$ 个未被熄灭,且此时高桥在区间 $[X _ i, X _ j]$ 的 左/右 端点,所被熄灭的蜡烛的长度和的最大值。

为什么只需要维护在选的蜡烛中有多少个未被熄灭,而不是维护选了多少个蜡烛在选的蜡烛中熄灭了多少个

因为如果维护两个状态,空间和时间的复杂度都是不接受的。

并且根据上面的结论,可以计算每秒钟被高桥选择的蜡烛的长度的变化量。

事实上,在状态转移时,需要动态决策每个蜡烛是否被选择。接下来考虑状态转移。

先不考虑左右端点和 $k$ 的情况,转移一定是如下形式的。

$f[i][j][\cdots] = \max\{f[i + 1][j][\cdots], f[i][j - 1][\cdots]\}$

接下来将 $k$ 填进去。

$k$ 的更新要考虑是否选择了 左/右 端点的蜡烛。由于左右端点对称,这里仅以左端点为例、

先考虑不选择的情况。

$f[i][j][k][\cdots] = \max\{f[i + 1][j][k][\cdots] - |X _ i - X _ {i + 1}| \times k, f[i + 1][j][k][\cdots] - |X _ i - X _ j| \times k\}$

其中左边需要减去 $|X _ i - X _ {i + 1}| \times k$,是因为需要考虑在高桥从 $X _ i$ 移动至 $X _ {i + 1}$ 时所选择的蜡烛的总长度的变化。右边减去同理。

再考虑选择左端点上蜡烛的情况。

$f[i][j][k][\cdots] = \max\{f[i + 1][j][k + 1][\cdots] + A _ i - |X _ i - X _ {i + 1}| \times k, f[i + 1][j][k + 1]\cdots] + A _ i - |X _ i - X _ j| \times k\}$

减项的原因和上面相同。

转移时再具体分析左右端点即可,可见代码。这里不再说明填入左右端点的情况。

时间复杂度

状态数量是 $O(n ^ 3)$,转移复杂度为 $O(1)$。故总复杂度为 $O(n ^ 3)$。

另外,空间复杂度也是 $O(n ^ 3)$ 的,并且需要开 long long,空间开销也是很大的。

$\text{AtCoder}$的空间限制一般是$\text{1GB}$,因此不需要使用滚动数组。

可以用滚动数组将空间优化至 $O(n)$。


Code

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 305;
const int dx[2] = {0, 1}, dy[2] = {-1, 0}, ds[2] = {1, 0};

int n;
LL f[N][N][N][2];
struct Data {
    int x, w;
    bool operator < (const Data &t) const {
        return x < t.x;
    }
} g[N];

// f[x][y][k][0/1]
//
// f[x][y][k] << max{f[x + 1][y][k], f[x][y - 1][k]}
// f[x][y][k] << f[x + 1][y][k + 1] + val[x] - (k + 1) * (pos[x + 1], pos[y] -> pos[x])
// f[x][y][k] << f[x][y - 1][k + 1] + val[y] - (k + 1) * (pos[x], pos[y - 1] -> pos[y])
//

int dis(int x, int y) {
    return g[x].x < g[y].x ? g[y].x - g[x].x : g[x].x - g[y].x;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &g[i].x, &g[i].w);
    }
    g[n++] = (Data){0, 0};
    sort(g, g + n);
    int beg = 0;
    while (g[beg].x || g[beg].w) ++beg;
    memset(f, -0x3f, sizeof f);
    for (int k = 0; k <= n; ++k) {
        f[beg][beg][k][0] = f[beg][beg][k][1] = 0;
    }
    for (int len = 1; len < n; ++len) {
        for (int x = 0, y; (y = x + len) < n; ++x) {
            for (int k = n; ~k; --k) {
                for (int d = 0; d < 2; ++d) {
                    int tx = x + dx[d], ty = y + dy[d], s = ds[d];
                    int cur = s ? y : x, d1 = dis(cur, tx), d2 = dis(cur, ty);
                    LL *v = f[tx][ty][k], &w = f[x][y][k][s];
                    w = max(v[0] - (LL)k * d1, v[1] - (LL)k * d2);
                    w = max(w, v[2] + g[cur].w - (k + 1ll) * d1);
                    w = max(w, v[3] + g[cur].w - (k + 1ll) * d2);
                }
            }
        }
    }
    LL res = 0;
    for (int k = 0; k <= n; ++k) {
#define f f[0][n - 1][k]
        res = max(res, max(f[0], f[1]));
    }
    printf("%lld\n", res);
    return 0;
}

$$ $$



新鲜事 原文

垫底抽风
2个月前
各位如果明天参加CSP,记得带好黑色签字笔、2B铅笔、橡皮、准考证、身份证。听说今年要涂答题卡,记得带涂卡笔。记得看好考试的时间与考点,预估好去考点的时间。记得看好答题卡使用说明。考场上不要紧张。考场上每做题后检查一遍,两个小时的时间应该是足够的。在不确定答案的时候,不要轻易改答案。遇到不会的题、没学过的题,就随便蒙一个选项,然后往后做就好了。不要轻易提前交卷。最后祝大家,$\large \huge \text{CSP RP++}$。


新鲜事 原文

垫底抽风
2个月前
纪念第一次在AcWing周赛拿到rk1。 感谢灵茶山艾府、墨染空、zqy1018、10circle、whsstory、難等大佬没有参加此次竞赛,得以让俺这个菜鸡侥幸夺冠。
图片


活动打卡代码 AcWing 273. 分级

垫底抽风
2个月前
#include <stdio.h>
#include <string.h>

const int N = 2005, INF = 0x7F7F7F7F;

int n, a[N], b[N];
int f[N][N], res = INF;

void swap(int &a, int &b) {
    a ^= b ^= a ^= b;
}

void cmin(int &a, const int b) {
    a = a < b ? a : b;
}

int min(const int a, const int b) {
    return a < b ? a : b;
}

int abs(const int x) {
    return x < 0 ? -x : x;
}

void work() {
    for (int i = 1; i <= n; ++i) {
        int minf = INF;
        for (int j = 1; j <= n; ++j) {
            cmin(minf, f[i - 1][j]);
            f[i][j] = minf + abs(a[i] - b[j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        cmin(res, f[n][i]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }
    memcpy(b + 1, a + 1, n << 2);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < n; ++j) {
            if (b[j] > b[j + 1]) {
                swap(b[j], b[j + 1]);
            }
        }
    }
    work();
    for (int i = 1; i << 1 < n + 1; ++i) {
        swap(b[i], b[n - i + 1]);
    }
    work();
    printf("%d\n", res);
    return 0;
}



垫底抽风
2个月前
#include <stdio.h>
#include <string.h>

const int N = 3005;

int n;
int a[N], b[N];
int f[N][N];

int max(const int a, const int b) {
    return a > b ? a : b;
}
void cmax(int &a, const int b) {
    a = a > b ? a : b;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", b + i);
    }
    for (int j = 1; j <= n; ++j) {
        int maxf = 0;
        for (int i = 1; i <= n; ++i) {
            f[i][j] = f[i][j - 1];
            if (a[i] == b[j]) f[i][j] = maxf + 1;
            else if (a[i] < b[j]) maxf = max(maxf, f[i][j - 1]);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        cmax(res, f[i][n]);
    }
    printf("%d\n", res);
    return 0;
}



垫底抽风
2个月前
#include <stdio.h>
#include <string.h>

typedef long long LL;
const int N = 31;

int n, s[N];
LL f[N][N][N][N][N];

int main() {
    while (scanf("%d", &n), n) {
        memset(s, 0, sizeof s);
        for (int i = 0; i < n; ++i) {
            scanf("%d", s + i);
        }
        f[0][0][0][0][0] = 1;
        for (int a = 0; a <= s[0]; ++a) {
            for (int b = 0; b <= s[1] && b <= a; ++b) {
                for (int c = 0; c <= s[2] && c <= b; ++c) {
                    for (int d = 0; d <= s[3] && d <= c; ++d) {
                        for (int e = 0; e <= s[4] && e <= d; ++e) {
                            LL &v = f[a][b][c][d][e];
                            if (a || b || c || d || e) v = 0;
                            if (a) v += f[a - 1][b][c][d][e];
                            if (b) v += f[a][b - 1][c][d][e];
                            if (c) v += f[a][b][c - 1][d][e];
                            if (d) v += f[a][b][c][d - 1][e];
                            if (e) v += f[a][b][c][d][e - 1];
                        }
                    }
                }
            }
        }
        printf("%lld\n", f[s[0]][s[1]][s[2]][s[3]][s[4]]);
    }
    return 0;
}


活动打卡代码 AcWing 268. 流星

垫底抽风
3个月前

整体二分

#include <stdio.h>
#include <string.h>

typedef long long LL;

char buf[1 << 21], *p1 = buf, *p2 = buf;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? -1 : *p1++)
int read() {
    int x = 0; char c = gc();
    while (c < 48 || c > 57) c = gc();
    for (; c > 47 && c < 58; c = gc()) x = x * 10 + (c ^ 48);
    return x;
}
void swap(int& a, int& b) {
    a ^= b ^= a ^= b;
}

const int N = 3e5 + 5;

int n, m, Q;
int h[N], ne[N];
int b[N], res[N], id[N];
struct Opt {int x, y, c;} q[N];

LL fw[N];
void add(int x, const int c) {
    for (; x <= m; x += x & -x) fw[x] += c;
}
void add(const int x, const int y, const int c) {
    add(x, c), add(y + 1, -c);
    if (y < x) add(1, c);
}
LL qry(int x) {
    LL s = 0;
    for (; x; x &= x - 1) s += fw[x];
    return s;
}

bool check(int x) {
    LL s = b[x];
    for (int i = h[x]; i; i = ne[i]) {
        if ((s -= qry(i)) <= 0) {
            return false;
        }
    }
    return true;
}

void solve(int l, int r, int ql, int qr) {
    if (ql > qr) return;
    if (l == r) {
        for (int i = ql; i <= qr; ++i) {
            res[id[i]] = r;
        }
        return;
    }
    int mid = l + r >> 1, i = ql, j = qr;
    for (int k = l; k <= mid; ++k) {
        add(q[k].x, q[k].y, q[k].c);
    }
    while (i <= j) {
        while (i <= j && !check(id[i])) ++i;
        while (i <= j && check(id[j])) --j;
        if (i <= j) swap(id[i], id[j]);
    }
    solve(mid + 1, r, i, qr);
    for (int k = l; k <= mid; ++k) {
        add(q[k].x, q[k].y, -q[k].c);
    }
    solve(l, mid, ql, j);
}

int main() {
    n = read(), m = read();
    for (int i = 1, x; i <= m; ++i) {
        x = read();
        ne[i] = h[x], h[x] = i;
    }
    for (int i = 1; i <= n; ++i) {
        b[i] = read();
    }
    Q = read();
    for (int i = 1; i <= Q; ++i) {
        int x = read(), y = read(), c = read();
        q[i] = (Opt){x, y, c};
        add(x, y, c);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (check(i)) {
            res[i] = -1;
        } else {
            id[++cnt] = i;
        }
    }
    memset(fw + 1, 0, m << 3);
    solve(1, Q, 1, cnt);
    for (int i = 1; i <= n; ++i) {
        if (~res[i]) {
            printf("%d\n", res[i]);
        } else {
            puts("NIE");
        }
    }
    return 0;
}


活动打卡代码 AcWing 267. 莫基亚

垫底抽风
3个月前

树状数组套线段树

#include <stdio.h>
#include <string.h>
#include <algorithm>

using std::sort;
using std::unique;

char buf[1 << 21], *p1 = buf, *p2 = buf;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? -1 : *p1++)
int read() {
    char c = gc(); int x = 0;
    while (c < 48 || c > 57) c = gc();
    for (; c > 47 && c < 58; c = gc()) x = x * 10 + (c ^ 48);
    return x;
}

const int M = 200005;
const int N = 2e7 + 5;
const int R = 2e6 + 5;

int n, dfy[M << 1], sz;

int get(int x) {
    int l = 0, r = sz - 1, mid;
    while (l < r) {
        mid = l + r >> 1;
        if (dfy[mid] >= x) r = mid;
        else    l = mid + 1;
    }
    return r + 1;
}

int idx;
struct Tree {
    int l, r, v;
} tr[N];
void update(const int x) {
    tr[x].v = tr[tr[x].l].v + tr[tr[x].r].v;
}
struct SegmentTree {
    int rt;
    SegmentTree() {
        rt = 0;
    }
    void add(int d, int c, int l, int r, int &x) {
        if (!x) x = ++idx;
        if (l == r) {
            tr[x].v += c;
        } else {
            int mid = l + r >> 1;
            if (d <= mid) add(d, c, l, mid, tr[x].l);
            else    add(d, c, mid + 1, r, tr[x].r);
            update(x);
        }
    }
    int qry(int d, int l, int r, int &x) {
        if (!x) return 0;
        if (r <= d) return tr[x].v;
        int mid = l + r >> 1;
        if (d <= mid) return qry(d, l, mid, tr[x].l);
        return qry(d, l, mid, tr[x].l) + qry(d, mid + 1, r, tr[x].r);
    }
    void add(int d, int c) {
        add(d, c, 0, sz, rt);
    }
    int qry(int x) {
        return qry(x, 0, sz, rt);
    }
} sgt[R];

void add(int x, int y, int c) {
    for (; x <= n; x += x & -x) sgt[x].add(y, c);
}

int qry(int x, int y) {
    int res = 0;
    for (; x; x &= x - 1) res += sgt[x].qry(y);
    return res;
}

int x[M], y[M], c[M], x2[M], y2[M], m, t;
int main() {
    n = (read(), read());
    while ((t = read()) != 3) {
        x[m] = read(), y[m] = read();
        if (t == 1) {
            c[m] = read();
        } else {
            x2[m] = read(), y2[m] = read();
            dfy[sz++] = y2[m];
        }
        dfy[sz++] = y[m];
        ++m;
    }
    sort(dfy, dfy + sz);
    sz = unique(dfy, dfy + sz) - dfy;
    #define x x[i]
    #define y y[i]
    #define c c[i]
    #define x2 x2[i]
    #define y2 y2[i]
    for (int i = 0; i < m; ++i) {
        y = get(y);
        if (c) {
            add(x, y, c);
        } else {
            y2 = get(y2), --x, --y;
            printf("%d\n", qry(x2, y2) - qry(x2, y) - qry(x, y2) + qry(x, y));
        }
    }
    return 0;
}

CDQ 分治

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
const int M = 200005;
const int N = 2000005;
const int Q = 10005;

int W, n, m;
int fw[N];
ll res[Q];

struct Query {
    int x, y, z, d;
    inline bool operator < (const Query& t) const {
        return x != t.x ? x < t.x : y < t.y;
    }
} w[M], t[M];

inline void add(int x, const int c) {
    if (!x) puts("???"), exit(0);
    for (; x <= W; x += x & -x) fw[x] += c;
}

inline int qry(int x) {
    int res = 0;
    for (; x; x &= x - 1) res += fw[x];
    return res;
}

void CDQ(int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    CDQ(l, mid), CDQ(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (w[i].x <= w[j].x) {
            if (!w[i].d) add(w[i].y, w[i].z);
            t[k++] = w[i++];
        } else {
            if (w[j].d) res[w[j].z] += w[j].d * qry(w[j].y);
            t[k++] = w[j++];
        }
    }
    while (i <= mid) {
        if (!w[i].d) add(w[i].y, w[i].z);
        t[k++] = w[i++];
    }
    while (j <= r) {
        res[w[j].z] += w[j].d * qry(w[j].y);
        t[k++] = w[j++];
    }
    for (i = l; i <= mid; ++i)
        if (!w[i].d)
            add(w[i].y, -w[i].z);
    for (i = 0; i < k; ++i) w[i + l] = t[i];
}

int main() {
    int t, x, y, xt, yt, z;
    scanf("%d%d", &t, &W);
    while (scanf("%d", &t), t != 3) {
        if (t == 1) {
            scanf("%d%d%d", &x, &y, &z);
            w[m++] = {x, y, z, 0};
        } else {
            scanf("%d%d%d%d", &x, &y, &xt, &yt);
            w[m++] = {x - 1, y - 1, n, 1};
            w[m++] = {x - 1, yt, n, -1};
            w[m++] = {xt, y - 1, n, -1};
            w[m++] = {xt, yt, n, 1};
            ++n;
        }
    }
    CDQ(0, m - 1);
    for (int i = 0; i < n; ++i) printf("%lld\n", res[i]);
}