JOISC2020总结&题解

程序员文章站 2022-03-14 19:39:14

...

距离比赛过去快一个星期了……
一共四场，每一场的题目都不是普通人能够做出来的。
以至于每次比赛都是两位数或者一位数的得分……
后来大多数题目也都搞清楚了，感觉收获还是蛮大的。
尽管改完的题不多，但题解就先挂在这儿。
~~PS：没改完题就打题解，还有一个愿意是gjx的题太恶心了~~

Day1T1

后来统计数据证明这是签到题，然而我却没有AC。
很不爽的是，我比赛时似乎成功将正解的那个结论证伪了。

暴力的做法，就是设一个 $f_{i,j,0/1}$ ，大家都会。
打表或归纳证明可以发吗，对于每个 $i$ 和 $0/1$ ，合法的 $j$ 都是连续一段。
于是我们只需要维护 $j$ 的左右端点。

using namespace std;
#include <cstdio>
#include <algorithm>
#define N 500010
int n;
int a[N * 2][2];
int l[N * 2][2], r[N * 2][2];
void print(int i, int j, int x) {
    if (i == 1) {
        putchar('A' + j);
        return;
    }
    for (int k = 0; k < 2; ++k)
        if (a[i - 1][k] <= a[i][j]) {
            if (l[i - 1][k] <= x - j && x - j <= r[i - 1][k]) {
                print(i - 1, k, x - j);
                putchar('A' + j);
                return;
            }
        }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n * 2; ++i) scanf("%d", &a[i][0]);
    for (int i = 1; i <= n * 2; ++i) scanf("%d", &a[i][1]);
    l[1][0] = 0, r[1][0] = 0;
    l[1][1] = 1, r[1][1] = 1;
    for (int i = 2; i <= 2 * n; ++i) {
        l[i][0] = l[i][1] = 2 * n;
        r[i][0] = r[i][1] = 0;
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k)
                if (a[i - 1][k] <= a[i][j]) {
                    l[i][j] = min(l[i][j], l[i - 1][k] + j);
                    r[i][j] = max(r[i][j], r[i - 1][k] + j);
                }
        }
    }
    if (min(l[2 * n][0], l[2 * n][1]) <= n && n <= max(r[2 * n][0], r[2 * n][1])) {
        if (l[2 * n][0] <= n && n <= r[2 * n][0])
            print(2 * n, 0, n);
        else
            print(2 * n, 1, n);
    } else
        printf("-1\n");
    return 0;
}

Day1T2

比赛时全在刚T1去了，这题也没有什么思路。
这是我比赛之后改的第四道题，但现在看来这是个糟糕的选择。
虽然AC了，但耗了我两天：一天学 $2-SAT$ ，一天写程序。
CC大佬说这是他心中最难的题，我想对于他来说，最难的题就是最难写的题吧……

考虑一维的情况：即是一堆线段，你要选若干个点，使得每条线段至少包含一个点。
求出 $minr$ 表示最小的右端点。因为右端点为 $minr$ 的线段要被照顾到，所以存在一个点坐标小于等于 $minr$ 。但为了使得能够在同时尽量包含更多线段，这个点应该选在 $minr$ 。
策略出来了：选择 $minr$ ，将包含它的线段删去，剩下的就是一个 $K-1$ 的子问题，递归继续做。
回到二维。同理地求出 $maxl,minu,maxd$
只考虑 $maxl>minr,maxd>minu$ 的情况（其它的情况一个等同于一维，一个矩形全部交在一起）
同理，可以发现这些代表的四条直线（进一步可以发现是线段）中，都必定会有个点。
考虑 $K\leq 3$ 的情况。
三个点要被四条直线包含，所以一个点至少要在交点上。
枚举这个交点，除去包含它的矩形，剩余的变成子问题递归下去做。
接下来就是 $K=4$
首先同样用枚举交点的做法搞一遍，如果没有出答案，那么情况只剩下：四个点分别在四条直线上。
如果一个矩形和三条直线有交，那么它一定包含一个线段。所以这个矩形可以忽略。
剩下与一条边相交的矩形和与两条边相交的矩形（后者可分成与邻边相交和与对边相交）。
对于后者，记 $0/1$ 表示点在哪条直线上。
在同一条直线上，如果有两个不相交的矩形 $a$ 和 $b$ ，他们选这条直线分别用 $x$ 和 $y$ 表示，那么 $a$ 选 $x$ 和 $b$ 选 $y$ 不能同时成立。
这是个 $2-SAT$ 问题，用线段树优化连边来跑 $2-SAT$ 就好了。
对于在同一条直线上的前者，可以将他们的相交区间取交，然后可以看做和两条边相交的矩形，但是强制选一条边。这是 $2-SAT$ 的基本操作之一。

码量吓死人。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
#define INF 1000000000
int n, K;
struct Sqr {
    int l, r, d, u;
} s[N], sc[N];
int did[N];
struct DOT {
    int x, y;
} ans[5];
inline bool in(int x, int y, Sqr &s) { return s.l <= x && x <= s.r && s.d <= y && y <= s.u; }
inline void put(int k, int x, int y) {
    for (int i = 1; i <= n; ++i)
        if (!did[i] && in(x, y, s[i]))
            did[i] = k;
    ans[k] = { x, y };
}
inline void take(int k) {
    for (int i = 1; i <= n; ++i)
        if (did[i] == k)
            did[i] = 0;
}
struct EDGE {
    int to;
    EDGE *las;
} e[N * 400];
int ne;
EDGE *last[N * 40];
inline void link(int u, int v, EDGE *lst[] = last) {
    e[ne] = { v, lst[u] };
    lst[u] = e + ne++;
}
int nc, nr;
int num, t[8][8 * N];
void build(int t[], int k, int l, int r) {
    t[k] = ++num;
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(t, k << 1, l, mid);
    build(t, k << 1 | 1, mid + 1, r);
    link(t[k], t[k << 1]);
    link(t[k], t[k << 1 | 1]);
}
void lk_to(int t[], int k, int l, int r, int x, int u) {
    if (l == r) {
        link(t[k], u);
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        lk_to(t, k << 1, l, mid, x, u);
    else
        lk_to(t, k << 1 | 1, mid + 1, r, x, u);
}
void lk_from(int t[], int k, int l, int r, int st, int en, int u) {
    if (st <= l && r <= en) {
        link(u, t[k]);
        return;
    }
    int mid = l + r >> 1;
    if (st <= mid)
        lk_from(t, k << 1, l, mid, st, en, u);
    if (mid < en)
        lk_from(t, k << 1 | 1, mid + 1, r, st, en, u);
}
int *p[N * 2], np;
inline bool cmpp(int *a, int *b) { return *a < *b; }
int id[N][2], its[N][2], L[N][2], R[N][2];
struct Range {
    int l, r, id, _01;
} ran[4][N * 2];
inline bool cmpr(const Range &a, const Range &b) { return a.r < b.r; }
inline bool cmpl(const Range &a, const Range &b) { return a.l > b.l; }
int cnt[4];
int mxL[4], mnR[4];
int nowdfn, dfn[N * 40], low[N * 40], bel[N * 40], nb;
int q[N * 40], tp;
void tarjan(int x) {
    low[x] = dfn[x] = ++nowdfn;
    q[++tp] = x;
    for (EDGE *ei = last[x]; ei; ei = ei->las)
        if (!dfn[ei->to])
            tarjan(ei->to), low[x] = min(low[x], low[ei->to]);
        else if (!bel[ei->to])
            low[x] = min(low[x], dfn[ei->to]);
    if (low[x] == dfn[x]) {
        bel[x] = ++nb;
        for (; q[tp] != x; --tp) bel[q[tp]] = nb;
        --tp;
    }
}
EDGE *last2[N * 40];
int deg[N * 40];
inline void topu() {
    int head = 1, tail = 0;
    for (int i = 1; i <= nb; ++i)
        if (deg[i] == 0)
            q[++tail] = i;
    while (head <= tail) {
        int x = q[head++];
        for (EDGE *ei = last2[x]; ei; ei = ei->las)
            if (!--deg[ei->to])
                q[++tail] = ei->to;
    }
}
int re[N * 40];
inline void two_sat() {
    for (int i = 1; i <= num; ++i)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= num; ++i) {
        int x = bel[i];
        for (EDGE *ei = last[i]; ei; ei = ei->las) {
            int y = bel[ei->to];
            if (x != y)
                link(x, y, last2), deg[y]++;
        }
    }
    topu();
    for (int i = 1; i <= nb; ++i) re[q[i]] = i;
    for (int i = 1; i <= n; ++i)
        if (id[i][0] && id[i][1]) {
            int c = re[bel[id[i][0]]] > re[bel[id[i][1]]];
            int b = its[i][c];
            mxL[b] = max(mxL[b], L[i][c]);
            mnR[b] = min(mnR[b], R[i][c]);
        }
}
bool solve(int K) {
    int mxl = 0, mnr = INF, mxd = 0, mnu = INF;
    for (int i = 1; i <= n; ++i)
        if (!did[i]) {
            mxl = max(mxl, s[i].l);
            mnr = min(mnr, s[i].r);
            mxd = max(mxd, s[i].d);
            mnu = min(mnu, s[i].u);
        }
    if (K == 1) {
        if (mxl <= mnr && mxd <= mnu) {
            ans[K] = { mxl, mxd };
            return 1;
        }
        return 0;
    }
    put(K, mxl, mxd);
    if (solve(K - 1))
        return 1;
    take(K);
    put(K, mxl, mnu);
    if (solve(K - 1))
        return 1;
    take(K);
    put(K, mnr, mxd);
    if (solve(K - 1))
        return 1;
    take(K);
    put(K, mnr, mnu);
    if (solve(K - 1))
        return 1;
    take(K);
    if (K <= 3)
        return 0;
    for (int i = 1; i <= n; ++i) {
        int cnt = in(mxl, mxd, s[i]) + in(mxl, mnu, s[i]) + in(mnr, mxd, s[i]) + in(mnr, mnu, s[i]);
        if (cnt >= 2)
            did[i] = K;
        sc[i] = s[i];
    }
    np = 0;
    for (int i = 1; i <= n; ++i) {
        if (did[i])
            continue;
        if (s[i].l >= mnr)
            p[++np] = &sc[i].l;
        else
            sc[i].l = 0;
        if (s[i].r <= mxl)
            p[++np] = &sc[i].r;
        else
            sc[i].r = 0;
    }
    sort(p + 1, p + np + 1, cmpp);
    for (int i = 1, last = -1; i <= np; ++i) {
        if (last != *p[i])
            ++nc, last = *p[i];
        *p[i] = nc;
    }
    np = 0;
    for (int i = 1; i <= n; ++i) {
        if (did[i])
            continue;
        if (s[i].d >= mnu)
            p[++np] = &sc[i].d;
        else
            sc[i].d = 0;
        if (s[i].u <= mxd)
            p[++np] = &sc[i].u;
        else
            sc[i].u = 0;
    }
    sort(p + 1, p + np + 1, cmpp);
    for (int i = 1, last = -1; i <= np; ++i) {
        if (last != *p[i])
            ++nr, last = *p[i];
        *p[i] = nr;
    }
    for (int i = 0; i < 4; ++i) mxL[i] = 0, mnR[i] = INF;
    for (int i = 1; i <= n; ++i) {
        if (did[i])
            continue;
        id[i][0] = ++num, id[i][1] = ++num;
        if (in(mxl, mxd, s[i])) {
            ran[0][++cnt[0]] = { L[i][0] = sc[i].d, R[i][0] = nr, i, 0 };
            ran[2][++cnt[2]] = { L[i][1] = sc[i].l, R[i][1] = nc, i, 1 };
            its[i][0] = 0, its[i][1] = 2;
        } else if (in(mxl, mnu, s[i])) {
            ran[0][++cnt[0]] = { L[i][0] = 1, R[i][0] = sc[i].u, i, 0 };
            ran[3][++cnt[3]] = { L[i][1] = sc[i].l, R[i][1] = nc, i, 1 };
            its[i][0] = 0, its[i][1] = 3;
        } else if (in(mnr, mxd, s[i])) {
            ran[1][++cnt[1]] = { L[i][0] = sc[i].d, R[i][0] = nr, i, 0 };
            ran[2][++cnt[2]] = { L[i][1] = 1, R[i][1] = sc[i].r, i, 1 };
            its[i][0] = 1, its[i][1] = 2;
        } else if (in(mnr, mnu, s[i])) {
            ran[1][++cnt[1]] = { L[i][0] = 1, R[i][0] = sc[i].u, i, 0 };
            ran[3][++cnt[3]] = { L[i][1] = 1, R[i][1] = sc[i].r, i, 1 };
            its[i][0] = 1, its[i][1] = 3;
        } else {
            if (s[i].l <= mnr && s[i].r >= mxl) {
                ran[0][++cnt[0]] = { L[i][0] = sc[i].d, R[i][0] = sc[i].u, i, 0 };
                ran[1][++cnt[1]] = { L[i][1] = sc[i].d, R[i][1] = sc[i].u, i, 1 };
                its[i][0] = 0, its[i][1] = 1;
            } else if (s[i].d <= mnu && s[i].u >= mxd) {
                ran[2][++cnt[2]] = { L[i][0] = sc[i].l, R[i][0] = sc[i].r, i, 0 };
                ran[3][++cnt[3]] = { L[i][1] = sc[i].l, R[i][1] = sc[i].r, i, 1 };
                its[i][0] = 2, its[i][1] = 3;
            } else {
                id[i][0] = id[i][1] = 0;
                num -= 2;
                if (s[i].l <= mxl && mxl <= s[i].r)
                    mxL[0] = max(mxL[0], sc[i].d), mnR[0] = min(mnR[0], sc[i].u);
                else if (s[i].l <= mnr && mnr <= s[i].r)
                    mxL[1] = max(mxL[1], sc[i].d), mnR[1] = min(mnR[1], sc[i].u);
                else if (s[i].d <= mxd && mxd <= s[i].u)
                    mxL[2] = max(mxL[2], sc[i].l), mnR[2] = min(mnR[2], sc[i].r);
                else if (s[i].d <= mnu && mnu <= s[i].u)
                    mxL[3] = max(mxL[3], sc[i].l), mnR[3] = min(mnR[3], sc[i].r);
            }
        }
    }
    for (int i = 0; i < 4; ++i) {
        int nrc = i < 2 ? nr : nc;
        build(t[i << 1], 1, 1, nrc), build(t[i << 1 | 1], 1, 1, nrc);
        id[n + i + 1][0] = ++num, id[n + i + 1][1] = ++num;
        its[n + i + 1][0] = i;
        link(id[n + i + 1][0], id[n + i + 1][1]);
        ran[i][++cnt[i]] = { L[n + i + 1][0] = mxL[i], R[n + i + 1][0] = mnR[i], n + i + 1, 0 };
        for (int j = 1; j <= cnt[i]; ++j) {
            Range a = ran[i][j];
            lk_to(t[i << 1], 1, 1, nrc, a.r, id[a.id][a._01]);
            lk_to(t[i << 1 | 1], 1, 1, nrc, a.l, id[a.id][a._01]);
        }
        for (int j = 1; j <= cnt[i]; ++j) {
            Range a = ran[i][j];
            if (a.l > 1)
                lk_from(t[i << 1], 1, 1, nrc, 1, a.l - 1, id[a.id][!a._01]);
            if (a.r < nrc)
                lk_from(t[i << 1 | 1], 1, 1, nrc, a.r + 1, nrc, id[a.id][!a._01]);
        }
    }
    two_sat();
    int l0, l1, l2, l3;
    for (int i = 1; i <= n; ++i) {
        if (mxL[0] == sc[i].d)
            l0 = s[i].d;
        if (mxL[1] == sc[i].d)
            l1 = s[i].d;
        if (mxL[2] == sc[i].l)
            l2 = s[i].l;
        if (mxL[3] == sc[i].l)
            l3 = s[i].l;
    }
    ans[1] = { mxl, l0 };
    ans[2] = { mnr, l1 };
    ans[3] = { l2, mxd };
    ans[4] = { l3, mnu };
    return 1;
}
int main() {
    //	freopen("in.txt","r",stdin);
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; ++i) scanf("%d%d%d%d", &s[i].l, &s[i].d, &s[i].r, &s[i].u);
    solve(K);
    for (int i = 1; i <= K; ++i) printf("%d %d\n", ans[i].x, ans[i].y);
    for (int i = 1; i <= n; ++i) {
        bool bz = 0;
        for (int j = 1; j <= K; ++j) bz |= in(ans[j].x, ans[j].y, s[i]);
        if (bz == 0) {
            printf("WA:%d\n", i);
            return 0;
        }
    }
    return 0;
}

Day3T1

比赛时搞了个 $O(n^2)$ 的DP，不知怎的就是没过（话说我还在本地对拍了很久！）
可惜当时我竟然没有发现那是一棵树。

对于某个位置 $i$ ，找到左边第一个比它高的位置 $l_i$ ，右边同理 $r_i$ 。
以 $i$ 的高度为底， $[l_i,r_i]$ 为横坐标区间建矩形。
将这个图的矩形建出来之后，就会发现一些矩形之间存在包含关系。以这种包含关系可以建出一棵树。这棵树和笛卡尔树类似，不同点在于一些高度相同的点要缩起来（就是矩形完全重合的点）。（不清楚不缩这些点会不会挂）
对于一个星星，可以发现包含它的矩形对应这树上的一条祖先后代链。
问题转化成了，选择尽量多祖先后代链，使得它们之间不相交。
经典问题，简单树形 $DP$ ，用线段树合并优化。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 200010
#define ll long long
#define INF 1000000000ll
int n, m;
int h[N];
int st[N], top;
int id[N], num;
int ch[N][2];
struct EDGE {
    int to, v;
    EDGE *las;
} e[N + N + N];
int ne;
EDGE *last[N], *ini[N], *lis[N];
int fa[N];
void init(int x, int f) {
    if (!x)
        return;
    if (h[x] == h[f])
        id[x] = id[f];
    else {
        id[x] = ++num;
        fa[num] = id[f];
    }
    st[++top] = x;
    for (EDGE *ei = ini[x]; ei; ei = ei->las) {
        int l = 1, r = top, res = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (h[st[mid]] < ei->to)
                r = (res = mid) - 1;
            else
                l = mid + 1;
        }
        int y = id[st[res]];
        e[ne] = { y, ei->v, lis[id[x]] };
        lis[id[x]] = e + ne++;
        //		printf("(%d,%d,%d):%d->%d\n",x,ei->to,ei->v,id[x],y);
    }
    init(ch[x][0], x);
    init(ch[x][1], x);
    --top;
}
struct Node {
    Node *l, *r;
    ll mx, tag;
    inline void pd() { l->mx += tag, l->tag += tag, r->mx += tag, r->tag += tag, tag = 0; }
} d[N * 100], *null, *rt[N];
int cnt;
Node *newnode() { return &(d[++cnt] = { null, null, -INF * INF, 0 }); }
int dep[N];
ll res, g[N];
void remove(Node *&t, int l, int r, int st) {
    if (t == null)
        return;
    if (st <= l) {
        res = max(res, t->mx);
        t = null;
        return;
    }
    t->pd();
    int mid = l + r >> 1;
    if (st <= mid)
        remove(t->l, l, mid, st);
    remove(t->r, mid + 1, r, st);
    t->mx = max(t->l->mx, t->r->mx);
}
void insert(Node *&t, int l, int r, int x, ll c) {
    if (t == null)
        t = newnode();
    if (l == r) {
        t->mx = max(t->mx, c);
        return;
    }
    t->pd();
    int mid = l + r >> 1;
    if (x <= mid)
        insert(t->l, l, mid, x, c);
    else
        insert(t->r, mid + 1, r, x, c);
    t->mx = max(t->l->mx, t->r->mx);
}
void add(Node *&t, int l, int r, int st, int en, ll c) {
    if (t == null)
        t = newnode();
    if (st <= l && r <= en) {
        t->mx += c;
        t->tag += c;
        return;
    }
    t->pd();
    int mid = l + r >> 1;
    if (st <= mid)
        add(t->l, l, mid, st, en, c);
    if (mid < en)
        add(t->r, mid + 1, r, st, en, c);
    t->mx = max(t->l->mx, t->r->mx);
}
Node *merge(Node *a, Node *b, int l, int r) {
    if (a == null)
        return b;
    if (b == null)
        return a;
    if (l == r) {
        a->mx = max(a->mx, b->mx);
        a->tag = 0;
        return a;
    }
    a->pd(), b->pd();
    int mid = l + r >> 1;
    a->l = merge(a->l, b->l, l, mid);
    a->r = merge(a->r, b->r, mid + 1, r);
    a->mx = max(a->l->mx, a->r->mx);
    return a;
}
ll s[N];
void dp(int x) {
    rt[x] = newnode();
    dep[x] = dep[fa[x]] + 1;
    ll sum = 0;
    for (EDGE *ei = last[x]; ei; ei = ei->las) {
        dp(ei->to);
        s[x] += s[ei->to];
        res = -INF * INF;
        remove(rt[ei->to], 1, n, dep[ei->to]);
        sum += g[ei->to] = res;
        assert(res >= 0);
    }
    insert(rt[x], 1, n, dep[x], sum);
    for (EDGE *ei = lis[x]; ei; ei = ei->las) s[x] += ei->v, insert(rt[x], 1, n, dep[ei->to], sum + ei->v);
    for (EDGE *ei = last[x]; ei; ei = ei->las) {
        add(rt[ei->to], 1, n, 1, dep[x], sum - g[ei->to]);
        rt[x] = merge(rt[x], rt[ei->to], 1, n);
    }
}
int main() {
    //	freopen("in.txt","r",stdin);
    //	freopen("out.txt","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    h[0] = h[n + 1] = INF;
    scanf("%d", &m);
    ll sum = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c), sum += c;
        e[ne] = { y, c, ini[x] };
        ini[x] = e + ne++;
    }
    st[top = 1] = 0;
    for (int i = 1; i <= n; ++i) {
        if (h[st[top]] > h[i]) {
            ch[st[top]][1] = i;
            st[++top] = i;
        } else {
            while (top && h[st[top]] <= h[i]) --top;
            int x = st[top + 1], y = st[top];
            ch[i][0] = x;
            ch[y][1] = i;
            st[++top] = i;
        }
    }
    top = 0;
    init(ch[0][1], 0);
    for (int i = 2; i <= num; ++i) {
        e[ne] = { i, 0, last[fa[i]] };
        last[fa[i]] = e + ne++;
    }
    null = d;
    *null = { null, null, -INF * INF, 0 };
    //	for (int i=1;i<=n;++i)
    //		printf("%d ",id[i]);
    dp(1);
    printf("%lld\n", sum - rt[1]->mx);
    return 0;
}

Day4T1

比赛时有思路，但是在一个地方卡了太久。后来LL讲课的时候网络挂了，导致没有听清楚，那个问题困扰了我几天。
在想清楚那个问题之前，我打了CC的做法，打出来之后发现空间爆掉了，卡了一个早上都没有办法。
于是就装作我AC了……
后来想清楚了那个问题，于是在极短的时间内将这题切了。

最显而易见的做法就是点分治：
如果选根，就 $O(n)$ 地暴力出选根的答案。
如果不选根，就要将和根颜色相同的东西打标记。还有，如果某个颜色存在两个点分别在根的两棵子树内，那么这个颜色也要被标记。
接下来就是一个重要的问题，出现了连锁反应怎么处理？
其实可以先不处理。在后面假如定了某个根，先往下搜一遍将所有的被标记的点找出来，用bfs依次将这些点的子树全部清掉（还要打另一个标记表示某个点是否被清掉）。清掉的时候，将和这些点颜色相同的丢进队列里，表示它们以及它们的子树也被清掉。
这样是O(n)的。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 200010
#define ll long long
#define INF 1000000000ll
int n, m;
int h[N];
int st[N], top;
int id[N], num;
int ch[N][2];
struct EDGE {
    int to, v;
    EDGE *las;
} e[N + N + N];
int ne;
EDGE *last[N], *ini[N], *lis[N];
int fa[N];
void init(int x, int f) {
    if (!x)
        return;
    if (h[x] == h[f])
        id[x] = id[f];
    else {
        id[x] = ++num;
        fa[num] = id[f];
    }
    st[++top] = x;
    for (EDGE *ei = ini[x]; ei; ei = ei->las) {
        int l = 1, r = top, res = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (h[st[mid]] < ei->to)
                r = (res = mid) - 1;
            else
                l = mid + 1;
        }
        int y = id[st[res]];
        e[ne] = { y, ei->v, lis[id[x]] };
        lis[id[x]] = e + ne++;
        //		printf("(%d,%d,%d):%d->%d\n",x,ei->to,ei->v,id[x],y);
    }
    init(ch[x][0], x);
    init(ch[x][1], x);
    --top;
}
struct Node {
    Node *l, *r;
    ll mx, tag;
    inline void pd() { l->mx += tag, l->tag += tag, r->mx += tag, r->tag += tag, tag = 0; }
} d[N * 100], *null, *rt[N];
int cnt;
Node *newnode() { return &(d[++cnt] = { null, null, -INF * INF, 0 }); }
int dep[N];
ll res, g[N];
void remove(Node *&t, int l, int r, int st) {
    if (t == null)
        return;
    if (st <= l) {
        res = max(res, t->mx);
        t = null;
        return;
    }
    t->pd();
    int mid = l + r >> 1;
    if (st <= mid)
        remove(t->l, l, mid, st);
    remove(t->r, mid + 1, r, st);
    t->mx = max(t->l->mx, t->r->mx);
}
void insert(Node *&t, int l, int r, int x, ll c) {
    if (t == null)
        t = newnode();
    if (l == r) {
        t->mx = max(t->mx, c);
        return;
    }
    t->pd();
    int mid = l + r >> 1;
    if (x <= mid)
        insert(t->l, l, mid, x, c);
    else
        insert(t->r, mid + 1, r, x, c);
    t->mx = max(t->l->mx, t->r->mx);
}
void add(Node *&t, int l, int r, int st, int en, ll c) {
    if (t == null)
        t = newnode();
    if (st <= l && r <= en) {
        t->mx += c;
        t->tag += c;
        return;
    }
    t->pd();
    int mid = l + r >> 1;
    if (st <= mid)
        add(t->l, l, mid, st, en, c);
    if (mid < en)
        add(t->r, mid + 1, r, st, en, c);
    t->mx = max(t->l->mx, t->r->mx);
}
Node *merge(Node *a, Node *b, int l, int r) {
    if (a == null)
        return b;
    if (b == null)
        return a;
    if (l == r) {
        a->mx = max(a->mx, b->mx);
        a->tag = 0;
        return a;
    }
    a->pd(), b->pd();
    int mid = l + r >> 1;
    a->l = merge(a->l, b->l, l, mid);
    a->r = merge(a->r, b->r, mid + 1, r);
    a->mx = max(a->l->mx, a->r->mx);
    return a;
}
ll s[N];
void dp(int x) {
    rt[x] = newnode();
    dep[x] = dep[fa[x]] + 1;
    ll sum = 0;
    for (EDGE *ei = last[x]; ei; ei = ei->las) {
        dp(ei->to);
        s[x] += s[ei->to];
        res = -INF * INF;
        remove(rt[ei->to], 1, n, dep[ei->to]);
        sum += g[ei->to] = res;
        assert(res >= 0);
    }
    insert(rt[x], 1, n, dep[x], sum);
    for (EDGE *ei = lis[x]; ei; ei = ei->las) s[x] += ei->v, insert(rt[x], 1, n, dep[ei->to], sum + ei->v);
    for (EDGE *ei = last[x]; ei; ei = ei->las) {
        add(rt[ei->to], 1, n, 1, dep[x], sum - g[ei->to]);
        rt[x] = merge(rt[x], rt[ei->to], 1, n);
    }
}
int main() {
    //	freopen("in.txt","r",stdin);
    //	freopen("out.txt","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    h[0] = h[n + 1] = INF;
    scanf("%d", &m);
    ll sum = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c), sum += c;
        e[ne] = { y, c, ini[x] };
        ini[x] = e + ne++;
    }
    st[top = 1] = 0;
    for (int i = 1; i <= n; ++i) {
        if (h[st[top]] > h[i]) {
            ch[st[top]][1] = i;
            st[++top] = i;
        } else {
            while (top && h[st[top]] <= h[i]) --top;
            int x = st[top + 1], y = st[top];
            ch[i][0] = x;
            ch[y][1] = i;
            st[++top] = i;
        }
    }
    top = 0;
    init(ch[0][1], 0);
    for (int i = 2; i <= num; ++i) {
        e[ne] = { i, 0, last[fa[i]] };
        last[fa[i]] = e + ne++;
    }
    null = d;
    *null = { null, null, -INF * INF, 0 };
    //	for (int i=1;i<=n;++i)
    //		printf("%d ",id[i]);
    dp(1);
    printf("%lld\n", sum - rt[1]->mx);
    return 0;
}

顺便祭奠一下我那可怜的空间超限程序。
大概就是通过线段树优化连边，如果选 $a$ 的前提是选 $b$ ，那么连边 $(b,a)$ （类似 $2-SAT$ ）。
然后跑 $tarjan$ 。
我是通过线段树合并的方式来优化连边的，而CC是用树链剖分来优化连边，看起来我还比他少个 $log$ 。可是为什么就是过不去呢！

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <bitset>
#define N 200010
#define ll long long
int n,K;
int c[N];
struct EDGE{
	int to;
	EDGE *las;
};
int ne;
EDGE *last[N];
#define rev(ei) (e+(int((ei)-e)^1))
int fa[N],siz[N],hs[N],dep[N],top[N];
void dfs1(int x){
	siz[x]=1;
	dep[x]=dep[fa[x]]+1;
	for (EDGE *ei=last[x];ei;ei=ei->las)
		if (ei->to!=fa[x]){
			fa[ei->to]=x;
			dfs1(ei->to);
			siz[x]+=siz[ei->to];
			if (siz[ei->to]>siz[hs[x]])
				hs[x]=ei->to;
		}
}
void dfs2(int x,int t){
	top[x]=t;
	if (hs[x])
		dfs2(hs[x],t);
	for (EDGE *ei=last[x];ei;ei=ei->las)
		if (ei->to!=fa[x] && ei->to!=hs[x])
			dfs2(ei->to,ei->to);
}
int LCA(int u,int v){
	for (;top[u]!=top[v];u=fa[top[u]])
		if (dep[top[u]]<dep[top[v]])
			swap(u,v);
	return dep[u]<dep[v]?u:v;
}

int num;
EDGE *lst[N*30];
inline void lk(int u,int v,EDGE *la[]=lst){
	EDGE *nw=new EDGE;
	*nw={v,la[u]};
	la[u]=nw;
//	ne++;
}
struct Node{
	Node *l,*r;
	int s,id;
} *null,*root[N];
int cnt;
inline Node *newnode(){/*++cnt;*/Node *nw=new Node;*nw={null,null,0};return nw;}
void insert(Node *&t,int l,int r,int x,int c){
	if (t==null)
		t=newnode();
	t->s+=c;
	if (l==r)
		return;
	int mid=l+r>>1;
	if (x<=mid)
		insert(t->l,l,mid,x,c);
	else
		insert(t->r,mid+1,r,x,c);
}
Node *merge(Node *a,Node *b){
	if (a==null)
		return b;
	if (b==null)
		return a;
	int s;
	Node *l,*r;
	s=a->s+b->s;
	l=merge(a->l,b->l);
	r=merge(a->r,b->r);
	if (!(l==null && r==null && s==0)){
		Node *nw=newnode();
		*nw={l,r,s};
		return nw;
	}
	return null;
}
int fir[N],pre[N];
void init1(int x){
	insert(root[x],1,K,c[x],1);
	if (pre[c[x]]){
		int lca=LCA(pre[c[x]],x);
		insert(root[lca],1,K,c[x],-1);
	}
	else
		fir[c[x]]=x;
	pre[c[x]]=x;
	for (EDGE *ei=last[x];ei;ei=ei->las)
		if (ei->to!=fa[x])
			init1(ei->to);
}
void init2(int x){
	for (EDGE *ei=last[x];ei;ei=ei->las)
		if (ei->to!=fa[x])
			init2(ei->to);
	for (EDGE *ei=last[x];ei;ei=ei->las)
		if (ei->to!=fa[x])
			root[x]=merge(root[x],root[ei->to]);
}
void dfs(Node *t,int l,int r){
	if (t==null || t->s==0 || t->id)
		return;
	if (l==r){
		t->id=l;
		return;
	}
	int mid=l+r>>1;
	dfs(t->l,l,mid),dfs(t->r,mid+1,r);
	t->id=++num;
	if (t->l->id)
		lk(t->id,t->l->id);
	if (t->r->id)
		lk(t->id,t->r->id);
}
vector<int> s,du;
vector<EDGE*> last2;
int num2;
int bel[N*30];
int dfn[N*30],low[N*30],nowdfn;
vector<int> q;
int tp;
void tarjan(int x){
	dfn[x]=low[x]=++nowdfn;
	q.push_back(x),++tp;
	for (EDGE *ei=lst[x];ei;ei=ei->las){
		if (!dfn[ei->to])
			tarjan(ei->to),low[x]=min(low[x],low[ei->to]);
		else if (!bel[ei->to])
			low[x]=min(low[x],dfn[ei->to]);
	}
	if (dfn[x]==low[x]){
		num2++;
		bel[x]=num2;
		int siz=(x<=K);
		for (;q[tp]!=x;--tp){
			bel[q[tp]]=num2;
			siz+=(q[tp]<=K);
			q.pop_back();
		}
		--tp;
		q.pop_back();
		s.push_back(siz);
		du.push_back(0);
		last2.push_back(NULL);
	}
}
inline void bfs(){
	int head=1,tail=0;
	for (int i=1;i<=num2;++i)
		if (du[i]==0 && s[i]==0)
			q.push_back(i),++tail;
	while (head<=tail){
		int x=q[head++];
		for (EDGE *ei=last2[x];ei;ei=ei->las){
			--du[ei->to];
			if (du[ei->to]==0 && s[ei->to]==0)
				q.push_back(ei->to),++tail;
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&K);
	for (int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		lk(u,v,last);
		lk(v,u,last);
	}
	dfs1(1),dfs2(1,1);
	for (int i=1;i<=n;++i)
		scanf("%d",&c[i]);
	null=new Node;
	*null={null,null,0};
	num=cnt=K;
	for (int i=1;i<=n;++i)
		root[i]=null;
	init1(1);
	for (int i=1;i<=K;++i){
		int lca=LCA(fir[i],pre[i]);
		if (fa[lca])
			insert(root[fa[lca]],1,K,i,-1);
	}
	init2(1);
	for (int i=1;i<=n;++i)
		if (root[i]!=null){
			dfs(root[i],1,K);
			lk(c[i],root[i]->id);
		}
	du.push_back(0),s.push_back(0);
	q.push_back(0);
	for (int i=1;i<=num;++i)
		if (!dfn[i])
			tarjan(i);
	for (int i=1;i<=num;++i){
		int x=bel[i];
		for (EDGE *ei=lst[i];ei;ei=ei->las,delete lst[i],lst[i]=ei){
			int y=bel[ei->to];
			if (x!=y){
				du[y]++;
				EDGE *nw=new EDGE;
				*nw={y,last2[x]};
				last2[x]=nw;
//				ne++;
			}
		}
	}
	bfs();
	int ans=K;
	for (int i=1;i<=num2;++i)
		if (du[i]==0 && s[i])
			ans=min(ans,s[i]);
//	printf("num=%d\n",num);
	printf("%d\n",ans-1);
	return 0;
}

Day4T3

比赛时基本上没有想这道题吧……
实际上这是一道，思想上怎样都很难被想到，但是很好实现的一道题。

考虑结果是将若干段区间拼起来。
设 $f_i$ 表示 $[1,R_i]$ 都被治愈的情况（注意，这时候不考虑后面的区间，想象 $R_i$ 是右边界而不是 $n$ 是右边界）
考虑从 $f_i$ 转移至 $f_j$ ，条件是 $R_i-L_j+1\geq |T_i-T_j|$
可以理解成将两个区间焊接起来，中间由于时间关系会被侵蚀一部分。由于我们假定 $R_j$ 是右边界，所以 $[1,R_j]$ 这段区间相当于完全治愈了。
这是一个非常妙的像是AGC的DP。
然后便可以发现，这个转移是个最短路的形式，并且是可以用线段树优化的。
注意这和线段树优化连边不一样：
取出 $f$ 值最小的堆顶之后，通过线段树快速地找到没有被转移到的点，转移了之后将它加入堆中，并且在线段树中删除它。由于只需要最小的去转移它，所以它不会被转移到第二遍。
（话说网上各种题解说线段树优化连边真是毒死我了）

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define M 100010
#define INF 2147483647
#define ll long long
int n, m;
struct Treat {
    int l, r, t, c;
} d[M];
inline bool cmpd(Treat a, Treat b) { return a.t < b.t; }
ll f[M];
ll mn0[M * 4], mn1[M * 4];
void build(int k, int l, int r) {
    if (l == r) {
        mn0[k] = d[l].l - d[l].t;
        mn1[k] = d[l].l + d[l].t;
        return;
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    mn0[k] = min(mn0[k << 1], mn0[k << 1 | 1]);
    mn1[k] = min(mn1[k << 1], mn1[k << 1 | 1]);
}
void erase(int k, int l, int r, int x) {
    if (l == r) {
        mn0[k] = mn1[k] = INF;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        erase(k << 1, l, mid, x);
    else
        erase(k << 1 | 1, mid + 1, r, x);
    mn0[k] = min(mn0[k << 1], mn0[k << 1 | 1]);
    mn1[k] = min(mn1[k << 1], mn1[k << 1 | 1]);
}
int h[M], nh;
inline bool cmph(int son, int fa) { return f[son] > f[fa]; }
void find0(int k, int l, int r, int st, int en, int v, ll c) {
    if (mn0[k] > v)
        return;
    if (l == r) {
        f[l] = c + d[l].c;
        h[nh++] = l;
        push_heap(h, h + nh, cmph);
        mn0[k] = mn1[k] = INF;
        return;
    }
    int mid = l + r >> 1;
    if (st <= mid)
        find0(k << 1, l, mid, st, en, v, c);
    if (mid < en)
        find0(k << 1 | 1, mid + 1, r, st, en, v, c);
    mn0[k] = min(mn0[k << 1], mn0[k << 1 | 1]);
    mn1[k] = min(mn1[k << 1], mn1[k << 1 | 1]);
}
void find1(int k, int l, int r, int st, int en, int v, ll c) {
    if (mn1[k] > v)
        return;
    if (l == r) {
        f[l] = c + d[l].c;
        h[nh++] = l;
        push_heap(h, h + nh, cmph);
        mn0[k] = mn1[k] = INF;
        return;
    }
    int mid = l + r >> 1;
    if (st <= mid)
        find1(k << 1, l, mid, st, en, v, c);
    if (mid < en)
        find1(k << 1 | 1, mid + 1, r, st, en, v, c);
    mn0[k] = min(mn0[k << 1], mn0[k << 1 | 1]);
    mn1[k] = min(mn1[k << 1], mn1[k << 1 | 1]);
}
int main() {
    //	freopen("in.txt","r",stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) scanf("%d%d%d%d", &d[i].t, &d[i].l, &d[i].r, &d[i].c);
    sort(d + 1, d + m + 1, cmpd);
    build(1, 1, m);
    memset(f, 127, sizeof f);
    for (int i = 1; i <= m; ++i)
        if (d[i].l == 1) {
            erase(1, 1, m, i);
            f[i] = d[i].c;
            h[nh++] = i;
        }
    make_heap(h, h + nh, cmph);
    while (nh) {
        int x = h[0];
        pop_heap(h, h + nh--, cmph);
        find0(1, 1, m, 1, x, d[x].r - d[x].t + 1, f[x]);
        if (x < m)
            find1(1, 1, m, x + 1, m, d[x].r + d[x].t + 1, f[x]);
    }
    ll ans = 0x7f7f7f7f7f7f7f7f;
    for (int i = 1; i <= m; ++i)
        if (d[i].r == n)
            ans = min(ans, f[i]);
    printf("%lld\n", ans == 0x7f7f7f7f7f7f7f7f ? -1 : ans);
    return 0;
}

JOISC2020总结&题解

Day1T1

Day1T2

Day3T1

Day4T1

Day4T3

Android view更改背景资源与padding消失的问题解决办法

PHP下打开phpMyAdmin出现403错误的问题解决方法

总结AngularJS开发者最常犯的十个错误

浅谈springMVC接收前端json数据的总结

javascript 继承学习心得总结

linux常用命令总结（含选项参数）

Spring boot 总结之跨域处理cors的方法

基于SpringMVC接受JSON参数详解及常见错误总结

html5跨域通讯之postMessage的用法总结

java程序设计报告总结（简单游戏代码编写方法）