“蔚来杯“2022牛客暑期多校训练营2 个人题解集合

文章目录

• ​​D.[Link with Game Glitch]​​

• ​​题目分析​​

• ​​Code​​
• ​​G.[ Link with Monotonic Subsequence]构造​​

• ​​题目分析​​
• ​​Code​​

• ​​H.[ Take the Elevator] 模拟​​

• ​​题目分析​​
• ​​Code​​

• ​​I.[ let fat tension]​​

• ​​题目分析​​
• ​​Code​​

• ​​J.[Link with Arithmetic Progression]线性回归​​

• ​​题目分析​​
• ​​Code​​

• ​​K.[Link with Bracket Sequence I](DP)​​

• ​​题目分析​​
• ​​Code​​

• ​​L.Link with Level Editor I​​

• ​​题目分析​​
• ​​Code​​

D.Link with Game Glitch

题目分析

有个配方，每个配方可以使用个种原料生成个种原料。现在要求在上乘一个权值，使得所有配方间不存在可以循环生成无限物品的局面。要求最大化。

显然要生成无限物品，需要存在一个环且沿该环生成一轮得到的物品数目比原来更多，即为环上满足所有的边有即为。

由于可能存在多个环，我们只需要保证最大环不会循环生成即可。显然可以二分答案来做。

Code

#include <bits/stdc++.h>
//#pragma gcc optimize(2)
#define double long double
#define endl '\n'
using namespace std;

const int N = 2e3 + 10, MOD = 1e9 + 7;
const double EPS = 1e-8;

struct node{ int v; double w; };

vector<node> g[N];
int n, m, cnt[N];
double dis[N];
bitset<N> vis;

bool check(double x){
    queue<int> q;
    x = -log(x);
    vis.set();
    memset(dis, 0, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i <= n; i++) q.emplace(i);
    while(q.size()){
        int u = q.front(); q.pop();
        vis.reset(u);
        for(auto nxt : g[u]){
            int v = nxt.v;
            double w = nxt.w;
            if(dis[v] > dis[u] + w + x){
                dis[v] = dis[u] + w + x;
                cnt[v] = cnt[u] + 1;
                if(cnt[v] > n) return true;
                if(!vis[v]){
                    q.emplace(v);
                    vis.set(v);
                }
            }
        }
    }
    return false;
}   

inline void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        g[b].emplace_back(node{d, -log((1.0 * c) / a)});
    }
    double l = 0, r = 1;
    for(int i = 1; i <= 300; i++){
        double mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << l << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

G. Link with Monotonic Subsequence 构造

题目分析

要求构造一个长度为的序列，使得序列的尽可能的小。

狄尔沃斯定理：对偏序集，设A中最长链的长度是，则将中元素分成不相交的反链，反链个数至少是。

那么有，那么显然 。因此直接构造个块即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;


inline void solve(){
    int n = 0; cin >> n;
    int b = ceil(sqrt(n));
    while(n > 0){
        for(int i = max(1ll, n - b + 1); i <= n; i++) cout << i << " ";
        n -= b;
    }
    cout << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

H. Take the Elevator 模拟

题目分析

给定层楼的楼栋，现在有一个电梯从楼出发，最多承载人，电梯有故障，向下运行时必须到达楼方可改变方向。有个人希望从楼层到达楼层，问电梯至少需要跑多少趟。

设表示向上走的第轮到达的最高的层数，表示向下走的第轮出发的最高层数，那么最终答案就是枚举轮数，，得到最终答案。

那么可以分上下两个过程，分别存下所有的端点(带标记)，每个乘客分配的轮数可以通过得到。

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

struct node{ int s, t; }up[N], down[N];

int ansup[N], ansdown[N];

inline void solve(){
    int n = 0, m = 0, k = 0; cin >> n >> m >> k;
    int upcnt = 0, downcnt = 0;
    for(int i = 1; i <= n; i++){
        int a, b; cin >> a >> b;
        if(a < b) up[++upcnt] = node{.s = a, .t = 1}, up[++upcnt] = node{.s = b, .t = -1};
        else down[++downcnt] = node{.s = a, .t = -1}, down[++downcnt] = node{.s = b, .t = 1};
    }
    int upans = 0, downans = 0;
    sort(up + 1, up + 1 + upcnt, [](const node &x, const node &y){ return x.s < y.s || x.s == y.s && x.t < y.t; });
    sort(down + 1, down + 1 + downcnt, [](const node &x, const node &y){ return x.s < y.s || x.s == y.s && x.t < y.t; });
    int now = 0; 
    for(int i = 1; i <= upcnt; i++){
        if(up[i].t == -1)
            ansup[(now + m - 1) / m] = up[i].s;    
        now += up[i].t;
    }
    assert(now == 0);
    for(int i = 1; i <= downcnt; i++){
        if(down[i].t == -1)
            ansdown[(now + m - 1) / m] = down[i].s;
        now += down[i].t;
    }
    int ans = 0;
    for(int i = 1; i <= 200000; i++)
        ans += 2 * max({1ll, ansup[i], ansdown[i]}) - 2;
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

I. let fat tension

题目分析

定义为之间的余弦相似度：

要求求新，。

发现暴力计算显然行不通，但是可以转化为矩阵运算，除以模长可以直接对矩阵每行做归一化运算，那么答案就是：

为按行归一化之后的矩阵。

那么可以得到运算的过程：。

发现先做后两个矩阵之间乘法，复杂度。那么直接计算即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
//#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

double X[10010][100], XT[100][10010], Y[10010][100], ans1[100][100], ans2[10010][100];



inline void solve(){
    int n, k, d; cin >> n >> k >> d;
    double sum = 0;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= k; j++) 
        cin >> X[i][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
        cin >> Y[i][j];
    for(int i = 1; i <= n; i++){
        sum = 0;
        for(int j = 1; j <= k; j++) sum += X[i][j] * X[i][j];
        sum = sqrt(sum);
        for(int j = 1; j <= k; j++) X[i][j] = XT[j][i] = X[i][j] / sum;
    }
    for(int i = 1; i <= k; i++) for(int j = 1; j <= d; j++)
    for(int t = 1; t <= n; t++) ans1[i][j] += XT[i][t] * Y[t][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
    for(int t = 1; t <= k; t++) ans2[i][j] += X[i][t] * ans1[t][j];
    for(int i = 1; i <= n; i++) for(int j = 1; j <= d; j++)
        cout << ans2[i][j] << " \n"[j == d];

}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

J.Link with Arithmetic Progression 线性回归

题目分析

给定数列，构造，使得最小，求最小值。

容易发现是线性回归问题，于是考虑用机器学习高中数学 的知识解决。

根据高斯-马尔可夫定理：在给定经典线性回归的假定下，最小二乘估计量是具有最小方差的线性无偏估计量。

对于函数，定义其目标函数为。

带入线性回归公式：

然后计算误差输出即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define double long double
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

inline int read(){
    int f = 1, x = 0; char s = getchar(); 
    while(s < '0'||s > '9'){ if(s == '-') f = -1; s = getchar(); } 
    while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
    return x *= f; 
}

int a[N];

inline void solve(){
    int n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    double sumx = 0, sumy = 0, da = 0, dc = 0;
    for(int i = 1; i <= n; i++){
        sumx += i, sumy += a[i];
        da += i * a[i], dc += i * i;
    }
    double db = sumx * sumy / n, dd = sumx * sumx / n, ans = 0;
    double B = (da - db)/(dc - dd);
    double A = sumy / n - B * sumx / n;
    for(int i = 1; i <= n; i++) ans += (B * i + A - a[i]) * (B * i + A - a[i]);
    cout << ans << endl;
}

signed main(){
    //ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    cout << fixed << setprecision(12);
    while(t--) solve();
    return 0;
}

K.Link with Bracket Sequence I (DP)

题目分析

给定长度为的括号序列(不保证合法性)，求在此基础上生成的长度为括号序列的方案数。

设表示插入括号的数量为、使用的原来的序列中的括号数量为，左括号比右括号多时的方案数。那么最终答案为。那么考虑如何设计状态转移：

首先枚举插入的括号数量，原来的括号序列和左括号比右括号多的数量。

如果目前枚举到的括号为左括号，并且使用的原括号的数量，就可以将该括号放入最终序列中，即为：

如果此时枚举到的是一个右括号，并且，即左括号的数量大于右括号的数量，并且使用的原括号的数量，就将该右括号放入最终序列：

如果使用的括号数量为，或当前枚举到右括号，则可以插入左括号：

当时，如果使用原序列括号的数目为，或当前枚举到左括号，则可以插入右括号：

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#pragma g++ optimize(2)
// #define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;
int dp[220][220][220];

inline void solve(){
    // memset(dp, 0, sizeof(dp));
    int m, n; cin >> n >> m;
    string s; cin >> s;
    // if(n & 1 || (m - n) & 1) { cout << 0 << endl; return; }
    dp[0][0][0]=1;
    for (int i = 0; i <= m - n; ++i)
    for (int j = 0; j <= n; ++j)
        for (int k = 0; k <= m; ++k){
            if (s[j] == '(' && j < n)
                dp[i][j + 1][k + 1] = (dp[i][j + 1][k + 1] + dp[i][j][k]) % mod;
            else
                dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod;
            if (k > 0){
                if (s[j] == ')' && j < n)
                    dp[i][j + 1][k - 1] = (dp[i][j + 1][k - 1] + dp[i][j][k]) % mod;
                else
                    dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + dp[i][j][k]) % mod;
            }
        }
    cout << dp[m - n][n][0] << endl;
    for(int i = 0; i <= m + 2; i++)
        for(int j = 0; j <= n + 2; j++)
            for(int k = 0; k <= m + 2; k++) dp[i][j][k] = 0;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

L.Link with Level Editor I

题目分析

记 表示在第个世界中到达点。然后用滚动数组优化第一维。

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#pragma g++ optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e3 + 5;
int dp[N], now[N];
void solve(){
    int n, m; cin >> n >> m;
    memset(dp, 0x3f, sizeof(dp));
    int ans = 1e9;
    while (n--){
        int k; cin >> k;
        dp[1] = 0;
        memset(now, 0x3f, sizeof(now));
        for (int i = 1; i <= k; i++){
            int u, v; cin >> u >> v;
            now[v] = min(now[v], dp[u] + 1);
        }
        for (int i = 1; i <= m; i++) dp[i] = min(dp[i] + 1, now[i]);
        ans = min(ans, dp[m]);
    }
    if (ans == 1e9) cout << "-1\n";
    else cout << ans << "\n";
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}