2022 牛客多校第二场 部分题解（DGJKL）

比赛链接：

G题 Link with Monotonic Subsequence（构造，打表，数学）

对于长度为 $nn$ 的排列 $\{p_n\}\backslash \{p\_n\backslash \}$，记该排列的价值为 $\max (f(p),g(p))\backslash max(f(p),g(p))$，其中 $f(p)f(p)$ 表示排列 $pp$ 的最长上升子序列长度（$g(p)g(p)$ 就是下降）。

给定正整数 $nn$，求出长度为 $nn$ 的所有排列的价值的最小值是多少，并输出其中一种排列。

$T\le 10^3,n\le 10^6,\sum n\le 10^{6}T\backslash leq\; 10^3,n\backslash leq\; 10^6,\backslash sum\; n\backslash leq\; 10^6$

比赛时候直接打表发现，价值最小值为 $t=\lceil \sqrt{n}\rceil t=\{\backslash lceil\backslash sqrt\{n\}\backslash rceil\}$。至于构造，就类似 $3,2,1,6,5,4,9,8,7\{3,2,1,6,5,4,9,8,7\}$ 即可（$n=9,t=3n=9,t=3$，每块内部 $tt$ 个倒置元素，一共分成 $\lfloor \frac{n}{t}\rfloor \backslash lfloor\backslash frac\{n\}\{t\}\backslash rfloor$）。

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, ans[N];
void solve() {
    scanf("%d", &n);
    int t = sqrt(n + 0.5);
    if (t * t != n) ++t;
    for (int i = 1; i <= n; ++i) ans[i] = i;
    for (int L = 1; L <= n; L += t) {
        int R = min(n, L + t - 1);
        reverse(ans + L, ans + R + 1);
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    puts("");
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

证明：直接参照 std 题解，假设 $(a_i,b_i)(a\_i,b\_i)$ 分别为以 $p_{i}p\_i$ 为结尾的最长上升/下降子序列的长度构成的二元组，那么若存在 ，则：

1. 当 时，$a_j\ge a_i+1a\_j\backslash geq\; a\_i+1$
2. 当 $p_i>p_{j}p\_i>p\_j$ 时，$b_j\ge b_i+1b\_j\backslash geq\; b\_i+1$

这意味着，所有位置所对应二元组互不相同。

如果要求构造一个价值不超过 $tt$ 的排列，那么这个排列的最长长度就是 $t^{2}t^2$：也就是二元组分别为：$(1,1),(1,2),\cdots ,(1,t),(2,1),\cdots ,(t-1,t),(t,t)(1,1),(1,2),\backslash cdots,(1,t),(2,1),\backslash cdots,(t-1,t),(t,t)$，总计 $t^{2}t^2$ 个（构造方式也类似上面的分块）。

D题 Link with Game Glitch（负环）

在游戏中存在 $nn$ 种物品和 $mm$ 种兑换规则：用 $k\ast a_{i}k*a\_i$ 个物品 $b_{i}b\_i$ 可以兑换 $k\ast c_{i}k*c\_i$ 个物品 $d_{i}d\_i$，$kk$ 可以是任意正实数（也就是说，兑换是连续的，不要求一定是整数）。

一天，管理员发现有人的物品多的离谱，他意识到一定是规则出了问题，有人使用漏洞在无限量的兑换物品。不过，他现在不想去具体找哪些规则出了问题，而是想到了另一个办法：引入加权系数 $ww$（一个 $(0,1)(0,1)$ 之间的浮点数），之后每次兑换只能到原来的 $ww$ 倍的物品（即 $kaka$ 个 $bb$ 兑换 $kwckwc$ 个物品 $dd$）。

问， $ww$ 的最大值是多少？

$2\le n\le 10^3,2\le m\le 2\ast 10^3,1\le a_i,c_i\le 10^3,b_i≠d_{i}2\backslash leq\; n\backslash leq\; 10^3,2\backslash leq\; m\backslash leq\; 2*10^3,1\backslash leq\; a\_i,c\_i\backslash leq\; 10^3,b\_i\backslash not=d\_i$，保证 $w=1w=1$ 时一定存在漏洞。

我们将第 $ii$ 条规则改成：1 个物品 $b_{i}b\_i$ 可以兑换 $\frac{c}{a}\backslash frac\{c\}\{a\}$ 个物品 $d_{i}d\_i$，那么我们就可以将其转化为一个有向带权图。游戏中存在漏洞，说明图中存在一个边权积大于 1 的环。显然，$ww$ 可以二分，每次直接 check 环是否存在即可。

边权积不太好写（一个是要改板子，还有一个就是边权积很容易爆 long long 甚至 double），所以我们可以直接取 log，这样就转化为了求正环的问题（如果所有边取反，就变成了求负环）。

浮点数二分大概要迭代 30 次以上，然后 Bellman-Ford 算法的复杂度是 $O(nm)O(nm)$，担心过不去的可以换 SPFA。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
struct Edge { int u, v; double w; };
vector<Edge> edges, ed;
int n, m;
double dis[N];
bool solve(double x) {
    //build
    ed.clear();
    for (auto e : edges)
        ed.push_back((Edge){e.u, e.v, log(e.w * x)});
    //bellman-ford
    //没错，我初始化的时候设成-1e18，然后WA了
    //我差点还以为我算法写错了，没想到就是浮点误差
    for (int i = 1; i <= n; ++i) dis[i] = -1e9;
    dis[1] = 0;
    for (int k = 1; k < n; ++k)
        for (auto e : ed)
            dis[e.v] = max(dis[e.v], dis[e.u] + e.w);
    //check
    for (auto e : ed)
        if (dis[e.v] < dis[e.u] + e.w) return false;
    return true;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        edges.push_back((Edge){b, d, (1.0 * c) / a});
    }
    double L = 0, R = 1;
    while (L + 1e-7 < R) {
        double mid = (L + R) / 2;
        if (solve(mid)) L = mid; else R = mid;
    }
    printf("%.8f", L);
    return 0;
}

J题 Link with Arithmetic Progression（最小二乘法，数学）

给定一个数列 $\{a_n\}\backslash \{a\_n\backslash \}$，现在要求尝试对每一位置的数都进行一定修改，使得新数列变成等差数列（可以是浮点数）。

记位置 $ii$ 上的数从 $a_{i}a\_i$ 改成了 $a_i^{\mathrm{\prime }}a\_i\text{'}$，那么总代价为 ${\sum }_{i=1}^n(a_i-a_i^{\mathrm{\prime }}{)}^2\backslash sum\backslash limits\_\{i=1\}^n(a\_i-a\_i\text{'})^2$。

试求出最小代价。

$T\le 10^3,\mathrm{\mid }{a}_i\mathrm{\mid }\le 10^9,n\le 10^5,\sum n\le 10^{6}T\backslash leq\; 10^3,|a\_i|\backslash leq\; 10^9,n\backslash leq\; 10^5,\backslash sum\; n\backslash leq\; 10^6$

我一开始看完后没开，两点半的时候发现过的人贼多，再重新看一下，离谱，原来是可以浮点数的，那没事了。

我们假定拟合成直线 $y=ax+by=ax+b$，那么总误差为 $f(a,b)={\sum }_{i=1}^n(a{x}_i+b-y_i{)}^{2}f(a,b)=\backslash sum\backslash limits\_\{i=1\}^\{n\}(ax\_i+b-y\_i)^2$。

那么，我们求这个二元函数极值点（我估计应该是都在 0 的地方，虽然已经把高数忘干净了），得：

化简可得

这样，就变成了一个一元二次方程的求解问题（实际上，这就是最小二乘法）。

这题贼卡精度，我是用上了高斯消元的主元更换法，外加 long double 才勉强过关。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
namespace GTI {
    char gc(void) {
        const int S = 1 << 16;
        static char buf[S], *s = buf, *t = buf;
        if (s == t)
            t = buf + fread(s = buf, 1, S, stdin);
        if (s == t)
            return EOF;
        return *s++;
    }
    int gti(void) {
        int a = 0, b = 1, c = gc();
        for (; !isdigit(c); c = gc())
            b ^= (c == '-');
        for (; isdigit(c); c = gc())
            a = a * 10 + c - '0';
        return b ? a : -a;
    }
}
using GTI::gti;
const int N = 100010;
int t[N];
//
long double a[10][10], ans[10];
void calc(int n) {
    const long double eps = 1e-8;
    for (int i = 1; i <= n; ++i) {
        int r = i;
        for (int j = i + 1; j <= n; ++j)
            if (abs(a[r][i]) < abs(a[j][i])) r = j;
        if (abs(a[r][i]) < eps) return;
        if (i != r) swap(a[i], a[r]);
        long double div = a[i][i];
        for (int j = i; j <= n + 1; ++j) a[i][j] /= div;
        for (int j = i + 1; j <= n; ++j) {
            div = a[j][i];
            for (int k = i; k <= n + 1; ++k)
                a[j][k] -= a[i][k] * div;
        }
    }
    for (int i = n; i >= 1; i--) {
        ans[i] = a[i][n + 1];
        for (int j = i + 1; j <= n; ++j)
            ans[i] -= a[i][j] * ans[j];
    }
    return;
}
long double solve() {
    int n = gti();
    for (int i = 1; i <= n; ++i)
        t[i] = gti();
    long double A1 = 0, B1 = n, C1 = 0, A2 = 0, B2 = 0, C2 = 0;
    for (LL i = 1; i <= n; ++i) {
        A1 += i, C1 += t[i];
        A2 += i * i, B2 += i, C2 += i * t[i];
    }
    //calc
    a[1][1] = A1, a[1][2] = B1, a[1][3] = C1;
    a[2][1] = A2, a[2][2] = B2, a[2][3] = C2;
    calc(2);
    long double k = ans[1], b = ans[2];
    long double ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += (k * i + b - t[i]) * (k * i + b - t[i]);
    return ans;
}
int main()
{
    int T = gti();
    while (T--) printf("%.16Lf\n", solve());
    return 0;
}

K题 Link with Bracket Sequence I（线性DP）

给定一个长度为 $nn$ 的括号串 $aa$，问有多少长度为 $mm$ 的合法括号串 $bb$，满足 $aa$ 是 $bb$ 的子串（不要求连续）。

$T\le 100,n\le m\le 200,\sum m\le 10^{3}T\backslash leq\; 100,n\backslash leq\; m\backslash leq\; 200,\backslash sum\; m\backslash leq\; 10^3$

以前没咋注意过，这一次直接栽在复杂度上了：我一开始觉得规模是 $10^{3}10^3$，只能 $O(n^2)O(n^2)$ 去做，没想到实际上应该这么算：满的数据至多 $\frac{1000}{200}=5\backslash frac\{1000\}\{200\}=5$ 组，那么 $5\ast (200^3)=4\ast 10^{7}5*(200^3)=4*10^7$ 也是可以的，因此只要 $O(n^3)O(n^3)$ 算法即可（以前 CF 上面都是 $10^{5}10^5$ 和 $10^{6}10^6$ 的区别，都差不多，就没咋关注过这玩意的计算，绷不住了家人们）。

$O(n^3)O(n^3)$ 或者 $O(n^2)O(n^2)$ 的算法，在序列上，那基本就是一个线性 DP 了。我们考虑前两维分别表示 $bb$ 的前 $ii$ 位和 $aa$ 的前 $jj$ 位匹配，但是这样子会漏掉不少信息（导致重复）。

想了一下，为了保证 $bb$ 合法，不妨再加一个维度 $kk$，记录当前 $bb$ 中左右括号的差值（$k\ge 0k\backslash geq\; 0$）。

在此基础上，我们构思一下状态转移方程：

f[0][0][0] = 1;
for (int i = 1; i <= m; i++)
    for (int j = 0; j <= i; j++)
        for (int k = 0; k <= i; k++) {
            if (k > 0) {
                if (s[j] == '(') f[i][j][k] += f[i - 1][j - 1][k - 1];
                else f[i][j][k] += f[i - 1][j][k - 1];
            }
            if (s[j] == ')') f[i][j][k] += f[i - 1][j - 1][k + 1];
            else f[i][j][k] += f[i - 1][j][k + 1];
        }

这个方程是枚举 $bb$ 的第 $ii$ 位填哪种括号（我之前是枚举 $bb$ 的第 $ii$ 位是否匹配，不过那个方式似乎会重复），对于意料外的边界条件就直接得到 0，时间复杂度 $O(m^3)O(m^3)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 210;
const int mod = 1e9 + 7;
int n, m, f[N][N][N];
char s[N];
int solve() {
    scanf("%d%d%s", &n, &m, s + 1);
    memset(f, 0, sizeof(f));
    f[0][0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= i; j++)
            for (int k = 0; k <= i; k++) {
                if (k > 0) {
                    if (s[j] == '(') f[i][j][k] += f[i - 1][j - 1][k - 1];
                    else f[i][j][k] += f[i - 1][j][k - 1];
                    f[i][j][k] %= mod;
                }
                if (s[j] == ')') f[i][j][k] += f[i - 1][j - 1][k + 1];
                else f[i][j][k] += f[i - 1][j][k + 1];
                //
                f[i][j][k] %= mod;
            }
    return f[m][n][0];
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        printf("%d\n", solve());
    return 0;
}

L题 Link with Level Editor I（线性DP）

给定 $nn$ 个世界，每个世界都有一张 $mm$ 点的有向图。

我们从第一个世界的一号点出发，然后可以走到（这张图中）相邻的点，或者呆在原地不动，随后你便会被传送到下一个世界的该位置。当目前所处世界就是最后一个世界时，流程结束，你此时所在节点就是你的最终位置（假设你在第 $n-1n-1$ 个世界里面走到了 $xx$ 点，然后传送到了第 $nn$ 个世界的 $xx$ 点，随后你走到了相邻的 $yy$ 点，因为是最后一个世界，所以你不会被继续传送，因而你的最终位置就是 $yy$）。

问，我们想要从中选取连续的一段，使得我们从这一段的第一个世界开始，然后到最后一个世界时，能够经过 $mm$ 点，问段的最短长度（不存在则输出 -1）。

$n\le 10^4,m\le 2\ast 10^{3}n\backslash leq\; 10^4,m\backslash leq\; 2*10^3$，图的边的总数不超过 $10^{6}10^6$

注意到一个性质：如果 $[l,r][l,r]$ 满足要求，那么对于 $l^{\mathrm{\prime }}\le l\le r\le r^{\mathrm{\prime }}l\text{'}\backslash leq\; l\backslash leq\; r\backslash leq\; r\text{'}$，区间 $[l\mathrm{’},r^{\mathrm{\prime }}][l’,r\text{'}]$ 同样可以（呆在点 $11$ 一直走到世界 $ll$，然后走到世界 $rr$ 的位置 $mm$，随后继续待着不动就完事了），那岂不是可以二分或者双指针？（不知道是不是，但我看似乎没人这么写，不知道是不是因为不好维护）

比赛完才发现，这是套着一个图论外壳的线性 DP（两个维度分别表示当前世界数和所在位置，图只是为了描述转移关系罢了），记 $d{p}_{i,j}dp\_\{i,j\}$ 为到达世界 $ii$ 的位置 $jj$ 所需要的最初世界位置（或者记录最短的世界段长度，下面的代码采用前者），那么，转移方向一共有两条：

1. 从前世界的 $jj$ 转移过来
2. 从前世界的 $xx$ 转移到本世界的 $yy$，然后从本世界的 $yy$ 走到世界 $jj$

注意第二条，需要对 $y=1y=1$ 特判一下（因为起点就是 $11$，不需要额外从前一个世界转移过来）。

复杂度 $O(nm)O(nm)$，空间上需要滚动数组优化一下。

#include <bits/stdc++.h>
using namespace std;
const int M = 2010;
int n, m, f[M], g[M];
int main() {
    scanf("%d%d", &n, &m);
    int ans = n + 1;
    for (int i = 1; i <= n; i++) {
        f[1] = i;
        //我之前还在想要不要执行以下g=f的操作来着
        //然后想起来，本来就有f=g，那没事了
        int l, u, v;
        scanf("%d", &l);
        while (l--) {
            scanf("%d%d", &u, &v);
            g[v] = max(g[v], f[u]);
        }
        if (g[m]) ans = std::min(ans, i - g[m] + 1);
        for (int j = 1; j <= m; j++) f[j] = g[j];
    }
    printf("%d\n", ans > n ? -1 : ans);
    return 0;
}

顺便贴一下记录长度的那种 DP：

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = 2010;
const int INF = 0x3f3f3f3f;
int n, m, dp[2][M];
vector<int> G[M];
void buildGraph() {
    for (int i = 1; i <= m; ++i) G[i].clear();
    int T, x, y;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(dp, 0x3f, sizeof(dp));
    int ans = INF;
    for (int i = 1; i <= n; ++i) {
        //不动，从上一个世界直接转移过来
        for (int x = 1; x <= m; ++x)
            dp[i % 2][x] = dp[(i - 1) % 2][x] + 1;
        //转移过来后在图上走一步
        buildGraph();
        for (int x = 1; x <= m; ++x)
            for (int y : G[x])
                dp[i % 2][y] = min(dp[i % 2][y], dp[(i - 1) % 2][x] + 1);
        //直接以这个世界作为起点
        dp[i % 2][1] = 1;
        for (int y : G[1])
            dp[i % 2][y] = min(dp[i % 2][y], 1);
        //更新答案
        ans = min(ans, dp[i % 2][m]);
    }
    printf("%d", ans < INF ? ans : -1);
    return 0;
}