牛客20220723第二场

Link with Monotonic Subsequence

题目描述：
构造长度为 n 的排列 p，使得 max {lis(p), lds(p)} 最小
lis(p): p 的最长上升子序列的长度
lds(p): p 的最长下降子序列的长度

解：
max {lis(p), lds(p)} 的下界是多少？
如果 n = k，构造(n − k + 1 n − k + 2 ... n)...(k + 1 k + 2 ... 2k)(1 2 ... k)
证明: lds(p) = 最小上升子序列分划数 (Dilworth 定理)
⇒ lis(p) lds(p) ≥ n ⇒ max {lds(p), lis(p)} ≥ $图片说明$

Link with Arithmetic Progression

题目描述：
给定一串整数a1、a2、a3、a4、an，将它调成等差数列b1、b2、b3、b4、bn
使得 $图片说明$ 最小

解：
这题本质上是线性回归的题目，有两种做法
1、直接套线性回归公式算出拟合直线
2、先算出x,y的平均值，根据线性回归的性质，可以知道这个点必在直线上，接着就可以利用三分法枚举斜率，同样可以计算出结果

方法1：直接套公式

#include<iostream>
#include <cstdio>
#include <cctype>
#include <iomanip>
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;


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;


ll arr[100005];

void solve() {
    ll n = gti();
    long double xy = 0, xx = 0, x_p = 0, y_p = 0;
    for (ll i = 1; i <= n; i++) {
        arr[i] = gti();
        xy += i * arr[i];
        xx += i * i;
        x_p += i;
        y_p += arr[i];
    }
    x_p = x_p / n;
    y_p = y_p / n;
    long double b = (xy - n * x_p * y_p) / (xx - n * x_p * x_p);
    long double a = y_p - b * x_p;
    long double res = 0;
    for (ll i = 1; i <= n; i++) {
        res += (b * i + a - arr[i]) * (b * i + a - arr[i]);
    }
    cout << fixed << setprecision(15) << res << endl;
}


int main() {
    int t = gti();
    while (t--) {
        solve();
    }
}

方法二：三分枚举斜率

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

ll y[100005];
ll n;
ld y_p, x_p;


#include <cstdio>
#include <cctype>

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;

ld dis(ld k) {
    ld res = 0;
    for (ll i = 1; i <= n; i++) {
        res += pow((k * (i - x_p) + y_p - y[i]), 2);
    }
    return res;
}

void solve() {
    n = gti();
    ll yy = 0;
    for (ll i = 1; i <= n; i++) {
        y[i] = gti();
        yy += y[i];
    }
    y_p = (ld) yy / n;
    x_p = (ld) (1 + n) / 2;
    ld r = 1e9, l = -1e9, k1, k2, k, res;
    while (r - l > 1e-9) {
        k = (r - l) / 3;
        k1 = l + k;
        k2 = l + k + k;
        ld resk1 = dis(k1);
        ld resk2 = dis(k2);
        res = resk1 < resk2 ? resk1 : resk2;
        res=min(res,dis((k1+k2)/2));
        if (resk1 < resk2) {
            r = k2;
        } else {
            l = k1;
        }
    }
    cout << fixed << setprecision(15) << res << endl;
}

int main() {
    int t = gti();
    while (t--) {
        solve();
    }
}

Link with Game Glitch

题目描述：
有n个物品，给出m种合成方式，每种合成方式都是用a个b物品能合成c个d物品，所以可能有某种方式能够得到无限大的某种物品，为了避免这个问题，现在添加一个参数w，只能用a个b物品合成w*c个d物品，求出满足题意的最大的w

解：
建图，n个顶点，m条边，每条边的权值就是c/a，二分枚举w，每条边的权值就变成了w*c/a，如果存在一个边权乘积大于1的环，就可以无限得到物品，对每条边取-log，就变成了如果边权相加存在负环，那么就可以无限得到物品，这样就可以求出答案。

牛客20220723第二场

Link with Monotonic Subsequence

Link with Arithmetic Progression

Link with Game Glitch

Link with Bracket Sequence I

全站热榜