Comet OJ – 模拟赛 #1 Day1 题解

作者: xht37 分类: 题解 发布时间: 2019-11-11 11:30

点击数:68

Comet OJ – 模拟赛 #1 Day1

修行

结论:不论怎样操作,当前序列的每个数始终分别对应原序列某极小段的总和,靠前的数对应的段也靠前,且段与段两两不相交。

拥有这个结论,我们只要找到 $b$ 中每个数对应 $a$ 中的段,如果段只包含了自己并且位置相同,我们就不需要浪费操作在它身上,否则恰好需要一次操作合并出该数。

然后就是模拟了,可以 $\mathcal O(n)$ 实现,细节较多。

const int N = 1e5 + 7;
int n, a[N], b[N], p[N];

inline void solve() {
    rd(n);
    ll sa = 0, sb = 0;
    for (int i = 1; i <= n; i++) rd(a[i]), sa += a[i];
    for (int i = 1; i <= n; i++) rd(b[i]), sb += b[i];
    if (sa ^ sb) return print(-1), void();
    for (int i = 0, j = 1; j <= n; j++) {
        int k = 0;
        while (i + 1 <= n && k < b[j]) k += a[++i];
        if (k == b[j]) p[j] = i;
        else return print(-1), void();
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += b[i] && (a[i] != b[i] || i != p[i]);
    print(ans);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

灾厄

显然的最小生成树,然后求树上路径长度,时间复杂度 $\mathcal O(n \log n + m + q \log n)$。

const int N = 3e5 + 7;
int n, m, q, fa[N], d[N], f[N][20], g[N][20];
vector< pi > e[N];

void dfs(int x) {
    for (ui i = 0; i < e[x].size(); i++) {
        int y = e[x][i].fi, z = e[x][i].se;
        if (y == f[x][0]) continue;
        f[y][0] = x;
        g[y][0] = z;
        d[y] = d[x] + 1;
        for (int i = 0; f[y][i]; i++)
            f[y][i+1] = f[f[y][i]][i], g[y][i+1] = Add(g[y][i], g[f[y][i]][i]);
        dfs(y);
    }
}

inline int ask(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    int ans = 0;
    for (int i = 19; ~i; i--)
        if (d[f[y][i]] >= d[x]) ans = Add(ans, g[y][i]), y = f[y][i];
    if (x == y) return ans;
    for (int i = 19; ~i; i--)
        if (f[x][i] ^ f[y][i])
            ans = Add(ans, Add(g[x][i], g[y][i])),
            x = f[x][i], y = f[y][i];
    return Add(ans, Add(g[x][0], g[y][0]));
}

int get(int x) {
    return x == fa[x] ? x : (fa[x] = get(fa[x]));
}

int main() {
    rd(n), rd(m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1, x, y, z = 2; i <= m; i++, z = Mul(z, 2)) {
        rd(x), rd(y);
        if (get(x) == get(y)) continue;
        fa[get(x)] = get(y), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
    }
    d[1] = 1;
    dfs(1);
    rd(q);
    for (int i = 1, x, y; i <= q; i++)
        rd(x), rd(y), print(ask(x, y));
    return 0;
}

羁绊

设 $a_i$ 在序列中由大到小的排名为 $p_i$,则 $ans = \frac 13 \sum_{i=1}^n a_i (\frac 34)^{p_i}$。

带修的话,可以先离散化然后在值域上维护一棵支持单点修改的线段树即可,时间复杂度 $\mathcal O(n \log n + q \log n)$。

代码有点麻烦不写了。

发表评论

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