Posted in: QuestOJ 比赛题解

「FZOI」OI 周赛 #2 Div.1 – 题解

Written by kal0rona Leave a Comment on 「FZOI」OI 周赛 #2 Div.1 – 题解
内容纲要

A - Genius ACM

个人认为这道题目作为一个小的贪心+模拟作为签到题不算过分。考虑把第一个连续的分数段作为金牌，之后一直取银牌直到大于金牌数量，最后能取多少取多少铜牌即可。

// genius.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e6 + 2000;

int T, n, pi[MAX_N], cnt;
pair<int, int> prs[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &pi[i]);
        if (pi[i] != pi[i - 1])
            prs[++cnt] = make_pair(pi[i], 0);
        prs[cnt].second++;
    }
    int gold = prs[1].second, silver = 0, bronze = 0, ptr = 2;
    while (silver <= gold && ptr <= cnt)
        silver += prs[ptr++].second;
    while (bronze <= gold && ptr <= cnt)
        bronze += prs[ptr++].second;
    while (gold + silver + bronze + prs[ptr].second <= (n >> 1) && ptr <= cnt)
        bronze += prs[ptr++].second;
    if (gold < silver && gold < silver && (gold + silver + bronze) <= (n >> 1))
        printf("%d %d %d\n", gold, silver, bronze);
    else
        puts("0 0 0");
    return 0;
}

B - 镜之边缘

一道比较基础的概率期望 DP。考虑设置状态$dp[i]$为从$1 \to i$的期望次数，那么很自然的有：
$$
\begin{aligned}
dp[i] &= dp[i - 1] \times p_i + 1 + (1 - p_i)(dp[i - 1] + 1 + dp[i]) \
&= \frac{dp[i - 1] + 1}{p_i}
\end{aligned}
$$
然而，这样直接做只能拿到$90$分。我们发现在$p_i \times 100 \in [0, 100]$之间，所以我们可以预处理$100$个逆元，并且加上一个快读即可。

// mirror.cpp
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 7e7 + 200, mod = 998244353;

int n, pi[MAX_N], dp[MAX_N], inv[200];

inline char gc()
{
    static const int IN_LEN = 1 << 21 | 1;
    static char buf[IN_LEN], *s, *t;
    return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)), s == t ? -1 : *s++;
}
int read()
{
    int x = 0, f = 1;
    char ch = gc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = gc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = gc();
    return x * f;
}
int quick_pow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}
int main()
{
    const int inv100 = quick_pow(100, mod - 2);
    n = read();
    for (register int i = 1; i <= n; i++)
        pi[i] = read();
    for (register int i = 1; i <= 100; i++)
        inv[i] = quick_pow(1LL * i * inv100 % mod, mod - 2);
    for (register int i = 1; i <= n; i++)
        dp[i] = 1LL * ((1LL * dp[i - 1] + 1) % mod) * inv[pi[i]] % mod;
    printf("%d\n", dp[n]);
    return 0;
}

C - 接水果

在讲题的时候并没有讲清楚，所以在这里我会写一个比较长的题解。

首先，对于每一个询问，我们都要确定一个问题：哪些设定路径会覆盖询问路径？我们把这颗树的 DFS 求出，记录子树的 DFS 序范围在 $[L[u], R[u]]$ 之间。询问路径 $(x, y)$ 有两种情况：

  • LCA 为 $x$ 或 $y$。
  • LCA 为其他点，记为 $w$。

第一种情况

考虑把设定路径设为 $(a, b), dfn[a] < dfn[b]$，我们把这个路径抽象成一个有序数对，只不过需要用 DFS 序进行表示：$(dfn[a], dfn[b])$。我们发现，满足覆盖的设定路径在这种情况下，一定满足：

  • $dfn[b] \in [L[y], R[y]]$。
  • $dfn[a] \in [1, L[x]] \cup (R[x], n]$。

如图所示就十分清晰：DFS 序的取值区间意味着是否在子树内。理解了这个之后就不难理解上面两则为什么是一定满足的了。

第二种情况

第二种情况更为简单，如图所示：

发现对于 $(a, b), dfn[a] < dfn[b]$，有：

  • $dfn[a] \in [L[x], R[x]]$。
  • $dfn[b] \in [L[y], R[y]]$。

这两种情况讨论之后，我们可以成功把这道题目转换成二位平面上的问题。

长方形问题

我们可以先对整个树进行一遍 DFS。结束之后，所有的设定路径就会分布在二维平面上。

我们再来思考每个询问的意义：在两个维度上限制 DFS 在某一个区间内。那么其实，第二种询问所对应的就是一块长方形区域，而第一种其实就是两块分开的长方形区域。我们需要一种技术，能让所有的长方形块中快速得到第$k$小的点（也就是设定路径）。

扫描线技术

详见：扫描线 - OI Wiki

整体二分

求第 $k$ 小是有二分性的：对于比当前$mid$小的，计入$cnt++$；而如果没有，那么则忽略。如果这个 $cnt \leq k$ ，那么说明 $mid$ 可以再大一点。假设我们硬是要在一个序列上做，那么复杂度是 $\Theta(n \log n)$ 的。然而，我们不能做 $q$ 次这样的操作，否则一定会超时。我们可以考虑把 $q$ 个问题一起进行二分：也就是整体二分。整体二分使用了分治的技巧，可以让最后的 $q$ 个询问都得到单独的处理。考虑把这 $q$ 个询问放入一个询问序列中 ${opt_i}$，设置函数 $solve(l, r, ql, qr)$：$l, r$ 指的是值域的二分范围，而 $ql, qr$ 则是需要处理的询问区间，初始的时候，参数设置为 $ql = 1, qr = q, l = 1, r = 10^9$。我们可以拿到一个 $mid$ ，这个时候整个询问序列中一定会分化出两种情况：一个是 $kth \leq mid$，还有一种是大于的。欲处理这两种二分方向，我们只能把这两种情况的询问分别取出，再重新分配给两个不同二分方向的子任务：左侧为小于的询问，而右侧为大于的询问，我们只需要开两个队列进行储存，并重新设置整个序列的顺序即可。

设置好了之后，我们就向下，让子问题继续解决被缩小的两个子问题。当触碰到边界时，那么我们发现$[ql, qr]$操作的答案全部为边界。

我们如何在整体二分时，把长方形放入扫描线中？很简单，只需要按 $x$ 进行排序即可，然后用树状数组维护即可。树状数组中维护的是当前平面上$y \in [lower, upper]$这一段上有多少个小于 $mid$ 的个数，以供询问时进行二分判断。

代码

// fruit.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200, INF = 0x3f3f3f3f;

int n, p, q, head[MAX_N], current, dfn[MAX_N], low[MAX_N], fa[20][MAX_N], dep[MAX_N];
int qcnt, ptot, ans[MAX_N], nodes[MAX_N], vec[MAX_N], vcnt;

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

struct query
{
    int typ, x, lower, upper, k, val, id;
    bool operator<(const query &rhs) const { return x < rhs.x || (x == rhs.x && typ < rhs.typ); }
} queries[MAX_N], q1[MAX_N], q2[MAX_N];

inline char gc()
{
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}

int read()
{
    int x = 0, f = 1;
    char ch = gc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = gc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + (ch - '0'), ch = gc();
    return x * f;
}

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u, int fat)
{
    fa[0][u] = fat, dep[u] = dep[fat] + 1, dfn[u] = ++ptot;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fat)
            dfs(edges[i].to, u);
    low[u] = ptot;
}

int getLCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[fa[i][x]] >= dep[y])
            x = fa[i][x];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}

int getSon(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[fa[i][x]] >= dep[y] + 1)
            x = fa[i][x];
    return x;
}

inline int lowbit(int x) { return x & (-x); }

inline void update(int qx, int d)
{
    for (; qx <= n; qx += lowbit(qx))
        nodes[qx] += d;
}

inline int querySum(int qx, int ret = 0)
{
    for (; qx != 0; qx -= lowbit(qx))
        ret += nodes[qx];
    return ret;
}

void solve(int l, int r, int ql, int qr)
{
    if (ql > qr)
        return;
    if (l == r)
    {
        for (int i = ql; i <= qr; i++)
            if (queries[i].typ == 1)
                ans[queries[i].id] = vec[l];
        return;
    }
    int mid = (l + r) >> 1, lcnt = 0, rcnt = 0;
    for (int i = ql; i <= qr; i++)
        if (queries[i].typ == 0)
            if (queries[i].k <= mid)
                update(queries[i].lower, queries[i].val), update(queries[i].upper + 1, -queries[i].val), q1[++lcnt] = queries[i];
            else
                q2[++rcnt] = queries[i];
        else
        {
            int ref_val = querySum(queries[i].lower);
            if (queries[i].k <= ref_val)
                q1[++lcnt] = queries[i];
            else
                q2[++rcnt] = queries[i], q2[rcnt].k -= ref_val;
        }
    for (int i = 1; i <= lcnt; i++)
        queries[ql + i - 1] = q1[i];
    for (int i = 1; i <= rcnt; i++)
        queries[ql + lcnt + i - 1] = q2[i];
    solve(l, mid, ql, ql + lcnt - 1), solve(mid + 1, r, ql + lcnt, qr);
}

int main()
{
    memset(head, -1, sizeof(head));
    n = read(), p = read(), q = read();
    for (int i = 1, u, v; i <= n - 1; i++)
        u = read(), v = read(), addpath(u, v), addpath(v, u);
    dfs(1, 0);
    for (int i = 1; i <= 19; i++)
        for (int j = 1; j <= n; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    // to put rect above the axis;
    for (int id = 1; id <= p; id++)
    {
        int a = read(), b = read(), c = read();
        vec[++vcnt] = c;
        if (dfn[a] > dfn[b])
            swap(a, b);
        int lca = getLCA(a, b);
        if (lca == a)
        {
            int son = getSon(a, b);
            // the less at x-axis, bigger at y-axis;
            if (dfn[son] > 1)
            {
                queries[++qcnt] = query{0, 1, dfn[b], low[b], c, 1, 0};
                queries[++qcnt] = query{0, dfn[son], dfn[b], low[b], c, -1, 0};
            }
            if (low[son] < n)
            {
                queries[++qcnt] = query{0, dfn[b], low[son] + 1, n, c, 1, 0};
                queries[++qcnt] = query{0, low[b] + 1, low[son] + 1, n, c, -1, 0};
            }
        }
        else
        {
            queries[++qcnt] = query{0, dfn[a], dfn[b], low[b], c, 1, id};
            queries[++qcnt] = query{0, low[a] + 1, dfn[b], low[b], c, -1, id};
        }
    }
    sort(vec + 1, vec + vcnt + 1), vcnt = unique(vec + 1, vec + vcnt + 1) - (vec + 1);
    for (int i = 1; i <= qcnt; i++)
        queries[i].k = lower_bound(vec + 1, vec + 1 + vcnt, queries[i].k) - vec;
    for (int i = 1; i <= q; i++)
    {
        int x = read(), y = read(), k = read();
        if (dfn[x] > dfn[y])
            swap(x, y);
        queries[++qcnt] = query{1, dfn[x], dfn[y], 0, k, 0, i};
    }
    sort(queries + 1, queries + 1 + qcnt);
    solve(1, vcnt, 1, qcnt);
    for (int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
    return 0;
}

发表回复

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

Back to Top