JOI Final 2020 题解

作者: xht37 分类: 题解 发布时间: 2020-04-20 16:45

点击数:85

JOI Final 2020

長いだけのネクタイ (Just Long Neckties)

显然 $a,b$ 排序后对应位置上的数相减最优,multiset 维护一下即可,时间复杂度 $\mathcal O(n \log n)$。

const int N = 2e5 + 7;
int n, a[N], b[N], p[N], ans[N];
multiset<int> s;

int main() {
    rd(n), rda(a, n + 1), rda(b, n);
    for (int i = 1; i <= n + 1; i++) p[i] = i;
    sort(p + 1, p + n + 2, [&](int i, int j) { return a[i] < a[j]; });
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) s.insert(max(a[p[i+1]] - b[i], 0));
    ans[p[1]] = *--s.end();
    for (int i = 1; i <= n; i++) {
        s.erase(s.find(max(a[p[i+1]] - b[i], 0)));
        s.insert(max(a[p[i]] - b[i], 0));
        ans[p[i+1]] = *--s.end();
    }
    for (int i = 1; i <= n + 1; i++)
        print(ans[i], " \n"[i==n+1]);
    return 0;
}

JJOOII 2 (JJOOII 2)

前缀和一下,然后枚举开头 $s$,二分出从 $s$ 开始的第 $k$ 个 J 的位置 $x$,从 $x$ 开始的第 $k$ 个 O 的位置 $y$,从 $y$ 开始的第 $k$ 个 I 的位置 $z$,从而求得答案,时间复杂度 $\mathcal O(n \log n)$。

当然也可以用类似 Two Pointers 的思想做到线性。

const int N = 2e5 + 7, inf = 1e9;
int n, k, f[3][N], ans = inf;
char s[N];

int main() {
    rd(n, k), rds(s, n);
    map<char, int> p;
    p['J'] = 0, p['O'] = 1, p['I'] = 2;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) f[j][i] = f[j][i-1];
        ++f[p[s[i]]][i];
    }
    for (int i = 0; i < n; i++) {
        if (f[0][i] + k > f[0][n]) break;
        int x = lower_bound(f[0] + 1, f[0] + n + 1, f[0][i] + k) - f[0];
        if (f[1][x] + k > f[1][n]) break;
        int y = lower_bound(f[1] + 1, f[1] + n + 1, f[1][x] + k) - f[1];
        if (f[2][y] + k > f[2][n]) break;
        int z = lower_bound(f[2] + 1, f[2] + n + 1, f[2][y] + k) - f[2];
        ans = min(ans, z - i - 3 * k);
    }
    print(ans == inf ? -1 : ans);
    return 0;
}

スタンプラリー 3 (Collecting Stamps 3)

断环成链,区间 DP。

设 $f_{l,r,0/1,i}$ 表示已经处理了 $l\sim r$ 种邮票,现在在 $l/r$ 的位置上,已经收集了 $i$ 种邮票的最小花费时间。

每次枚举走到 $l-1$ 还是走到 $r+1$,时间复杂度 $\mathcal O(n^3)$。

const int N = 207;
const ll inf = 1e18;
int n, m, p[N<<1|1], t[N<<1|1], ans;
ll f[N<<1|1][N<<1|1][2][N];

inline void upd(ll &x, ll y) {
    x = min(x, y);
}

int main() {
    rd(n, m), rda(p + n + 1, n), rda(t + n + 1, n);
    for (int i = 1; i <= n; i++) p[i] = p[i+n+1] - m, t[i] = t[i+n+1];
    for (int l = 1; l <= n + 1; l++)
        for (int r = n + 1; r <= (n << 1 | 1); r++)
            for (int k = 0; k < 2; k++)
                for (int i = 0; i <= n; i++)
                    f[l][r][k][i] = inf;
    f[n+1][n+1][0][0] = f[n+1][n+1][1][0] = 0;
    for (int len = 0; len < n; len++)
        for (int l = n + 1 - len, r = n + 1; l <= n + 1; l++, r++)
            for (int k = 0; k < 2; k++)
                for (int i = 0; i < n; i++)
                    upd(f[l-1][r][0][i+(f[l][r][k][i]+p[k?r:l]-p[l-1]<=t[l-1])],
                        f[l][r][k][i] + p[k?r:l] - p[l-1]),
                    upd(f[l][r+1][1][i+(f[l][r][k][i]+p[r+1]-p[k?r:l]<=t[r+1])],
                        f[l][r][k][i] + p[r+1] - p[k?r:l]);
    for (int l = 1; l <= n + 1; l++)
        for (int r = n + 1; r <= (n << 1 | 1); r++)
            for (int k = 0; k < 2; k++)
                for (int i = 0; i <= n; i++)
                    if (f[l][r][k][i] != inf) ans = max(ans, i);
    print(ans);
    return 0;
}

オリンピックバス (Olympic Bus)

首先求出不变向时的答案,由于本题中的图是稠密图,我们考虑用 $\mathcal O(n^2 + m)$ 的 Dijkstra 跑。

考虑一条边 $(u,v)$ 变向之后造成的影响,不妨考虑 $1 \to n$ 的部分,$n \to 1$ 同理。

如果 $(u,v)$ 不在原本 $1 \to n$ 的最短路上,则此时的最短路要么不变,要么是强制经过 $(v,u)$ 且不经过 $(u,v)$ 的最短路。

考虑如何求后者,相当于我们要求不经过 $(u,v)$ 的情况下 $1 \to v$ 和 $u \to n$ 的最短路。考虑图中以 $1$ 为起点的最短路树和反图中以 $n$ 为起点的最短路树,若 $(u,v)$ 不在前/后者中,则可以直接得到答案,否则重新跑一遍最短路。由于最短路树上的边数只有 $\mathcal O(n)$ 条,因此这部分的时间复杂度为 $\mathcal O(n^3 + nm)$。

如果 $(u,v)$ 在原本 $1 \to n$ 的最短路上,则同样重新跑一遍最短路,时间复杂度同样为 $\mathcal O(n^3 + nm)$。

const int N = 207, M = 1e5 + 7;
const ll inf = 1e18;
int n, m;
int h[N], e[M], t[M], tot = 1;
ll c[M], d[M], now, ans = inf;
bool u[M];
struct Gragh {
    ll f[N];
    bool in[M];
} G1, Gn, GT1, GTn;

inline void add(int x, int y, int c, int d, int o = 1) {
    e[++tot] = y, t[tot] = h[x], h[x] = tot;
    ::c[tot] = c, ::d[tot] = d, u[tot] = o;
    if (o) add(y, x, c, d, 0);
}

namespace Dij {
    ll e[N][N], f[N];
    int a[N][N], g[N];
    bool v[N];

    inline ll dij(int S, int T) {
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= n; y++)
                e[x][y] = inf;
            for (int i = h[x]; i; i = t[i]) {
                if (!u[i]) continue;
                int y = ::e[i];
                if (e[x][y] > c[i])
                    e[x][y] = c[i], a[x][y] = i;
            }
        }
        for (int i = 0; i <= n; i++)
            f[i] = inf, g[i] = v[i] = 0;
        f[S] = 0;
        for (int i = 1; i <= n; i++) {
            int x = 0;
            for (int j = 1; j <= n; j++) {
                if (v[j]) continue;
                if (f[j] < f[x]) x = j;
            }
            v[x] = 1;
            for (int y = 1; y <= n; y++) {
                if (v[y]) continue;
                if (f[y] > f[x] + e[x][y])
                    f[y] = f[x] + e[x][y], g[y] = a[x][y];
            }
        }
        return f[T];
    }

    inline void get(Gragh &G) {
        for (int i = 1; i <= n; i++) G.f[i] = f[i], G.in[g[i]] = 1;
    }
}
using Dij::dij;
using Dij::get;

inline ll work(int i) {
    now = d[i];
    u[i] = 0, u[i^1] = 1;
    if (G1.in[i]) now += dij(1, n);
    else {
        ll cur = c[i] + G1.f[e[i]];
        if (GTn.in[i]) cur += dij(e[i^1], n);
        else cur += GTn.f[e[i^1]];
        now += min(G1.f[n], cur);
    }
    if (Gn.in[i]) now += dij(n, 1);
    else {
        ll cur = c[i] + Gn.f[e[i]];
        if (GT1.in[i]) cur += dij(e[i^1], 1);
        else cur += GT1.f[e[i^1]];
        now += min(Gn.f[1], cur);
    }
    u[i] = 1, u[i^1] = 0;
    return now;
}

int main() {
    rd(n, m);
    for (int i = 1, x, y, c, d; i <= m; i++)
        rd(x, y), rd(c, d), add(x, y, c, d);
    now += dij(1, n), get(G1);
    now += dij(n, 1), get(Gn);
    ans = min(ans, now);
    for (int i = 2; i <= tot; i++) u[i] ^= 1;
    dij(1, n), get(GT1);
    dij(n, 1), get(GTn);
    for (int i = 2; i <= tot; i++) u[i] ^= 1;
    for (int i = 2; i <= tot; i += 2) ans = min(ans, work(i));
    print(ans == inf ? -1 : ans);
    return 0;
}

火事 (Fire)

考虑平面直角坐标系中 $([1,n],[0,n])$ 的部分,其中 $(i,j)$ 对应题目中的 $S_i(j)$。

注意到每个 $S_i$ 的覆盖范围都是一个平行四边形,而这样一个平行四边形可以拆成四个三角形,每个三角形 $(a,b,c)$ 表示 $([a,+\infty), [x-b,+\infty))$ 的部分权值 $+c$。

再看询问,一次询问 $(t,l,r)$ 可以差分为 $(t,r) – (t,l-1)$,其中 $(t,p)$ 表示 $((-\infty, p], t)$ 的权值和。

于是问题变成 $(a,b,c)$ 加 $(t,p)$ 求和,以 $y$ 轴正方向进行扫描线,考虑一个 $(a,b,c)$ 在满足 $a-b \le t$ 的情况下对 $(t,p)$ 的贡献为 $c\cdot (\min(t+b,p)-\min(a-1,p))$。

由于 $(t,p)$ 是 $(t,l,r)$ 差分而来的,不妨将这个贡献差分前后都减去 $ct$,则贡献为 $c\cdot (\min(b,p-t)-\min(a-1,p))$。

考虑在 $p-t$ 处维护 $c\cdot \min(b,p-t)$ 的贡献,在 $p$ 处维护 $c \cdot \min(a-1,p)$ 的贡献。于是问题变成维护一个序列,每次在 $x$ 处加 $c \cdot \min(k,x)$,同时单点查询,用两个树状数组即可维护。

最后的问题是如何找到每个 $S-i$ 覆盖的平行四边形,其实就是要找到每个 $S_i$ 左边第一个 $> S_i$ 和右边第一个 $\ge S_i$ 的位置,正反做两次单调栈即可。

总时间复杂度 $\mathcal O(n \log n)$。

const int N = 2e5 + 7;
int n, m, l[N], r[N];
ll a[N], ans[N];
struct P {
    int a, b;
    ll c;
    inline P() {}
    inline P(int a, int b, ll c) : a(a), b(b), c(c) {}
};
vector<P> p[N];
struct Q {
    int p, i, o;
    inline Q() {}
    inline Q(int p, int i, int o) : p(p), i(i), o(o) {}
};
vector<Q> q[N];
struct BIT {
    vector<ll> c;
    inline BIT(int n = N) { c.resize(n); }
    inline void add(ui x, ll k) {
        while (x < c.size()) c[x] += k, x += x & -x;
    }
    inline ll ask(ui x) {
        ll k = 0;
        while (x) k += c[x], x -= x & -x;
        return k;
    }
};

int main() {
    rd(n, m), rda(a, n);
    for (int i = 1, t, l, r; i <= m; i++) {
        rd(t, l, r);
        q[t].pb(Q(r, i, 1));
        q[t].pb(Q(l - 1, i, -1));
    }
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() && a[st.top()] <= a[i]) st.pop();
        l[i] = st.size() ? st.top() : 0;
        st.push(i);
    }
    while (st.size()) st.pop();
    for (int i = n; i; i--) {
        while (st.size() && a[st.top()] < a[i]) st.pop();
        r[i] = st.size() ? st.top() : n + 1;
        st.push(i);
    }
    for (int i = 1; i <= n; i++) {
        p[0].pb(P(i, i, a[i]));
        if (l[i]) p[i-l[i]].pb(P(i, l[i], -a[i]));
        if (r[i] != n + 1) p[r[i]-i].pb(P(r[i], i, -a[i]));
        if (l[i] && r[i] != n + 1) p[r[i]-l[i]].pb(P(r[i], l[i], a[i]));
    }
    BIT cx1 = BIT(N << 1 | 1), ck1 = BIT(N << 1 | 1), cx2, ck2;
    for (int t = 0; t <= n; t++) {
        for (P p : ::p[t]) {
            int a = p.a, b = p.b;
            ll c = p.c;
            cx1.add(1, c), cx1.add(b + n + 1, -c);
            ck1.add(b + n + 1, c * b);
            cx2.add(1, c), cx2.add(a, -c);
            ck2.add(a, c * (a - 1));
        }
        for (Q o : ::q[t]) {
            int p = o.p;
            ans[o.i] += o.o * cx1.ask(p - t + n + 1) * (p - t);
            ans[o.i] += o.o * ck1.ask(p - t + n + 1);
            ans[o.i] -= o.o * cx2.ask(p + 1) * p;
            ans[o.i] -= o.o * ck2.ask(p + 1);
        }
    }
    for (int i = 1; i <= m; i++) print(ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注