Visits: 309

USACO

2018 December Contest

Balance Beam

单调栈求一个上凸壳即可。

卡精度，要用 __int128。

const int N = 1e5 + 7;
int n;
__int128 a[N];
vi s(1, 0);

inline bool pd(int i, int j, int k) {
    return (a[j] - a[i]) * (k - i) <= (a[k] - a[i]) * (j - i);
}

int main() {
    rd(n);
    for (int i = 1; i <= n + 1; i++) {
        if (i != n + 1) rd(a[i]), a[i] *= 1e5;
        while (s.size() > 1u && pd(s[s.size()-2], s.back(), i))
            s.pop_back();
        s.pb(i);
    }
    for (ui i = 1; i < s.size(); i++) {
        int l = s[i-1], r = s[i];
        for (int k = l + 1; k < r; k++)
            print(((k - l) * a[r] + (r - k) * a[l]) / (r - l));
        if (r != n + 1) print(a[r]);
    }
    return 0;
}

Sort It Out

首先题意可以转化为第 $k$ 大最长上升子序列 (LIS)。

先考虑如何求 LIS 的数量，设 $f_{i,j},g_{i,j}$ 分别表示考虑前 $i$ 个数，最后一个元素为 $j$ 的 LIS 长度以及数量。

这可以用建立在值域上的树状数组优化，时间复杂度 $\mathcal O(n \log n)$。

那么求第 $k$ 大 LIS，先预处理出每个位置开头的 LIS 长度及数量，然后从前往后找即可。

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

const int N = 1e5 + 7;
const ll inf = 1e18;
int n, m, a[N], b[N];
ll k, c[N];
bool v[N];
vi e[N];

struct T {
    int x;
    ll c;
    inline T() {}
    inline T(int x, ll c) : x(x), c(c) {}
    inline friend void operator += (T &a, const T &b) {
        if (a.x < b.x) a.x = b.x, a.c = b.c;
        else if (a.x == b.x) a.c = min(inf, a.c + b.c);
    }
} t[N];

inline void add(int x, T y) {
    while (x) t[x] += y, x -= x & -x;
}

T ask(int x) {
    T y = T(0, 1);
    while (x <= n) y += t[x], x += x & -x;
    return y;
}

int main() {
    rd(n), rd(k);
    for (int i = 1; i <= n; i++) rd(a[i]), b[a[i]] = i;
    for (int i = n; i; i--) {
        T o = ask(b[i] + 1);
        e[++o.x].push_back(i), c[i] = o.c, add(b[i], o);
    }
    m = ask(1).x;
    int now = -1;
    for (int i = m; i; i--)
        for (int j : e[i])
            if (b[j] >= now) {
                if (k <= c[j]) {
                    v[j] = 1, now = b[j];
                    break;
                } else k -= c[j];
            }
    print(n - m);
    for (int i = 1; i <= n; i++)
        if (!v[i]) print(i);
    return 0;
}

The Cow Gathering

显然每次只能删叶子。

对于点 $i$，考虑以 $i$ 为根的内向树加上限制构成的图，若图无环则可以为最后一个点，否则不可以，这样就 $\mathcal O(n(n+m))$ 了。

注意到每一条限制会砍掉一棵子树，这棵子树中的点必不可以。

最后剩下的点的答案一定是相同的，$\mathcal O(n+m)$ 判一下即可。

#define Fail { for (int i = 1; i <= n; i++) print(0); return 0; }
const int N = 1e5 + 7;
int n, m, b[N], f[N][21], d[N], rt;
vi e[N];
pi p[N];
bool v[N], ans[N];

void dfs(int x) {
    d[x] = d[f[x][0]] + 1;
    for (int i = 0; f[x][i]; i++)
        f[x][i+1] = f[f[x][i]][i];
    for (int y : e[x])
        if (y != f[x][0])
            f[y][0] = x, dfs(y);
}

inline int jump(int x, int d) {
    while (d) x = f[x][b[d&-d]], d -= d & -d;
    return x;
}

inline bool pd(int x, int y) {
    if (d[y] < d[x]) return 0;
    return jump(y, d[y] - d[x]) == x;
}

void dfs1(int x) {
    if (v[x]) return;
    ans[x] = 1;
    for (int y : e[x])
        if (y != f[x][0]) dfs1(y);
}

namespace work {
    int d[N], c[N];
    vi e[N];
    bool v[N];

    void dfs(int x, int f) {
        for (int y : ::e[x])
            if (y != f) d[y] = d[x] + 1, dfs(y, x);
    }

    inline bool main(int rt) {
        d[rt] = 1, dfs(rt, 0);
        for (int x = 1; x <= n; x++)
            for (int y : ::e[x])
                if (d[x] > d[y]) e[x].pb(y), ++c[y];
        for (int i = 1; i <= m; i++)
            e[p[i].fi].pb(p[i].se), ++c[p[i].se];
        queue<int> q;
        for (int i = 1; i <= n; i++)
            if (!c[i]) q.push(i);
        while (q.size()) {
            int x = q.front();
            q.pop();
            for (int y : e[x])
                if (!--c[y]) q.push(y);
        }
        for (int i = 1; i <= n; i++)
            if (c[i]) return 0;
        return 1;
    }
}

int main() {
    rd(n, m);
    for (int i = 1, t = 2; t < n; i++, t <<= 1) b[t] = i;
    for (int i = 1, x, y; i < n; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x);
    dfs(rt = 1);
    for (int i = 1; i <= m; i++) {
        rd(p[i].fi, p[i].se);
        if (pd(p[i].fi, p[i].se)) {
            int x = jump(p[i].se, d[p[i].se] - d[p[i].fi] - 1);
            if (pd(rt, x)) rt = x;
            else if (!pd(x, rt)) Fail;
        } else {
            if (pd(rt, p[i].fi)) {
                if (rt == p[i].fi) Fail;
                v[p[i].fi] = 1;
            } else if (pd(p[i].fi, rt)) Fail;
        }
    }
    if (work::main(rt)) {
        dfs1(rt);
        for (int i = 1; i <= n; i++) print(ans[i]);
    } else Fail;
    return 0;
}

2019 January Contest

Redistricting

线段树优化 DP，时间复杂度 $\mathcal O(n \log n)$。

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

struct SGT {
    struct T {
        int l, r, x;
    } t[N<<3|1];
    multiset<int> st[N<<1|1];

    inline void update(int p) {
        t[p].x = min(t[ls].x, t[rs].x);
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) return t[p].x = inf, void();
        build(ls, l, md), build(rs, md + 1, r);
        update(p);
    }

    void ins(int p, int x, int k) {
        if (t[p].l == t[p].r) {
            st[x].insert(k);
            t[p].x = *st[x].begin();
            return;
        }
        ins(x <= md ? ls : rs, x, k);
        update(p);
    }

    void del(int p, int x, int k) {
        if (t[p].l == t[p].r) {
            st[x].erase(st[x].find(k));
            t[p].x = st[x].size() ? *st[x].begin() : inf;
            return;
        }
        del(x <= md ? ls : rs, x, k);
        update(p);
    }

    int ask(int p, int l, int r) {
        if (t[p].l >= l && t[p].r <= r) return t[p].x;
        int ret = inf;
        if (l <= md) ret = min(ret, ask(ls, l, r));
        if (r > md) ret = min(ret, ask(rs, l, r));
        return ret;
    }
} t;

int main() {
    rd(n, k), rds(s, n);
    for (int i = 1; i <= n; i++) a[i] = a[i-1] + (s[i] == 'G');
    for (int i = 0; i <= n; i++) a[i] = 2 * a[i] - i + n + 1;
    t.build(1, 1, n * 2 + 2);
    t.ins(1, a[0], 0);
    for (int i = 1; i <= n; i++) {
        if (i > k) t.del(1, a[i-k-1], f[i-k-1]);
        f[i] = min(t.ask(1, 1, a[i]) + 1, t.ask(1, a[i] + 1, n * 2 + 2));
        t.ins(1, a[i], f[i]);
    }
    print(f[n]);
    return 0;
}

Exercise Route

两条非树边合法当且仅当它们在树上的路径有边交。

考虑如何计数，首先把一条路径从 LCA 处断开，对两段分别计数，再减去同时与两段有交的个数。

后者很好算，考虑如何计算前者。

对于一条祖先到孩子的路径 $P$，与其有交的路径个数为祖先在 $P$ 孩子之上的数量减去孩子在 $P$ 祖先之上的数量。

那么树上差分一下就好了。

Train Tracking 2

先考虑所有限制都相同的情况。

设大于限制的数有 $x$ 个，限制的区间长度为 $k$。

考虑 DP，设 $f_i$ 表示 $i$ 个数的答案，则有 $f_i = (x+1)f_{i-1} – x^kf_{i-k-1}$。

解释一下就是，第 $i$ 个数有 $x+1$ 种填法，而其中 $i-k+1\sim i$ 都大于限制的情况不合法，而在这种情况下 $i-k$ 处必须等于限制。

现在考虑限制不同的情况，若相邻两个限制不同，一定可以确定一个数。

对每一个相同限制的段，去掉确定的数之后计算即可。

const int N = 1e5 + 7, inf = 1e9;
int n, k, a[N];
modint f[N], ans = 1;

inline modint calc(modint x, int n) {
    modint w = x ^ k;
    f[0] = f[1] = 1;
    for (int i = 2; i <= n; i++)
        f[i] = (x + 1) * f[i-1] - (i - k - 1 >= 0 ? w * f[i-k-1] : 0);
    return f[n];
}

int main() {
    rd(n, k), rda(a, n + 1 - k);
    for (int i = 1; i <= n + 1 - k; i++) a[i] = inf - a[i];
    for (int i = 1, j = 1; i <= n + 1 - k; i = ++j) {
        while (j < n - k + 1 && a[j+1] == a[i]) ++j;
        int m = j - i + k + 1;
        if (i != 1 && a[i-1] < a[i]) m -= k;
        if (j != n - k + 1 && a[j+1] < a[i]) m -= k;
        if (m > 1) ans = 1ll * ans * calc(a[i], m);
    }
    print(ans);
    return 0;
}

2019 February Contest

Cow Dating

推一下式子就会发现，答案就是对于每个 $l$ 找到最近的 $r$ 满足 $\sum_{i=l}^r \frac{p_i}{1-p_i} \ge 1$，然后用 $\left(\prod_{i=l}^r(1-p_i)\right)\left(\sum_{i=l}^r \frac{p_i}{1-p_i}\right)$ 去更新答案。

two pointers 即可，时间复杂度 $\mathcal O(n)$。

const int N = 1e6 + 7;
int n;
ld a[N], A = 1, B, ans;

int main() {
    rd(n);
    for (int i = 1, x; i <= n; i++) rd(x), a[i] = x / 1e6;
    for (int l = 1, r = 0; l <= n; A /= 1 - a[l], B -= a[l] / (1 - a[l]), l++) {
        while (r < n && B < 1) ++r, A *= 1 - a[r], B += a[r] / (1 - a[r]);
        ans = max(ans, A * B);
    }
    print((int)(ans * 1e6));
    return 0;
}

Moorio Kart

这题目说了个啥……

读一年没读懂题目系列，扔了。

Mowing Mischief

题目太神仙了，先咕咕咕着。

2019 US Open Contest

Compound Escape

咕。

Valleys

咕。