王清楚

编辑于 2022-07-27 17:35

【题解】"蔚来杯"2022牛客暑期多校训练营2

A

题面等价于找到一条最长的，恰好 $k$ 条边的回路。

为了简化问题，不妨找到任意两个相邻的点，把环断成链。因为最后的路径肯定会跨过这条边，所以枚举跨过这条边的两个端点更新答案即可。

此时有个暴力的做法，设 $f[k][i][j]$ 为恰好 $k$ 条边，从 $i$ 走到 $j$ 的最长路，转移式有： $\begin{aligned} f[1][i][j]&=dis(i,j)\\ f[k+1][i][j]&=\max_lf[k][i][l]+f[1][l][k] \end{aligned}$
这个可以矩阵快速幂加速，时间复杂度 $\mathcal O(n^3\log k)$ 。

观察式子形态，唯一可优化的就是用四边形不等式。所以我们试图证明对于任意 $a\leq b\leq c\leq d$ 满足 $dis(a,d)+dis(b,c)\leq dis(a,c)+dis(b,d)$ 。

我们在平面上依次连接 $a,b,c,d$ 并让 $ac$ 和 $bd$ 交于点 $O$ ，可得 $aO+Od\geq ad,cO+Ob\geq cb$ 。两式加起来，就有 $ac+bd\geq ad+bc$ 满足四边形不等式。而两个满足四边形不等式的状态合并起来仍然满足四边形不等式，于是我们可以用决策单调性解决这个问题。时间复杂度 $\mathcal O(n^2\log n)$ 。

#include <bits/stdc++.h>
#define db double
using namespace std;
const int N = 2e3 + 9;
db dp[12][N][N];
db x[N], y[N], ans[2][N][N], res;
int g[N][N];
db dis(int i, int j) {
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
int main() {
    int n, k;
    cin >> n >> k;
    k--;
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &x[i], &y[i]);
    for (int i = 1; i <= n; i++) {
        g[i][i] = i;
        for (int j = i + 1; j <= n; ++j) {
            dp[0][i][j] = dis(i, j);

            if (k & 1)
                ans[0][i][j] = dp[0][i][j];
        }
    }
    int op = 0;
    for (int m = 1; m < 12; ++m) {
        if (!(k >> m))
            break;
        for (int len = 2; len <= n; ++len)
            for (int i = 1, j = len; j <= n; i++, j++)
                for (int c = g[i][j - 1]; c <= g[i + 1][j]; ++c)
                    if (dp[m][i][j] < dp[m - 1][i][c] + dp[m - 1][c][j]) {
                        dp[m][i][j] = dp[m - 1][i][c] + dp[m - 1][c][j];
                        g[i][j] = c;
                    }
        if (((k >> m) & 1) == 0)
            continue;
        memset(ans[!op], 0, sizeof ans[!op]);
        for (int len = 2; len <= n; ++len)
            for (int i = 1, j = len; j <= n; i++, j++)
                for (int c = g[i][j - 1]; c <= g[i + 1][j]; ++c)
                    if (ans[!op][i][j] < ans[op][i][c] + dp[m][c][j]) {
                        ans[!op][i][j] = ans[op][i][c] + dp[m][c][j];
                        g[i][j] = c;
                    }
        op ^= 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 2; j <= n; ++j)
            res = max(res, ans[op][i][j] + dp[0][i][j]);
    printf("%.6lf\n", res);
}

C

由 $\text{nim}$ 游戏相关知识可知，先手必胜的条件是所有堆石头数量的异或和不为 $0$ ，而必败方必定有一种方案使得在之后每步操作中双方都只能取一个石头。通过这一结论不难推出答案：若先手必胜，则先手会在使剩余石头的数量异或和为 $0$ 的前提下尽可能多的取石头，游戏轮数为第一轮操作后剩余石头数量 $+1$ ，首轮操作方案数为满足上述条件的取法数；若先手必败，则游戏轮数等于石头的总数量，首轮操作方案数为满足从堆中取出一个石头后下一步只能取一个石头的堆数，听起来貌似只能 $O(n^2)$ 计算，但是取出一个石头后的异或和只有 $\log a$ 种可能，只需判断这 $\log a$ 种异或和是否满足条件即可。

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N], sm[31], n, t_case, vis[31];
signed main() {
    scanf("%d", &t_case);

    while (t_case--) {
        scanf("%d", &n);
        memset(sm, 0, sizeof sm);
        memset(vis, 0, sizeof vis);
        ll sum = 0;
        int xsum = 0;

        for (int i = 1; i <= n; ++i)
            cin >> a[i], xsum ^= a[i], sum += a[i];

        if (!xsum) {
            for (int i = 1; i <= n; ++i) {
                int x = a[i];
                int tt = 0;

                while (x) {
                    int t = __lg(x & -x);
                    ++tt;

                    if (tt > 1)
                        vis[t] = 1;
                    else
                        sm[t]++;

                    x ^= x & -x;
                }
            }

            int s2 = 0;

            for (int i = 0; i <= 30; ++i)
                if (!vis[i])
                    s2 += sm[i];

            printf("%lld %d\n", sum, s2);
        } else {
            int s2 = 0;
            int mx = 0;

            for (int i = 1; i <= n; ++i) {
                if (a[i] - (a[i]^xsum) > mx) {
                    mx = a[i] - (a[i] ^ xsum);
                    s2 = 1;
                } else if (-(a[i]^xsum) + a[i] == mx)
                    s2++;
            }

            printf("%lld %d\n", sum - mx + 1, s2);
        }
    }

    return 0;
}

D

对于一种合成方式，连一条从 $b_i$ 到 $d_i$ 的边，边权为 $\frac{c_i}{a_i}$ 。若不考虑 $m$ ，那是否能无限造出一个物品等价于图中是否有乘积大于 $1$ 的环。但是由于乘积太大，不妨化乘为加，对所有边权取 $\log$ ，那么一次判定就变成了 $\rm SPFA$ 判负环。

而答案 $w$ 具有单调性，所以再在外面套一层二分即可。时间复杂度 $\mathcal O(n^2\log n)$ 。

#include <bits/stdc++.h>
#define double long double
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
const int N = 2e3 + 10;
const double eps = 1e-8;
int n, m;
int last[N], to[N], pre[N], cnt;
double val[N], V[N], dis[N];
void add(int x, int y, double w) {
    to[++cnt] = y;
    val[cnt] = w;
    pre[cnt] = last[x];
    last[x] = cnt;
}
queue<int> q;
int vis[N];
bool check(double mul) {
    for (int i = 1; i <= cnt; i++)
        V[i] = -log(val[i] * mul);
    while (!q.empty())
        q.pop();
    for (int i = 1; i <= n; i++)
        dis[i] = 0, q.push(i), vis[i] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = last[x]; i; i = pre[i]) {
            int y = to[i];
            double w = V[i];
            if (dis[x] + w < dis[y]) {
                dis[y] = dis[x] + w;
                ++vis[y];
                if (vis[y] > n)
                    return 0;
                q.push(y);
            }
        }
    }
    return 1;
}
signed main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int a = read(), b = read(), c = read(), d = read();
        add(b, d, 1.0 * c / a);
    }
    double l = 0, r = 1;
    while (r - l > eps) {
        double m = (l + r) / 2;

        if (check(m))
            l = m;
        else
            r = m;
    }
    printf("%.10Lf\n", l);
    return 0;
}

E

恰好就要联想到容斥。根据二项式反演： $f(n)=\sum_{i=n}^m\binom{i}{n}g(i)\Longleftrightarrow g(n)=\sum_{i=n}^m (-1)^{i-n}\binom{i}{n}f(i)$
其中 $f(i)$ 表示钦定出现 $i$ 个 bit方案数， $g(i)$ 表示恰好出现 $i$ 个 bit 的方案数。

我们把 bit 三位字符看成一个字符。那么钦定 $i$ 个 bit 位置的方案数就为 $\binom{n-2i}{i}$ 。而剩下的每个位置可以放 $26$ 个字符，所以再乘上 $26^{n-3i}$ 。所以 $f(i)=26^{n-3i}\binom{n-2i}{i}$

对于反演式子，直接做是 $n^2$ 的，而用 $\rm NTT$ 加速即可做到 $\mathcal O(n\log n)$ 的复杂度。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e6 + 9;
const int p = 998244353;
const int g = 3;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int ig;
int lim = 1, l;
int r[N];
int inv(int x, int base = p - 2) {
    int res = 1;
    while (base) {
        if (base & 1)
            res = res * x % p;
        x = x * x % p;
        base >>= 1;
    }
    return res;
}
void NTT(int *a, const int &op) {
    for (int i = 1; i <= lim - 1; i++)
        if (i < r[i])
            swap(a[i], a[r[i]]);
    for (int mid = 1; mid < lim; mid <<= 1) {
        int len = mid << 1, wn = inv(op ? ig : g, (p - 1) / len);
        for (int j = 0; j < lim; j += len) {
            int w = 1;
            for (int k = 0; k < mid; k++, (w *= wn) %= p) {
                int x = a[j + k], y = w * a[j + mid + k] % p;
                a[j + k] = (x + y) % p, a[j + mid + k] = (x - y + p) % p;
            }
        }
    }
    if (!op)
        return;
    int invn = inv(lim);
    for (int i = 0; i < lim; i++)
        (a[i] *= invn) %= p;
}
int a[N], b[N];
int fac[N], ifac[N];
void init(int n = N - 9) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % p;
    ifac[n] = inv(fac[n]);
    for (int i = n - 1; i >= 0; i--)
        ifac[i] = ifac[i + 1] * (i + 1) % p;
}
int C(int n, int m) {
    return n >= m && m >= 0 ? fac[n] * ifac[m] % p * ifac[n - m] % p : 0;
}
signed main() {
    ig = inv(g);
    int n = read(), m = n;
    init();
    for (int i = 0; i <= n; i++) {
        a[i] = ifac[i];
        if (i % 2)
            a[i] = (p - a[i]) % p;
        if (n >= 3 * i)
            b[i] = C(n - 2 * i, i) * inv(26, n - 3 * i) % p;
        else
            b[i] = 0;
        (b[i] *= fac[i]) %= p;
    }
    reverse(a, a + 1 + n);
    while (lim <= n + m)
        lim <<= 1, l++;
    for (int i = 1; i <= lim - 1; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    NTT(a, 0), NTT(b, 0);
    for (int i = 0; i <= lim - 1; i++)
        ((a[i] *= b[i]) += p) %= p;
    NTT(a, 1);
    for (int i = n; i <= 2 * n; i++)
        printf("%lld ", a[i]*ifac[i - n] % p);
    return 0;
}

F

先考虑问题的弱化版，然后一步步增加限制。

若 $t$ 不增加字符，并且 $s$ 只会加减一个字符：对于 $t$ 建 $\rm trie$ ，预处理每个点的答案，每次在 $\rm trie$ 上直接移动。
若 $t$ 不增加字符：每次 $s$ 删除可以倍增往上跳。因为加入的都是相同的字符，所以记录 $ed_{i,c}$ 表示节点 $i$ 一直走字符 $c$ 到达的地方，再倍增跳回来即可。
对于 $t$ 的增加操作，可以离线建 $\rm trie$ ，每次移动使用线段树维护 $\rm dfn$ 区间加贡献答案。

注意可能会跳出 $\rm trie$ 。总时间复杂度 $\mathcal O((n+q)\log n)$ 。

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int N = 4e5 + 9;
string s, t[N];
char S[N];
int ch[N][26];
int fa[N][20], son[20][N];
int idx = 1, n, q;
int dfn[N], re[N], sz[N], op[N], c[N];
int id, last[N];
long long K[N];
void insert(int &x, int y) {
    if (!ch[x][y])
        ch[x][y] = ++idx;

    x = ch[x][y];
}
void add(int x, int v) {
    while (x < N)
        c[x] += v, x += lowbit(x);
}
int get(int x, int res = 0) {
    while (x)
        res += c[x], x -= lowbit(x);

    return res;
}
void dfs(int x) {
    sz[x] = 1;
    dfn[x] = ++id;
    re[id] = x;

    for (int i = 1; i < 20; ++i)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];

    for (int i = 0; i < 26; ++i)
        if (ch[x][i]) {
            fa[ch[x][i]][0] = x,
                              dfs(ch[x][i]),
                              sz[x] += sz[ch[x][i]];
        }
}
int getfa(int x, int k) {
    for (int i = 19; i >= 0; --i)
        if (k >> i & 1)
            x = fa[x][i];

    return x;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q >> s;

    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
        last[i] = 1;

        for (auto it : t[i])
            insert(last[i], it - 'a');
    }

    for (int i = 1; i <= q; ++i) {
        cin >> op[i];

        if (op[i] == 1)
            cin >> K[i] >> S[i], insert(last[K[i]], S[i] - 'a');
        else if (op[i] == 2)
            cin >> K[i];
        else if (op[i] == 3)
            cin >> K[i] >> S[i];
    }

    dfs(1);
    int now = 1;
    long long ex = 0;
    int nt = -1;

    for (int i = 1; i <= idx; ++i)
        for (int j = 0; j < 26; ++j)
            son[0][ch[i][j]] = ch[ch[i][j]][j];

    for (int k = 1; k < 20; ++k)
        for (int i = 1; i <= idx; ++i)
            son[k][i] = son[k - 1][son[k - 1][i]];

    for (auto it : s) {
        int y = it - 'a';

        if (ex || ch[now][y] == 0) {
            if (!ex)
                nt = y;

            ++ex;
        } else
            now = ch[now][y];
    }

    for (int i = 1; i <= n; ++i) {
        last[i] = 1;

        for (auto it : t[i])
            last[i] = ch[last[i]][it - 'a'];

        add(dfn[last[i]], 1);
    }

    for (int i = 1; i <= q; ++i) {
        if (op[i] == 1) {
            int x = K[i], y = S[i] - 'a';
            add(dfn[last[x]], -1);
            last[x] = ch[last[x]][y];
            add(dfn[last[x]], 1);
        } else if (op[i] == 2) {
            long long k = K[i], y = min(ex, k);
            ex -= y, k -= y;

            if (ex == 0 && k)
                now = getfa(now, k);
        } else if (op[i] == 3) {
            int y = S[i] - 'a', k = K[i];

            if (!k)
                continue;

            if (ex)
                ex += k;
            else {
                if (!ch[now][y]) {
                    ex += k;
                    nt = y;
                    continue;
                }

                now = ch[now][y], --k;

                for (int i = 19; i >= 0; --i)
                    if (k >= (1 << i) && son[i][now])
                        now = son[i][now], k -= 1 << i;

                if (k)
                    ex += k, nt = y;
            }
        } else {
            if (ex) {
                int x = dfn[now];

                for (int j = nt - 1; j >= 0; --j)
                    if (ch[now][j]) {
                        x = dfn[ch[now][j]] + sz[ch[now][j]] - 1;
                        break;
                    }

                printf("%d\n", get(x));
            } else
                printf("%d\n", get(dfn[now] - 1));
        }
    }

    return 0;
}

G

我们取一个阈值 $B$ ，将 $[1,n]$ 分成 $\lceil\frac{n}{B}\rceil$ 段，每段从大到小输出，画图模拟可知 $LIS=\lceil\frac{n}{B}\rceil,LDS=B$ ，计算可得最优的 $B$ 为 $\lceil\sqrt n\rceil$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, t_case;
int main() {
    scanf("%d", &t_case);

    while (t_case--) {
        scanf("%d", &n);
        int B = ceil(sqrt(n));

        for (int l = 1; l <= n;) {
            int r = min(l + B - 1, n);

            for (int j = r; j >= l; --j)
                printf("%d ", j);

            l = r + 1;
        }

        putchar('\n');
    }

    return 0;
}

H

以下默认 $a$ 和 $b$ 已离散化，即值域为 $[1,2n]$ 。

先考虑 $a_i<b_i$ 的情况，将其看作一条 $[2a_i,2b_i)$ 的线段（乘 $2$ 的原因是一个人在某层下电梯后，这层的另外一个人可以上电梯，若不这样做则这两个人的线段会有交点），那么每个点被覆盖的次数就是电梯至少要经过这里的次数，设其为 $c1_i$ ，不妨设电梯每次到达的层数是单调不升的，那么满足 $\lceil\frac{c1_i}{m}\rceil=x$ 的最大的 $i$ 便是前 $x$ 次至少要到达的楼层。

对于 $a_i>b_i$ 的情况，以同样方法处理即可。

时间复杂度 $O(n\log n)$ ，效率瓶颈在于离散化的排序。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8e5 + 10;
int ans[N], b[N], bl, c1[N], c2[N], k, l[N], m, n, r[N];
ll sum;
int main() {
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", l + i, r + i);
        b[++bl] = l[i], b[++bl] = r[i];
    }

    sort(b + 1, b + bl + 1);
    bl = unique(b + 1, b + bl + 1) - b - 1;

    for (int i = 1; i <= n; ++i) {
        l[i] = lower_bound(b + 1, b + bl + 1, l[i]) - b;
        r[i] = lower_bound(b + 1, b + bl + 1, r[i]) - b;

        if (l[i] < r[i])
            ++c1[2 * l[i]], --c1[2 * r[i]];

        if (l[i] > r[i])
            ++c2[2 * l[i]], --c2[2 * r[i]];
    }

    for (int i = 1; i <= 2 * bl; ++i)
        c1[i] += c1[i - 1], ans[(c1[i] + m - 1) / m] = max(ans[(c1[i] + m - 1) / m], b[i + 1 >> 1]);

    for (int i = 2 * bl; i; --i)
        c2[i] += c2[i + 1], ans[(c2[i] + m - 1) / m] = max(ans[(c2[i] + m - 1) / m], b[i + 1 >> 1]);

    ans[n + 1] = 1;

    for (int i = n; i; --i)
        ans[i] = max(ans[i], ans[i + 1]), sum += 2 * (ans[i] - 1);

    printf("%lld", sum);
    return 0;
}

I

以下用 $m_1$ 表示 $k$ ，用 $m_2$ 表示 $d$ 。

先列出答案的式子 $Y_{i,j}^{new}=\frac{\sum\limits_{k=1}^{m_1}(a_{i,k} \sum\limits_{l=1}^n\sum\limits_{o=1}^{m_1}\frac{X_{l,o}Y_{l,j}}{|X_l|})}{|X_i|}$ ，发现里面的 $\sum\limits_{l=1}^n\sum\limits_{o=1}^{m_1}\frac{X_{l,o}Y_{l,j}}{|X_l|}$ 只和 $j$ 有关，因此枚举 $j$ ，令 $sum_k$ 表示 $\sum\limits_{l=1}^n\sum\limits_{o=1}^{m_1}\frac{X_{l,o}Y_{l,j}}{|X_l|}$ ，那么 $Y_{i,j}^{new}=\frac{\sum\limits_{k=1}^{m_1}a_{i,k}sum_{k}}{|X_i|}$ 。

预处理 $m_2$ 次 $sum$ ，大小为 $nm_1$ ，因此其时间复杂度为 $O(nm_1m_2)$ 。

计算 $Y_{i,j}^{new}$ 需要从 $1$ 到 $m_2$ 枚举 $j$ ，从 $1$ 到 $m_1$ 枚举 $k$ ，因此其时间复杂度为 $O(nm_1m_2)$ 。

故总时间复杂度为 $O(nm_1m_2)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long double ll;
const int M = 53, N = 1e4 + 10;
int a[N][M], b[N][M], m1, m2, n;
ll ans[N][M], len[N], sum[M];
int main() {
    scanf("%d%d%d", &n, &m1, &m2);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m1; ++j)
            scanf("%d", &a[i][j]), len[i] += (ll)a[i][j] * a[i][j];

        len[i] = sqrt(len[i]);

        for (int j = 1; j <= m1; ++j)
            sum[j] += a[i][j] / len[i];
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m2; ++j)
            scanf("%d", &b[i][j]);

    for (int i = 1; i <= m2; ++i) {
        for (int j = 1; j <= m1; ++j)
            sum[j] = 0;

        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= m1; ++k)
                sum[k] += a[j][k] / len[j] * b[j][i];

        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= m1; ++k)
                ans[j][i] += a[j][k] * sum[k];

            ans[j][i] /= len[j];
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m2; ++j)
            printf("%Lf ", ans[i][j]);

        putchar('\n');
    }

    return 0;
}

J

设 $b_i=c+id$ ，其中 $c$ 是首项， $d$ 是公差。

化简后，若把 $c$ 看成常量， $d$ 看成变量，那么是一个关于 $d$ 二次函数，可以直接用 $c$ 表达出极值。再代回原式，发现是一个关于 $c$ 的二次函数，又可以直接求出极值。但是注意精度误差。

当然，只要观察到枚举 $c$ 后的最优答案是个二次函数，也可以三分套三分解决，这个可以避免手动求极值。

#include <bits/stdc++.h>
#define int long long
#define F128 __float128
using namespace std;
const int N = 1e5 + 9;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int n, x[N];
signed main() {
    int T = read();
    while (T--) {
        n = read();
        for (int i = 1; i <= n; i++)
            x[i] = read();
        F128 A = 0, B = 0, s = 0, a = 0, b = 0, c = 0;
        for (int i = 1; i <= n; i++)
            B += (F128)i * x[i];
        s = (F128)n * (n + 1) / 6 * ((F128)2 * n + 1);
        A = -(F128)n * (n + 1) / 2;
        A /= s, B /= s;
        for (int i = 1; i <= n; i++)
            a += (F128)1 + (F128)i * i * A * A + (F128)2 * i * A;
        for (int i = 1; i <= n; i++)
            b += -(F128)2 * x[i] - (F128)2 * x[i] * i * A + (F128)i * i * 2 * A * B + (F128)2 * i * B;
        for (int i = 1; i <= n; i++)
            c += -(F128)2 * x[i] * i * B + (F128)x[i] * x[i] + (F128)i * i * B * B;
        printf("%.15Lf\n", (long double)(c - b * b * .25 / a));
    }

    return 0;
}

K

首先，一个括号序列合法的充要条件是，将 ( 看做 $1$ ，将 ) 看做 $-1$ ，那么序列的和为 $0$ 且最小前缀和 $\ge 0$ 。

定义 $f_{i,j,k}$ 为答案串中已经有 $i$ 个字符， $s$ 中前 $j$ 个字符是答案串的子序列，答案串的和为 $k$ 的方案数。

那么有以下四种转移（默认 $0\le i<n$ ）：

$i+1$ 位置放 (，且有 $j=n$ 或 $s_{j+1}\neq$ ( ，那么有转移 $f_{i,j,k}\rightarrow f_{i+1,j,k+1}$ 。
$i+1$ 位置放 )，且有 $j=n$ 或 $s_{j+1}\neq$ ) ，且 $k>0$ ，那么有转移 $f_{i,j,k}\rightarrow f_{i+1,j,k-1}$ 。
$i+1$ 位置放 (，且有 $j<n,s_{j+1}=$ ( ，那么有转移 $f_{i,j,k}\rightarrow f_{i+1,j+1,k+1}$ 。
$i+1$ 位置放 )，且有 $j<n,s_{j+1}=$ ) ，且 $k>0$ ，那么有转移 $f_{i,j,k}\rightarrow f_{i+1,j+1,k-1}$ 。

时间复杂度 $O(nm^2)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 210, mod = 1e9 + 7;
inline void add(int &x, int y) {
    if ((x += y) >= mod)
        x -= mod;
}
int m, n, t_case;
char s[N];
int main() {
    scanf("%d", &t_case);

    while (t_case--) {
        scanf("%d%d%s", &n, &m, s + 1);
        vector<vector<vector<int>>>f(m + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));
        f[0][0][0] = 1;

        for (int i = 0; i < m; ++i)
            for (int j = 0; j <= min(i, n); ++j)
                for (int k = 0; k <= i; ++k)
                    if (f[i][j][k]) {
                        if (k && (j == n || s[j + 1] != ')'))
                            add(f[i + 1][j][k - 1], f[i][j][k]);

                        if (k < m && (j == n || s[j + 1] != '('))
                            add(f[i + 1][j][k + 1], f[i][j][k]);

                        if (j < n) {
                            if (k && s[j + 1] == ')')
                                add(f[i + 1][j + 1][k - 1], f[i][j][k]);

                            if (k < m && s[j + 1] == '(')
                                add(f[i + 1][j + 1][k + 1], f[i][j][k]);
                        }
                    }

        printf("%d\n", f[m][n][0]);
    }

    return 0;
}

L

定义 $d_{i,j}$ 表示到达第 $i$ 个世界中的 $j$ 号点最少需要经过多少世界，初始化 $d_{i,1}=1,d_{i,j}=+\infty\ (j>1)$ 。

转移只有两种：

从某个世界原地不动到达下一个世界，需要用到的世界增加 $1$ ，因此有转移 $d_{i,j}+1\rightarrow d_{i+1,j}\ (i<n)$ 。
从某个世界通过一条边到达下一个世界，需要用到的世界增加 $1$ ，因此有转移 $d_{i,u}+1\rightarrow d_{i+1,v}\ (i<n, (u,v)\in E_i)$ 。

最后若 $\min{a_{i,n}}=+\infty$ 则输出 $-1$ ，否则输出 $\min{a_{i,n}}$ 。

时间复杂度 $O(nm+\sum l)$ ，空间复杂度使用滚动数组优化后可做到 $O(m)$ 。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, M = 2010;
int d[M], dd[M], l, m, n;
int main() {
    scanf("%d%d", &n, &m);
    memset(d, 0x3f, sizeof d);
    d[1] = 1;

    while (n--) {
        scanf("%d", &l);

        for (int i = 1; i <= m; ++i)
            if (i > 1 && i < m && d[i] != inf)
                ++d[i];

        memcpy(dd, d, sizeof d);

        while (l--) {
            int x, y;
            scanf("%d%d", &x, &y);
            dd[y] = min(dd[y], d[x]);
        }

        memcpy(d, dd, sizeof d);
    }

    printf("%d", d[m] == inf ? -1 : d[m]);
    return 0;
}

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(0) 回帖

加载中...

话题同步到我的动态回帖

【题解】"蔚来杯"2022牛客暑期多校训练营2

A

C

D

E

F

G

H

I

J

K

L

已采纳

精彩回帖

全部评论

等你来战

热门推荐