grade

好菜啊,不会 T2。

T4 会 60 结果暴力假了。

achen

n 个节点,i 号节点 (i \leq n - 2)i + 1, i + 2 之间有双向边。n - 1n 节点有双向边。

ab 的哈密顿路径个数。


结论好题。

考虑从 1 出发,走完 [1 , x] 内的每个点的方案数 f(x)

如果走一步,那么就是 f(x + 1)

否则走两步,发现走法是唯一的。只能向右走两步,左走一步,右走两步,是 f(x + 3)

所以就有 f(x) = f(x- 1) + f(x - 3)

a 出发到 b。首先 [1, a][b, n] 这一部分均只有一种走法。

然后走完这两部分会从 a + 1 出发走到 b - 1,答案就是 f(b - 1 - (a + 1))

注意特判 a = 1b = n 的情况,在这种情况下,是从 a 出发或从 b 出发。

void solve() {
    int n, a, b;
    IO::read(n), IO::read(a), IO::read(b);
    if (a > b) swap(a, b);
    if (n == 1) return puts("1"), void();
    if (a != 1) a++; if (b != n) b--;
    if (b - a < 0) return puts("0"), void();
    printf("%d\n", f[b - a]);
}

int main() {
    int t; IO::read(t);
    f[0] = f[1] = f[2] = 1, f[3] = 2;
    rep(i, 4, MAXN - 1) f[i] = f[i - 1] + f[i - 3] > P ? f[i - 1] + f[i - 3] - P : f[i - 1] + f[i - 3];
    while (t--) solve();
    return 0;
}

tree

一棵 n 个节点的树,每个节点有颜色。选一个点作为根,一些点,满足这些点取遍所有颜色,并且这些点的 LCA 在该根的意义下深度最深。输出深度。

n \leq 10^6


一些满足特殊性质的点的 LCA \Leftrightarrow 一个点的子树满足某些性质。

即,一个点的子树取遍所有点。

考虑根与该点的关系(在 1 为根的意义下)。只要确定了关系,那么子树也能确定。这提醒我们预处理出某个点的子树(子树补集)是否合法。

根在该点外

即,在新根意义下,该点子树与 1 根意义下的子树一样。

考虑经典问题:子树颜色个数。打标记,并每次减少与 dfs 序上的前驱的 LCA 的标记。

如果颜色个数是 m 就合法。

根在该点内

新根意义下的子树是该点子树的补集加上自己。

如果新根不合法,那么一定是该点的所有子树 完全 涵盖了某个颜色。同样对每个颜色,处理出该有颜色所有点的 LCA。容易知道该 LCA 到根的链上每个点都完全覆盖。

如果该点存在要给子树没有完全覆盖某个颜色,那么就可以在该子树内找一个点当新根。

合法性判断完毕,接下来考虑求出答案。

up and down,求出子树 内/外 距离一个点最远的点。

注意在 up 的时候,因为 \max 运算没有逆运算,只能在 down 时提前预处理出一个 down 的次大值,并且判断一下最大值是在哪个点取到。

时间复杂度 O(n \log n),瓶颈在 LCA。

namespace Tree {
    int ecnt, head[MAXN];
    struct Edge { int nxt, to; } e[MAXN << 1];
    void add(int u, int v) { e[++ecnt].nxt = head[u], e[ecnt].to = v, head[u] = ecnt; }

    int dfsclock;
    struct Vertix { int dfn, sz, son, top, col, mxdep, mxdepnum, mxdep2, fa, dep, up_mxdep, cover_all, col_num; } vtx[MAXN];

    void getDown(int u, int fr) {
        vtx[u].dfn = ++dfsclock, vtx[u].sz = 1, vtx[u].fa = fr, vtx[u].dep = vtx[fr].dep + 1;
        vtx[u].mxdep = 1;
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == fr) continue;
            getDown(v, u);
            if (vtx[vtx[u].son].sz < vtx[v].sz) vtx[u].son = v;
            if (vtx[v].mxdep + 1 > vtx[u].mxdep) {
                swap(vtx[u].mxdep, vtx[u].mxdep2), vtx[u].mxdep = vtx[v].mxdep + 1, vtx[u].mxdepnum = v;
            } else if (vtx[v].mxdep + 1 > vtx[u].mxdep2) vtx[u].mxdep2 = vtx[v].mxdep + 1;
            vtx[u].sz += vtx[v].sz;
        }
    }
    void getTop(int u, int top) {
        vtx[u].top = top;
        if (vtx[u].son) getTop(vtx[u].son, top);
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == vtx[u].fa || v == vtx[u].son) continue;
            getTop(v, v);
        }
    }
    int LCA(int u, int v) {
        while (vtx[u].top != vtx[v].top) {
            if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v);
            u = vtx[vtx[u].top].fa;
        }
        return vtx[u].dep < vtx[v].dep ? u : v;
    }
    void getUp(int u, int fr) {
        vtx[u].up_mxdep = max(vtx[u].up_mxdep, 1);
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == fr) continue;
            vtx[v].up_mxdep = max(vtx[u].up_mxdep + 1, (vtx[u].mxdepnum == v ? vtx[u].mxdep2 : vtx[u].mxdep) + 1);
            getUp(v, u);
        }
    }
    void init() { getDown(1, 0), getTop(1, 1), getUp(1, 0); }
    void merge_data(int u, int fr) {
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == fr) continue;
            merge_data(v, u);
            vtx[u].cover_all |= vtx[v].cover_all; vtx[u].col_num += vtx[v].col_num;
        }
    }
    void get_ans(int u, int fr) {
        if (vtx[u].col_num == m)
            chkmax(ans, vtx[u].up_mxdep);
        for (int _ = head[u], v; _; _ = e[_].nxt) {
            v = e[_].to;
            if (v == fr) continue;
            get_ans(v, u);
            if (!vtx[v].cover_all) chkmax(ans, vtx[v].mxdep + 1);
        }
    }
}

int col_lca[MAXN];
vector<int> col[MAXM];

int main() {
    IO::read(n), IO::read(m);
    rep(i, 1, n) {
        int x; IO::read(x);
        Tree::vtx[i].col = x, col[x].push_back(i);
    }
    rep(i, 1, n - 1) {
        int u, v; IO::read(u), IO::read(v);
        Tree::add(u, v), Tree::add(v, u);
    }
    Tree::init();
    rep(i, 1, m) {
        sort(col[i].begin(), col[i].end(), [](const int& a, const int& b) { return Tree::vtx[a].dfn < Tree::vtx[b].dfn; });
        col_lca[i] = col[i][0], Tree::vtx[col[i][0]].col_num++;
        rep(idx, 1, col[i].size() - 1) {
            col_lca[i] = Tree::LCA(col_lca[i], col[i][idx]);
            int pre_lca = Tree::LCA(col[i][idx - 1], col[i][idx]);
            Tree::vtx[col[i][idx]].col_num++, Tree::vtx[pre_lca].col_num--;
        }
        Tree::vtx[col_lca[i]].cover_all = true;

    }
    Tree::merge_data(1, 0);
    Tree::get_ans(1, 0);
    printf("%d\n", ans);
    return 0;
}

esay

给出整数序列 A, |A| \leq 10^5, A_i \leq 10^9,求有多少个有序整数对 (l, r),满足:

  • \forall i \in [l, r]A_i 的值是一段连续的区间。

一个区间是合法的 \Leftrightarrow \max - \min - c = 0c 代表区间不同的数的个数。

容易发现对于任意区间 \max - \min - c 的最小值就是 0,这样我们可以维护最小值出现次数与最小值的值,来支持区间加的操作。

考虑枚举 r \rightarrow 1 \cdots n,观察 r \leftarrow r + 1 这个过程式子的变化。

大概会有一些后缀的 \max 会变大,\min 会变小。所以搞个队列(实际上是栈),维护一下每个后缀最值的连续段。每次加入一个就暴力看哪个 大/小。

然后 c 是,(pre, r]c 都会 +1pre 表示 r 的值上一次出现的位置。

式子是可以维护了,如何维护区间的特征值(\max - \min - c),直接搞个线段树维护一下值就好。

看起来复杂度非常不对,因为栈会进进出出很多次的样子。不过最坏情况下每个点也只会 进/出 至多一次,至多有 2n 次操作,所以复杂度是对的。

O(n \log n)

typedef long long ll;

const int MAXN = 1e5 + 10;

int n, arr[MAXN];
ll ans;

struct OrzSJX {
    #define mid ((l + r) >> 1)
    #define ls k << 1, l, mid
    #define rs k << 1 | 1, mid + 1, r
    struct Node { int mnval, cnt, tag; } t[MAXN << 2];
    void build(int k, int l, int r) {
        t[k].cnt = r - l + 1, t[k].mnval = 114514;
        if (l == r) return ;
        build(ls), build(rs);
    }
    void pushup(int k) {
        if (t[k << 1].mnval == t[k << 1 | 1].mnval) t[k].mnval = t[k << 1].mnval, t[k].cnt  = t[k << 1].cnt + t[k << 1 | 1].cnt;
        else if (t[k << 1].mnval < t[k << 1 | 1].mnval) t[k].mnval = t[k << 1].mnval, t[k].cnt = t[k << 1].cnt;
        else t[k].mnval = t[k << 1 | 1].mnval, t[k].cnt = t[k << 1 | 1].cnt;
    }
    void pushdown(int k) {
        t[k << 1].tag += t[k].tag, t[k << 1 | 1].tag += t[k].tag;
        t[k << 1].mnval += t[k].tag, t[k << 1 | 1].mnval += t[k].tag;
        t[k].tag = 0;
    }
    void add(int k, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr) return t[k].mnval += val, t[k].tag += val, void();
        pushdown(k);
        if (ql <= mid) add(ls, ql, qr, val);
        if (qr > mid) add(rs, ql, qr, val);
        pushup(k);
    }
    int query(int k, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return t[k].mnval == 0 ? t[k].cnt : 0;
        int ret = 0; pushdown(k);
        if (ql <= mid) ret += query(ls, ql, qr);
        if (qr > mid) ret += query(rs, ql, qr);
        return ret;
    }
} sgt;

int pre[MAXN];
map<int, int> pos;
int mn[MAXN], mx[MAXN], mntop, mxtop;

int main() {
    IO::read(n);
    sgt.build(1, 1, n);
    rep(i, 1, n) {
        IO::read(arr[i]);
        if (pos.count(arr[i])) pre[i] = pos[arr[i]];
        pos[arr[i]] = i;
    }
    rep(r, 1, n) {
        while (mxtop && arr[mx[mxtop]] < arr[r]) sgt.add(1, 1, n, mx[mxtop - 1] + 1, mx[mxtop], arr[r] - arr[mx[mxtop]]), mxtop--;
        while (mntop && arr[mn[mntop]] > arr[r]) sgt.add(1, 1, n, mn[mntop - 1] + 1, mn[mntop], arr[mn[mntop]] - arr[r]), mntop--;
        sgt.add(1, 1, n, pre[r] + 1, r, -1);
        mx[++mxtop] = r, mn[++mntop] = r;
        ans += sgt.t[1].cnt;
    }
    printf("%lld\n", ans);
    return 0;
}

原题是 CF526F(

总结

感觉完全不在状态,这场不行.jpg

肝 T4 太久了,T3 其实挺好做。

感觉以后不仅要看完所有题,还要想想所有题。

10-23 赛后题解
上一篇 «
10-19 赛后题解与复盘
» 下一篇