Ryoku 的新年欢乐赛题解

· · 个人记录

Ryoku 的欢乐赛题解

A Ryoku 的探索

显然图为一个基环树。

拓扑排序找到环，对于环上的每一个点 i ，令 w_i 为它在环上与它连接的美观度最小边的边权，每个点及其子树的答案即为所有边权之和减去 w_i.

#include <bits/stdc++.h>

typedef long long ll;

const int kMaxN = 2e6 + 5;
const int kInf = 0x3f3f3f3f;

struct Edge {
    int to, nxt, prf, val;
} edges[kMaxN << 1];
int head[kMaxN], deg[kMaxN], ans[kMaxN], cnt = 0, n;
bool vis[kMaxN];
ll tot = 0;
void AddEdge(int u, int v, int w, int p) { edges[cnt] = (Edge) { v, head[u], p, w }; head[u] = cnt++; }
void Topsort(int cur) {
    vis[cur] = true;
    for(int i = head[cur]; ~i; i = edges[i].nxt) {
        int v = edges[i].to;
        if(vis[v]) continue;
        --deg[v];
        if(deg[v] == 1)
            Topsort(v);
    }
}
void SetAns(int cur, int w) {
    ans[cur] = w;
    for(int i = head[cur]; ~i; i = edges[i].nxt)
        if(vis[edges[i].to] && !ans[edges[i].to])
            SetAns(edges[i].to, w);
}

int main() {
    memset(head, 0xff, sizeof(head));
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        int u, v, p, w;
        scanf("%d%d%d%d", &u, &v, &w, &p);
        AddEdge(u, v, w, p);AddEdge(v, u, w, p);
        ++deg[u]; ++deg[v];
        tot += w;
    }
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) Topsort(i);
    for(int i = 1; i <= n; ++i)
        if(!vis[i]) {
            int minw, minprf = kInf;
            for(int j = head[i]; ~j; j = edges[j].nxt)
                if(!vis[edges[j].to] && edges[j].prf < minprf) {
                    minprf = edges[j].prf;
                    minw = edges[j].val;
                }
            SetAns(i, minw);
        }
    for(int i = 1; i <= n; ++i)
        printf("%lld\n", tot - ans[i]);
    return 0;
}

B Ryoku 与最初之人的笔记

考虑题目相当于求：

a\ {\rm xor}\ b\ |\ a-b

的对数。

注意到 a\ {\rm xor}\ b\ \ge\ a-b，所以实际上是求 a\ {\rm xor}\ b\ =\ a-b 的个数。

观察二进制位，这个式子满足的条件是：对于每一位，b 中为 1 的位必须在 a 中也为一，根据这个进行 \Theta(n \log n) 枚举可以得到可观的分数。如果加上分段打表应该能得到 70\rm pts，即：（r(n) 为 n 在二进制下为 1 的位数）

ans = \sum_{i}2^{r(i)}-n

考虑最高位开始顶着上界，到第 i 位不顶着上界的答案，对于比 i 高的位，由于 a 的这部分已经确定，所以 b 这部分的方案数为 2^{k(i)}（k(i) 表示 n 在比 i 高的位中 1 的个数）

对于比 i 低的位，注意到一个集合 S 的子集的子集个数和位 3^{|S|}，所以共 3^{i-1} 种情况。

利用乘法原理共 2^{k(i)}3^{i-1} 种，累计即可。

我实现的好像有一些细微差异。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll kMod = 1e9 + 7;

ll pow3[100];

int main() {
    pow3[0] = 1;
    for(int i = 1; i < 64; i++)
        pow3[i] = pow3[i - 1] * 3 % kMod;
    ll n, ans = 0; int k = 0;
    cin >> n;
    for(int i = 63; i >= 0; i--)
        if((n >> i) & 1) {
            ans = (ans + (1LL << k) % kMod * pow3[i] % kMod) % kMod;
            k++;
        }
    ans = ((ans + (1LL << k) % kMod - n % kMod - 1) % kMod + kMod) % kMod;
    cout << ans << endl;
    return 0;
}

C Ryoku 的逆序对

（其实这道题本来想放 T1 的…不小心出难了就放这里了）

猜想到合法的序列 B 与排列 A 一一对应。

证明：

证毕。

考虑合法的序列 B 的必要条件：\forall i,0\le b_i \le n-i，符合该条件的 b_i 共 n! 个。由鸽巢原理，这些序列都是合法的，即 \forall i,0\le b_i < n-i \Leftrightarrow B 合法。

这样，易证答案为：

[\forall b_i\neq -1,\ 0\le b_i < n-i]\prod_{b_i=-1} (n-i+1)

显然，令所有 b_i = -1 的位置的 b_i 都为 0 即为字典序最小的方案。

当然，本题也可以通过找规律得到答案。到这里再加上一些奇奇怪怪的构造可以获得 40 \rm pts.

使用你喜欢的一个 \log 的数据结构维护构造应该可获得 100 \rm pts.

#include <bits/stdc++.h>

typedef long long ll;

const int kMod = 1e9 + 7;
const int kMaxN = 1e6 + 5;

int b[kMaxN], seg[kMaxN << 3];
void Update(int cur) { seg[cur] = seg[cur << 1] + seg[cur << 1 | 1]; }
void Build(int cur, int l, int r) {
    if(l < r) {
        int mid = (l + r) >> 1;
        Build(cur << 1, l, mid);
        Build(cur << 1 | 1, mid + 1, r);
        Update(cur);
    } else seg[cur] = 1;
}
void Modify(int cur, int l, int r, int q, int k) {
    if(l == r) seg[cur] = k;
    else {
        int mid = (l + r) >> 1;
        if(q <= mid) Modify(cur << 1, l, mid, q, k);
        if(q > mid) Modify(cur << 1 | 1, mid + 1, r, q, k);
        Update(cur);
    }
}
int QueryKth(int cur, int l, int r, int k) {
    if(l == r) return l;
    int siz = seg[cur << 1], mid = (l + r) >> 1;
    if(k <= siz) return QueryKth(cur << 1, l, mid, k);
    else return QueryKth(cur << 1 | 1, mid + 1, r, k - siz);
}

int main() {
    int n; ll ans = 1;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", b + i);
        if(b[i] > n - i) ans = 0;
        else if(b[i] == -1) { ans = ans * (n - i + 1) % kMod; b[i] = 0; }
    }
    printf("%d\n", ans);
    if(!ans) return 0;
    Build(1, 1, n);
    for(int i = 1; i <= n; ++i) {
        int x = QueryKth(1, 1, n, b[i] + 1);
        printf("%d ", x);
        Modify(1, 1, n, x, 0);
    }
    return 0;
}

D 爱学习的 Ryoku

upd:这题我已经把我自己卡掉了，可以 \Theta(n) 直接期望dp

然而，大部分julao貌似都不是这个做法，他们具体是怎么做的我也不知道。但是精度应该比我强。

而且这题好像可以用奇奇怪怪的做法水过去

首先要给 a^{bx} 找一个多项式近似，随便取若干个点插值即可，设用 F(x) = \sum_{i=0}^k c_ix^i 去近似它

令 x=r-l，这段区间知识的实际效用为：

\sum_{j=0}^kc_jx^j\sum_{i=r-x}^r w_i

考虑 r + 1 时刻的知识，若成功掌握实际效用的变化量为：

\sum_{j=0}^kc_j(x+1)^j\sum_{i=r-x}^{r+1} w_i-\sum_{j=0}^kc_jx^j\sum_{i=r-x}^r w_i

整理得：

\sum_{j=0}^k c_j \left[\sum_{q=0}^{j-1}{j\choose q} x^j\sum_{i=r-x}^{r+1} w_i - (x+1)^jw_i\right]

注意到期望具有线性性，设 Ans(r) 代表前 r 个数的答案，有：

Ans(r + 1) = Ans(r) + p_{r+1}E\left\{\sum_{j=0}^k c_j \left[\sum_{q=0}^{j-1}{j\choose q} x^j\sum_{i=r-x}^{r+1} w_i - (x+1)^jw_{r+1}\right] \right\} = Ans(r)+ p_{r+1}\sum_{j=0}^kc_j\left\{\sum_{q=0}^{j-1}{j\choose q} E\left(x^j\sum_{i=r-x}^{r+1} w_i\right) - E[(x+1)^j]w_{r+1}\right\}

考虑如何分别求出这两个期望。

设：（代表以 r 结尾，连续的最后一段的该式的期望）

W(r,q)=E\left(x^q\sum_{i=r-x}^rw_i\right) P(r,q) = E[(x+1)^q]

易得（W 的计算可以使用与 Ans 同样的方法推导）：

P(r,q) = p_r\sum_{t=0}^{q}{q\choose t}P(r-1,t) W(r,q)=p_{r}\left[\sum_{t=0}^{q}{q\choose t}W(r-1,t) + P(r-1,q)w_r\right]

预处理出组合数，用这个去递推就可以了。

时间复杂度 \Theta(nk^2). k 取 10 左右就可以了。

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ff;

const int kMaxN = 2e5 + 5;
const int kMaxTerm = 9;
const int kMaxT = kMaxTerm + 5;

ff m[kMaxT][kMaxT];
void Div(int i, ff v) { for(int j = 0; j <= kMaxTerm + 1; ++j) m[i][j] /= v; }
void Rem(int i0, int i1, ff t) { for(int j = 0; j <= kMaxTerm + 1; ++j) m[i0][j] -= t * m[i1][j]; }

int n, w[kMaxN]; ll C[kMaxT][kMaxT];
double a, b, p[kMaxN], pt[kMaxT] = {20, 15, 10, 8, 7, 5, 4, 3, 2, 1};
ff c[kMaxN], W[kMaxN][kMaxT], P[kMaxN][kMaxT], ans[kMaxN];

void Init() {
    for(int i = 0; i <= kMaxTerm; ++i) {
        long double x = pt[i];
        m[i][0] = 1;
        for(int j = 1; j <= kMaxTerm; ++j) m[i][j] = m[i][j - 1] * x;
        m[i][kMaxTerm + 1] = pow((ff)a, (ff)b * x);
    }
    for(int i = 0; i <= kMaxTerm; ++i) {
        Div(i, m[i][i]);
        for(int j = 0; j <= kMaxTerm; ++j)
            if(j != i) Rem(j, i, m[j][i]);
    }
    for(int i = 0; i <= kMaxTerm; ++i) c[i] = m[i][kMaxTerm + 1];
    C[0][0] = 1;
    for(int i = 1; i <= kMaxTerm; ++i) {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
}

void Solve() {
    for(int i = 1; i <= n; ++i) {
        P[i][0] = 1;
        W[i][0] = (W[i - 1][0] + w[i]) * p[i];
    }
    for(int q = 1; q <= kMaxTerm; ++q) {
        W[1][q] = 0; P[1][q] = p[1];
        for(int r = 2; r <= n; ++r) {
            ff tmp1 = 0, tmp2 = 0;
            for(int t = 0; t <= q; ++t) tmp1 += C[q][t] * W[r - 1][t], tmp2 += C[q][t] * P[r - 1][t];
            P[r][q] = p[r] * tmp2;
            W[r][q] = p[r] * (tmp1 + P[r - 1][q] * w[r]);
        }
    }
    ans[1] = p[1] * w[1];
    for(int r = 2; r <= n; ++r) {
        for(int j = 0; j <= kMaxTerm; ++j) {
            ff tmp = 0;
            for(int q = 0; q < j; ++q)
                tmp += C[j][q] * W[r - 1][q];
            tmp += P[r - 1][j] * w[r];
            ans[r] += tmp * c[j];
        }
        ans[r] = p[r] * ans[r] + ans[r - 1];
    }
}

int main() {
    scanf("%d%lf%lf", &n, &a, &b);
    for(int i = 1; i <= n; ++i) scanf("%d", w + i);
    for(int i = 1; i <= n; ++i) scanf("%lf", p + i);
    Init(); Solve();
    printf("%.4Lf", ans[n]);
    return 0;
}