牛客多校第二场补题记录（签到合集）

D Link with Game Glitch

题意：给定 $nn$ 个物品和 $mm$ 种物品合成方式 $(a,b,c,d)(a,b,c,d)$：$kaka$ 个 $bb$ 物品合成 $kckc$ 个 $dd$ 物品，$k\in {\mathbb{R}}^{+}k\; \backslash in\; \backslash R^+$。原定方式会导致出现无穷多个物品，现在需要求出最大的参数 $ww$，使得每个合成方式均变成 $(a,b,wc,d)(a,b,wc,d)$。求最大的实数 $ww$。$n,m,a,c\le 1\times 10^{3}n,m,a,c\; \backslash leq\; 1\backslash times\; 10^3$。

解法：将合成方式抽象成有向图，边权为 ${\displaystyle \frac{c}{a}}\backslash dfrac\{c\}\{a\}$，原题即是找到最大的 $ww$ 使得图上边权都变成 ${\displaystyle \frac{wc}{a}}\backslash dfrac\{wc\}\{a\}$，图上无边权乘积超过 $11$ 的环。由于边权乘积太大，因而考虑取对数，则题意变成边权为 $\log c-\log a\backslash log\; c-\backslash log\; a$，求最大的 $\log w\backslash log\; w$ 使得图上无正环。显然 $ww$ 有单调性，因而二分答案然后使用 spfa 判断正环是否存在即可。复杂度 $\mathcal{O}(nm\log w)\backslash mathcal\; O(nm\; \backslash log\; w)$。

#include <bits/stdc++.h>
using namespace std;
const long double inf = 1e12;
const int M = 2000, N = 1000;
struct line
{
    int from;
    int to;
    long double v;
    int next;
};
line que[M + 5];
int cnt, headers[N + 5];
void add(int from, int to, long double v)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].v = v;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
bool spfa(int n, long double w)
{
    vector<int> vis(n + 1, 0), times(n + 1, 0);
    vector<long double> dis(n + 1, -inf);
    queue<int> q;
    for (int i = 1; i <= n;i++)
    {
        q.push(i);
        vis[i] = 1;
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = headers[u]; i; i = que[i].next)
            if (dis[que[i].to] < dis[u] + w + que[i].v)
            {
                dis[que[i].to] = dis[u] + w + que[i].v;
                times[que[i].to] = times[u] + 1;
                if (vis[que[i].to] == 0)
                {
                    vis[que[i].to] = 1;
                    q.push(que[i].to);
                }
                if (times[que[i].to] > n)
                    return false;
            }
    }
    return true;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, b, d; i <= m;i++)
    {
        long double a, c;
        scanf("%Lf%d%Lf%d", &a, &b, &c, &d);
        add(b, d, log2(c) - log2(a));
    }
    long double left = 1.0 / 1000, right = 1;
    for (int times = 1; times <= 50;times++)
    {
        long double mid = (left + right) / 2;
        if (!spfa(n, log2(mid)))
            right = mid;
        else
            left = mid;
    }
    printf("%.15Lf", (left + right) / 2);
    return 0;
}

G Link with Monotonic Subsequence

题意：构造一个长度为 $nn$ 的排列，使得其最长上升子序列和最长下降子序列长度的最大值尽可能小。

解法：考虑如下的构造：$(k,k-1,k-2,\cdots ,1),(2k,2k-1,2k-2,\cdots ,k+1),\cdots ,(n,n-1,\cdots ,\lfloor {\displaystyle \frac{n}{k}}\rfloor k+1)(k,k-1,k-2,\backslash cdots,1),(2k,2k-1,2k-2,\backslash cdots,k+1),\backslash cdots,\backslash left\; (n,n-1,\backslash cdots,\backslash left\; \backslash lfloor\; \backslash dfrac\{n\}\{k\}\backslash right\; \backslash rfloor\; k+1\; \backslash right)$，则答案为 $\max (k,\lceil {\displaystyle \frac{n}{k}}\rceil )\backslash max(k,\backslash left\; \backslash lceil\; \backslash dfrac\{n\}\{k\}\backslash right\; \backslash rceil)$。因而取 $k=\lceil \sqrt{n}\rceil k=\backslash left\; \backslash lceil\; \backslash sqrt\{n\}\; \backslash right\; \backslash rceil$ 即可。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define LF long double
using namespace std;
const int N=1e6+3;
int n,a[N];
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
int main()
{
	int t=in();
	while(t--){
		n=in();
		int x=ceil(sqrt(n));
		for(int i=1;(i-1)*x<n;++i){
			int cnt=0;
			for(int j=(i-1)*x+1;j<=min(i*x,n);++j)
			  a[++cnt]=j;
			reverse(a+1,a+cnt+1);
			for(int j=1;j<=cnt;++j) printf("%d ",a[j]);
		}
		puts("");
	}
    return 0;
}

H Take the Elevator

题意：有 $nn$ 个人要坐电梯，第 $ii$ 个人要从 $a_{i}a\_i$ 坐到 $b_{i}b\_i$，电梯有容量限制 $mm$，且电梯下行时想恢复上行，必须先下到 $11$ 层。问运输完这些人最少需要多少时间。$n,m\le 2\times 10^{5}n,m\; \backslash leq\; 2\backslash times\; 10^5$。

解法：将所有人分成两类：从低到高和从高到低的，分开考虑。从上到下的可以反转过来变成从下到上的。

对于电梯的一次上行，首先取出 $b_{i}b\_i$ 最高的——他必然需要一次覆盖。同时维护一个电梯中人员序列，仅记录其上电梯的时刻。当该序列长度小于 $mm$ 时，继续取 $b_{i}b\_i$ 高的——能尽量带走更多的 $b_{i}b\_i$ 大的一定不劣。若电梯已满，则只能选择进电梯楼层最高的还没上之前就把人运到，因而选择最大的、同时不超过序列中 $l_{\max }l\_\{\backslash max\}$ 的 $rr$ 加入电梯。这样可以维护出一次电梯能带走多少人，记录最高楼层。

对于上行和下行均做同样的操作。电梯的一次运行必然可以同时满足一次上行和一次下行，因而对其做归并即可。

总时间复杂度 $\mathcal{O}(n\log n)\backslash mathcal\; O(n\; \backslash log\; n)$。

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<long long> cal(vector<pair<long long, long long>> &que)
{
    sort(que.begin(), que.end());
    multiset<long long> s;
    for (auto i : que)
    {
        auto it = s.upper_bound(i.first);
        if (it != s.begin())
            s.erase(prev(it));
        s.insert(i.second);
    }
    vector<long long> ans;
    while(!s.empty())
    {
        int times = m;
        ans.push_back(*s.rbegin());
        while(!s.empty() && times--)
            s.erase(s.find(*s.rbegin()));
    }
    return ans;
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    vector<pair<long long,long long>> up, down;
    for (int i = 1, a, b; i <= n;i++)
    {
        scanf("%d%d", &a, &b);
        if (a < b)
            up.emplace_back(a, b);
        else
            down.emplace_back(b, a);
    }
    auto f1 = cal(up), f2 = cal(down);
    long long ans = 0;
    for (int i = 0; i < max(f1.size(), f2.size()); i++)
    {
        long long d1 = i < f1.size() ? f1[i] : 0;
        long long d2 = i < f2.size() ? f2[i] : 0;
        ans += 2 * (max(d1, d2) - 1);
    }
    printf("%lld", ans);
    return 0;
}

J Link with Arithmetic Progression

题意：给定 $nn$ 个点 $(i,a_i)(i,a\_i)$，求作一直线 $l:y=kx+bl:y=kx+b$ 使得 $\sum (a_i-y_i{)}^2\backslash sum\; (a\_i-y\_i)^2$ 最小。

解法：最小二乘法：

带入公式即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        vector<long double> num(n + 1);
        long double sum = 0, avay = 0, avax = 0, squx = 0;
        for (long long i = 1; i <= n;i++)
        {
            scanf("%Lf", &num[i]);
            avay += num[i];
            avax += i;
            squx += i * i;
            sum += i * num[i];
        }
        long double k = (sum - avay * avax / n) / (squx - avax * avax / n);
        long double b = avay / n - k * (avax / n);
        long double ans = 0;
        for (int i = 1; i <= n;i++)
        {
            long double dif = num[i] - k * i - b;
            ans += dif * dif;
        }
        printf("%.15Lf\n", ans);
    }
    return 0;
}

K Link with Bracket Sequence I

题意：给定一个长度为 $nn$ 的括号序列 $SS$，求有多少个合法长度为 $mm$ 的括号序列是以 $SS$ 作为其子序列（可以不连续）。多测，$T,n,m\le 200T,n,m\; \backslash leq\; 200$。

解法：考虑三维 dp：$f_{i,j,k}f\_\{i,j,k\}$ 表示原序列长度为 $ii$，和 $SS$ 的最长公共子序列长度为 $jj$（尽量优先和 $SS$ 匹配），左侧有 $kk$ 个游离左括号的方案数。

则转移有：

1. 和当前 $S_{j}S\_j$ 相同。$f_{i,j,k}\leftarrow f_{i-1,j-1,k^{\mathrm{\prime }}}f\_\{i,j,k\}\; \backslash leftarrow\; f\_\{i-1,j-1,k\text{'}\}$，其中当 $S_{j}S\_j$ 为左括号时 $k^{\mathrm{\prime }}\leftarrow k+1k\text{'}\; \backslash leftarrow\; k+1$，反之为 $k^{\mathrm{\prime }}\leftarrow k-1k\text{'}\; \backslash leftarrow\; k-1$。
2. 和当前 $S_{j}S\_j$ 不同。$f_{i,j,k}\leftarrow f_{i-1,j,k^{\mathrm{\prime }}}f\_\{i,j,k\}\; \backslash leftarrow\; f\_\{i-1,j,k\text{'}\}$，和上文同理。

注意一定要优先和 $SS$ 匹配：否则对于括号串 ()，就会有两种 ()()，一种为新序列是原序列的前两个位置，另一种为后两个位置，但是最终呈现的答案只有一种。

#include <bits/stdc++.h>
using namespace std;
const int N = 200;
char s[N + 5];
const long long mod = 1000000007;
int main()
{
    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%s", &n, &m, s + 1);
        vector<vector<vector<int>>> f(m + 1, vector<vector<int>>(n + 1, vector<int>(m + 1, 0)));
        f[0][0][0] = 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 0; k <= i; k++)
                {
                    f[i + 1][j + (s[j + 1] == '(')][k + 1] = (f[i][j][k] + f[i + 1][j + (s[j + 1] == '(')][k + 1]) % mod;
                    if (k)
                        f[i + 1][j + (s[j + 1] == ')')][k - 1] = (f[i][j][k] + f[i + 1][j + (s[j + 1] == ')')][k - 1]) % mod;
            }
        printf("%d\n", f[m][n][0]);
    }
    return 0;
}

L Link with Level Editor I

题意：给定 $nn$ 层图，每层图都有 $mm$ 个节点，和不同的边连接。选择一个子段 $[l,r],1\le l\le r\le n[l,r],1\; \backslash leq\; l\; \backslash leq\; r\; \backslash leq\; n$，从 $11$ 号节点出发，每一步可以停留不动或者沿当前层的边走一条边，然后传送到下一层的同一编号节点，到达 $mm$ 号节点成功。问最小的子段长度。空间非常小，$n\le 1\times 10^4,m\le 2\times 10^{3}n\; \backslash leq\; 1\backslash times\; 10^4,m\; \backslash leq\; 2\backslash times\; 10^3$。

解法：$f_{i,j}f\_\{i,j\}$ 表示在第 $ii$ 层的节点 $jj$，最晚需要从哪一层出发。显然它的转移是只需要本层的图和上层的 dp 数组——要么从上层停留不动，要么从本层的转移边转移，因而使用滚动数组优化即可。时间复杂度 $\mathcal{O}(nm)\backslash mathcal\; O(nm)$，空间复杂度 $\mathcal{O}(m)\backslash mathcal\; O(m)$。

#include <bits/stdc++.h>
using namespace std;
const int M = 2000;
int f[2][M + 5];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int ans = n + 1;
    for (int i = 1, l, u, v; i <= n;i++)
    {
        for (int j = 1; j <= m;j++)
            f[i % 2][j] = f[(i ^ 1) % 2][j];
        f[(i ^ 1) % 2][1] = i;
        scanf("%d", &l);
        for (int j = 1; j <= l; j++)
        {
            scanf("%d%d", &u, &v);
            f[i % 2][v] = max(f[i % 2][v], f[(i ^ 1) % 2][u]);
        }
        if (f[i % 2][m])
            ans = min(ans, i - f[i % 2][m] + 1);
    }
    if(ans > n)
        printf("-1");
    else
        printf("%d", ans);
    return 0;
}