JOISC 2018 题解

作者: xht37 分类: 题解 发布时间: 2020-05-29 16:45

点击数:103

JOISC 2018

Day 1

道路建设

发现操作本质上是一个 $\text{access}$,LCT 维护即可,逆序对就把路径上的颜色爬下来树状数组求就行了,时间复杂度 $\mathcal O(n \log^2 n)$。

const int N = 1e5 + 7;

struct LCT {
    int f[N], ch[N][2], s[N], z[N], a[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
    #define get(p) (p == ch[f[p]][1])
    #define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
    #define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
    inline void spd(int p) {
        if (z[p]) {
            if (lc) a[lc] = z[lc] = z[p];
            if (rc) a[rc] = z[rc] = z[p];
            z[p] = 0;
        }
    }
    inline void rot(int p) {
        int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
        f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
        f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
        if ((f[p] = y) && !o) ch[y][v] = p;
    }
    void pre(int p) {
        if (!isrt(p)) pre(f[p]);
        spd(p);
    }
    inline void splay(int p) {
        pre(p);
        for (int x = f[p]; !isrt(p); rot(p), x = f[p])
            if (!isrt(x)) rot(get(p) == get(x) ? x : p);
    }
    inline vector<pi> access(int p) {
        vector<pi> ret;
        int w = 0;
        for (int x = 0; p; p = f[x=p])
            splay(p), rc = x, upd(p),
            ret.pb(mp(a[p], s[p] - w)), w = s[p];
        return ret;
    }
    inline void link(int p, int x) {
        int w = a[x];
        splay(p), rc = x, f[x] = p, splay(x), upd(x), a[x] = z[x] = w;
    }
} lct;

struct BIT {
    vector<ll> c;
    inline BIT() {}
    inline BIT(int n) { c.resize(n); }
    inline void add(ui x, ll k) {
        while (x < c.size()) c[x] += k, x += x & -x;
    }
    inline ll ask(ui x) {
        ll k = 0;
        while (x) k += c[x], x -= x & -x;
        return k;
    }
};

int n, a[N];

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), lct.a[i] = a[i];
    sort(a + 1, a + n + 1);
    int t = unique(a + 1, a + n + 1) - (a + 1);
    BIT c(t + 1);
    for (int i = 1; i <= n; i++)
        lct.a[i] = lower_bound(a + 1, a + t + 1, lct.a[i]) - a;
    lct.s[1] = 1;
    for (int i = 1, x, y; i < n; i++) {
        rd(x, y);
        auto ret = lct.access(x);
        ll ans = 0;
        for (pi o : ret)
            ans += o.se * c.ask(o.fi - 1), c.add(o.fi, o.se);
        print(ans);
        for (pi o : ret) c.add(o.fi, -o.se);
        lct.link(x, y);
    }
    return 0;
}

栅栏

咕。

帐篷

设 $f_{i,j}$ 表示 $i,j$ 的答案,转移枚举第一行怎么填即可,采用记搜写法,时间复杂度 $\mathcal O(n^2)$。

const int N = 3e3 + 7;
const modint inv2 = (modint)1 / 2;
modint f[N][N];
bool v[N][N];

inline modint F(int n, int m) {
    if (!n || !m) return 1;
    if (v[n][m]) return f[n][m];
    v[n][m] = 1;
    modint &k = f[n][m];
    k += F(n - 1, m);
    k += m * F(n - 1, m - 1) * 4;
    if (m >= 2) k += m * (m - 1) * inv2 * F(n - 1, m - 2);
    if (n >= 2) k += m * (n - 1) * F(n - 2, m - 1);
    return k;
}

int main() {
    int n, m;
    rd(n, m), print(F(n, m) - 1);
    return 0;
}

Day 2

修行

题意相当于求有多少 $1\sim n$ 的排列满足 $p_i > p_{i+1}$ 的 $i$ 恰好 $k-1$ 个。

转化为求概率,等价于 $n$ 个 $[0,1)$ 的随机变量 $a_{1\dots n}$ 满足 $a_i > a_{i+1}$ 的 $i$ 恰好 $k-1$ 个的概率。

考虑构造 $b_{i} = [a_{i-1} > a_i] + a_i – a_{i-1}$,其中 $b_1 = a_1$,即 $a$ 为 $b$ 的前缀和的小数部分。

于是问题转化为求 $k-1 \le \sum_{i=1}^n b_i < k$ 的概率,可以差分一下。

考虑容斥掉 $b_i \in [0,1)$ 的限制,于是问题变成 $n$ 个 $[0,+\infty)$ 的数之和 $< k$ 的概率,这个概率实际上等于 $\frac{k^n}{n!}$。

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

int n, k;

inline modint calc(int k) {
    modint ans = 0, o = 1;
    for (int i = 0; i < k; i++, o = -o)
        ans += o * binom(n, i) * ((modint)(k - i) ^ n);
    return ans;
}

int main() {
    rd(n, k), init(n);
    print(calc(k) - calc(k - 1));
    return 0;
}

路网服务

提答题,扔了。

最差记者 3

首先可以直接求出每个人的周期,即当 $i-1$ 走的长度不小于 $d_i$ 时,$i$ 将走 $i-1$ 所走的那么长。

于是 $d_i$ 为 $d_{i-1}$ 的倍数,则不同的 $d$ 只有 $\mathcal O(\log w)$ 个,则每次暴力求区间交即可,时间复杂度 $\mathcal O(q\log w)$。

const int N = 5e5 + 7;
int n, m, a[N];

int main() {
    rd(n, m), rda(a, n), a[0] = 1;
    vector<pi> p;
    p.pb(mp(1, 0));
    for (int i = 1; i <= n; i++) {
        if (a[i] % a[i-1]) a[i] = (a[i] / a[i-1] + 1) * a[i-1];
        if (a[i] == a[i-1]) ++p.back().se;
        else p.pb(mp(a[i], i));
    }
    for (int i = 1, t, l, r, ans, lst; i <= m; i++) {
        rd(t, l, r), ans = lst = 0;
        for (pi o : p) {
            int L = t / o.fi * o.fi - o.se, R = t / o.fi * o.fi - lst;
            ans += max(0, min(r, R) - max(l, L) + 1), lst = o.se + 1;
        }
        print(ans);
    }
    return 0;
}

Day 3

比太郎的聚会

对于这种询问中的某个量之和与 $n$ 同阶的题目,通常有三个做法:

  1. 如果是在树上,可以考虑虚树。
  2. 这个量只有 $\mathcal O(\sqrt n)$ 种,算过的保存下来就可以直接用。
  3. 这个量 $> \sqrt n$ 的只有 $\mathcal O(\sqrt n)$ 个,可以暴力;$\le \sqrt n$ 的通常可以预处理。

本题考虑第三个性质即可。

安全门

咕。

Day 4

其实是 经典题

其实同样是个带悔贪心。

带悔贪心的解题方法:

  • 算上反悔的代价之后用堆贪心。
  • 模拟费用流。

首先贪心的选,当选择在 $i$ 之后,$i-1$ 和 $i+1$ 的位置要么同时选,要么同时不选,当同时选的时候就要撤销选择 $i$,因此我们可以将 $a_{i-1}+a_{i+1}-a_i$ 作为一个新的物品放入原本 $i$ 的位置,同时删掉 $i-1$ 和 $i+1$。

用链表和堆维护即可。

#define P pair<ll, int>
const int N = 2e5 + 7;
int n, m, l[N], r[N];
ll a[N], ans;
bool v[N];
priority_queue<P> q;

int main() {
    rd(n), m = (n + 1) >> 1, rda(a, n), a[0] = a[n+1] = -1e18, r[n+1] = n + 1;
    for (int i = 1; i <= n; i++)
        q.push(mp(a[i], i)), l[i] = i - 1, r[i] = i + 1;
    for (int i = 1; i <= m; i++) {
        while (v[q.top().se]) q.pop();
        int x = q.top().se;
        q.pop(), ans += a[x], print(ans);
        int L = l[x], R = r[x];
        v[L] = v[R] = 1, a[x] = a[L] + a[R] - a[x];
        l[x] = l[L], r[x] = r[R], r[l[x]] = x, l[r[x]] = x;
        if (L >= 1 && R <= n) q.push(mp(a[x], x));
    }
    return 0;
}

图书馆

考虑先通过最多 $n$ 次询问找到某一端,方法为询问 $[1,n] – i$,若答案为 $1$ 说明是某一端。

然后从这一端不断地找到与其相邻的下一个位置。考虑二分,假设我们现在要找到与位置 $p$ 相邻的某个位置,设可能的位置集合为 $S$,将其均匀的分为 $A,B$ 两个集合,然后询问 $A$ 和 $A + p$ 的答案,如果后者等于前者,说明 $A$ 中存在与 $p$ 相邻的位置,否则说明 $B$ 中存在与 $p$ 相邻的位置,然后二分下去即可。

询问复杂度为 $\mathcal O(n \log n)$。

int n;

inline int ask(vi p, int w = 0) {
    vi m(n);
    for (int x : p) m[x-1] = 1;
    if (w) m[w-1] = 1;
    return Query(m);
}

void Solve(int n) {
    srand(time(0) ^ n);
    ::n = n;
    vi p(n);
    for (int i = 0; i < n; i++) p[i] = i + 1;
    random_shuffle(p.begin(), p.end());
    for (int i = 0; i < n; i++) {
        swap(p[0], p[i]);
        if (i == n - 1 || ask(vi(p.begin() + 1, p.end())) == 1) break;
    }
    for (int i = 0; i < n - 1; i++) {
        auto l = p.begin() + i + 1, r = p.end();
        while (l + 1 != r) {
            auto mid = l + ((r - l) >> 1);
            if (ask(vi(l, mid)) == ask(vi(l, mid), p[i])) r = mid;
            else l = mid;
        }
        swap(p[i+1], *l);
    }
    Answer(p);
}

野猪

咕。

发表评论

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