Visits: 355

EA 的练习赛

后缀树 suffix

$ans = 26 \times 25^{n-1}$，快速幂即可。

int main() {
    int n;
    rd(n);
    print(((modint)25 ^ (n - 1)) * 26);
    return 0;
}

纯粹容器 senpai

分四种情况讨论一下，有一种情况要期望 dp，复杂度 $\mathcal O(n^4)$。

const int N = 53;
int n, a[N], p[N];
modint f[N][N][N];

inline modint DP(int o, int l, int r) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= o - l; j++)
            for (int k = 0; k <= r - o; k++)
                f[i][j][k] = 0;
    f[0][o-l][r-o] = 1;
    modint ret = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j <= o - l; j++)
            for (int k = 0; k <= r - o; k++) {
                if (!f[i][j][k]) continue;
                if (!j || !k) ret += (i - 1) * f[i][j][k];
                else {
                    int w = n - 1 - i - j - k;
                    f[i+1][j-1][k] += f[i][j][k] * j / (j + k + w);
                    f[i+1][j][k-1] += f[i][j][k] * k / (j + k + w);
                    f[i+1][j][k] += f[i][j][k] * w / (j + k + w);
                }
            }
    return ret;
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]);
    for (int i = 1; i <= n; i++) {
        int l = i, r = i;
        while (l && a[l] <= a[i]) --l;
        while (r <= n && a[r] <= a[i]) ++r;
        if (!l && r > n) print(n - 1, ' ');
        else if (!l) print((modint)(n - r + i - 1) * (r - i) / (r - i + 1) + (r - i - 1), ' ');
        else if (r > n) print((modint)(n - i + l - 1) * (i - l) / (i - l + 1) + (i - l - 1), ' ');
        else print(DP(i, l, r), ' ');
    }
    return 0;
}

丝之割 silksong

$n^2$ 的 dp，注意到转移是一个一次函数，斜率优化 + 单调队列做到 $\mathcal O(n)$。

const int N = 3e5 + 7;
int n, m, c[N], t, l, r, qu[N];
pi p[N];
pair<ll, ll> q[N];
ll a[N], b[N], f[N];

inline ld calc(pair<ll, ll> a, pair<ll, ll> b) {
    return 1.0L * (b.se - a.se) / (a.fi - b.fi);
}

int main() {
    rd(n), rd(m);
    for (int i = 1; i <= n; i++) rd(a[i]);
    for (int i = 2; i <= n; i++) a[i] = min(a[i], a[i-1]);
    for (int i = 1; i <= n; i++) rd(b[i]);
    for (int i = n - 1; i; i--) b[i] = min(b[i], b[i+1]);
    for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), c[x] = max(c[x], y);
    for (int i = 2, j = 0; i <= n; i++)
        if (c[i] > j) j = c[i], p[++t] = mp(i, j);
    p[t+1].fi = n + 1;
    q[0] = mp(a[p[1].fi-1], 0), qu[0] = 0;
    for (int i = 1; i <= t; i++) {
        while (l < r && calc(q[l], q[l+1]) < b[p[i].se+1]) ++l;
        f[i] = q[l].fi * b[p[i].se+1] + q[l].se;
        pair<ll, ll> o = mp(a[p[i+1].fi-1], f[i]);
        while (l < r && calc(q[r-1], q[r]) > calc(q[r], o)) --r;
        if (o.fi != q[r].fi) q[++r] = o, qu[r] = i;
    }
    print(f[t]);
    return 0;
}

最优性剪枝 search

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

燔祭 sacrificial

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