A

題解

知識點：貪心，揹包dp。

注意到交換鄰項不影響其他的結果，可以通過鄰項交換證明選擇順序，假設a在b前更優：

\[\Sigma + w_a\Pi + w_bp_a\Pi + \Sigma' \geq \Sigma + w_b\Pi + w_ap_b\Pi + \Sigma'\\ w_a+w_bp_a \geq w_b + w_ap_b\\ \frac{w_a}{1-p_a} \geq \frac{w_b}{1-p_b} \]

發現排序性質只和自己有關，顯然具有傳遞性，因此以此排序。

但這只是確定了選擇的順序，即一個序列中元素應當出現的順序，並不是指前 \(m\) 個是最優的序列，因此需要通過揹包dp，\(f[i][j]\) 表示考慮到第 \(i\) 個伺服器，已經選了 \(j\) 個。

題目雖然要求我們必須選 \(m\) 個，但由於收益全是正的，所以不需要初始化負無窮。

因為在揹包收益計算中如果正著選則需要記錄前面選擇的所有 \(p\) 值累乘，很不方便。而倒著選，可以通過整體乘法給選好的都乘上這次選的 \(p\) ，非常方便。

時間複雜度 \(O(n(m+\log n))\)

空間複雜度 \(O(n+m)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

struct node {
    ll w, p;
}a[100007];

double f[27];

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i].w;
    for (int i = 1;i <= n;i++) cin >> a[i].p;
    sort(a + 1, a + 1 + n, [&](node a, node b) {
        return a.w * 10000 + b.w * a.p > b.w * 10000 + a.w * b.p;
    });///排的是選擇的相對順序，即如果選了a和b，則a在前比b在前更優的條件，而非前m個一定最優，最優子序列需要dp

    //for (int i = 1;i <= n;i++) cout << a[i].w << ' ' << a[i].p << '\n';
    for (int i = n;i >= 1;i--) {///倒著選，因為要累乘
        for (int j = m;j >= 1;j--) {
            f[j] = max(f[j], f[j - 1] * a[i].p / 10000.0 + a[i].w);
        }
    }
    cout << fixed << setprecision(7) << f[m] << '\n';
    return 0;
}

D

題解

方法一

知識點：列舉，字首和。

題目強制線上，卡掉了一些離線演演算法，此時還有一些如樹套樹，K-D樹等結構可用（但我不會wwwwww。本題我用了較簡單的方法。

\(dp[i][j]\) 代表IQ為 \(i\) ，EQ為 \(j\) 時需要滿足的最小AQ。對於一個公司，把每個工作記錄，通過 min(dp[a][b],c) 更新給出IQ,EQ的最低AQ。再通過遞推式：min(dp[i-1][j],dp[i][j]) ，min(dp[i][j-1],dp[i][j]) 遍歷狀態空間，更新所有IQ,EQ的最低AQ。

時間複雜度 \(O(\Sigma m + n\cdot 400^2 + nq)\)

空間複雜度 \(O(n\cdot 400^2)\)

方法二

知識點：列舉，字首和。

\(bs[i][j][k]\) 表示IQ,EQ,AQ時可以。因此有遞推式： bs[id][i][j][k] = bs[id][i][j][k] | bs[id][i - 1][j][k] | bs[id][i][j - 1][k] | bs[id][i][j][k - 1] 。

注意常數。

時間複雜度 \(O(\Sigma m + n\cdot 400^3 + nq)\)

空間複雜度 \(O(n\cdot 400^3)\)

程式碼

方法一

#include <bits/stdc++.h>
#include <random>

using namespace std;

const int mod = 998244353;
int dp[17][407][407];///第id家公司，當IQ為i，EQ為j的能入職的最小AQ

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    memset(dp, 0x3f, sizeof(dp));
    int n, q;
    cin >> n >> q;
    for (int id = 1;id <= n;id++) {
        int m;
        cin >> m;
        for (int i = 1;i <= m;i++) {///表示IQ>=a,EQ>=b的最小AQ
            int a, b, c;
            cin >> a >> b >> c;
            dp[id][a][b] = min(dp[id][a][b], c);
        }
        for (int i = 1;i <= 400;i++) {
            for (int j = 1;j <= 400;j++) {///發現有效區是一個向i,j,k方向展開的正方體，因此從座標最小遞推，取第三維能滿足的最小值
                dp[id][i][j] = min(dp[id][i - 1][j], dp[id][i][j]);
                dp[id][i][j] = min(dp[id][i][j - 1], dp[id][i][j]);
            }
        }
    }
    int seed;
    cin >> seed;
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1, 400);

    int lastans = 0, ans = 0;
    for (int i = 1;i <= q;i++) {
        int IQ = (u(rng) ^ lastans) % 400 + 1;  // The IQ of the i-th friend
        int EQ = (u(rng) ^ lastans) % 400 + 1;  // The EQ of the i-th friend
        int AQ = (u(rng) ^ lastans) % 400 + 1;  // The AQ of the i-th friend
        lastans = 0;
        for (int i = 1;i <= n;i++)
            lastans += dp[i][IQ][EQ] <= AQ;  // The answer to the i-th friend
        ans = (1LL * ans * seed + lastans) % mod;
    }
    cout << ans << '\n';
    return 0;
}

方法二

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;
bitset<401> bs[11][401][401];///表示id公司，IQ = a,EQ = b,AQ = c時可以

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int id = 1;id <= n;id++) {
        int m;
        cin >> m;
        for (int i = 1;i <= m;i++) {///表示IQ = a,EQ = b,AQ = c時可以
            int a, b, c;
            cin >> a >> b >> c;
            bs[id][a][b][c] = 1;
        }
        for (int i = 1;i <= 400;i++)
            for (int j = 1;j <= 400;j++)
                for (int k = 1;k <= 400;k++)///正方體同上，因此從座標最小遞推，如果座標小的滿足那麼這個也能滿足
                    bs[id][i][j][k] = bs[id][i][j][k] | bs[id][i - 1][j][k] | bs[id][i][j - 1][k] | bs[id][i][j][k - 1];
    }
    int seed;
    cin >> seed;
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1, 400);

    int lastans = 0, ans = 0;
    for (int i = 1;i <= q;i++) {
        int IQ = (u(rng) ^ lastans) % 400 + 1;  // The IQ of the i-th friend
        int EQ = (u(rng) ^ lastans) % 400 + 1;  // The EQ of the i-th friend
        int AQ = (u(rng) ^ lastans) % 400 + 1;  // The AQ of the i-th friend
        lastans = 0;
        for (int i = 1;i <= n;i++)
            lastans += bs[i][IQ][EQ][AQ] == 1;  // The answer to the i-th friend
        ans = (1LL * ans * seed + lastans) % mod;
    }
    cout << ans << '\n';
    return 0;
}

H

題解

知識點：列舉，貪心，STL。

先求出面積 \(S\) ，只需要列舉可能的長寬，在去檢查這個長和寬的答案。對於一行，我們貪心地選擇最接近剩餘長度的磚塊（類似sticks這題，剪枝好惡心qwq），過程中運用到 multiset 查詢符合要求的磚塊。

時間複雜度 \(O(n^3)\)

空間複雜度 \(O(n^2)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int n, ans;
multiset<int> ms;
vector<pair<int, int>> tmp[207], path[207];///長度為i的方塊座標


void check(int w, int h) {
    ms.clear();
    for (int i = 1;i <= n;i++) tmp[i].clear();
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n - i + 1;j++) ms.insert(i);
    int rem = w;///剩餘長度
    int hi = 0;///底部高度
    while (hi < h) {
        auto p = ms.upper_bound(rem);
        if (p == ms.begin()) return;
        int k = *prev(p);
        ms.erase(prev(p));///erase(type)是刪掉某個元素全部,刪掉一個要用指標
        tmp[k].push_back({ w - rem,hi });///左下角
        rem -= k;
        if (!rem) rem = w, hi++;
    }
    if (2 * (w + h) < ans) {
        ans = 2 * (w + h);
        for (int i = 1;i <= n;i++)
            path[i] = tmp[i];
    }
}

bool solve() {
    cin >> n;
    int S = 0;
    for (int i = 1;i <= n;i++) S += (n - i + 1) * i;
    ans = ~(1 << 31);
    for (int w = 1;w * w <= S;w++) {
        if (S % w == 0) {
            int h = S / w;
            check(h, w);
            check(w, h);
        }
    }
    cout << ans << '\n';
    for (int i = 1;i <= n;i++)
        for (auto j : path[i])
            cout << j.first << ' ' << j.second << ' ' << j.first + i << ' ' << j.second + 1 << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

K

題解

知識點：數論，列舉，思維。

首先特判 \(n = 1\) 時，不需要任何操作。

當 \(n > 1\) 時，假設有 \(A \equiv i-1\ (mod\ n)\) ，經過 \(k\ (1 \leq k \leq 6)\) 次(因為不可能不操作，最多操作6次可以遍歷最大的 \(n\) )做操作後有如下式：

\[\begin {aligned} 10^kA + x &\equiv i \ (mod\ n)\\ x &\equiv i-10^kA \ (mod\ n) \end {aligned} \]

因此對每個 \(i\) 可以求出 \(x\) 最小正整數解，若 \(x < 10^k\) 則說明成立。

時間複雜度 \(O(n)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int tb[10] = { 1,10,100,1000,10000,100000,1000000 };

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        int k;
        for (k = 1;k <= 6;k++) {
            int x = ((i - 1LL * tb[k] * (i - 1)) % n + n) % n;///可能負數所以先模再加再模
            if (x < tb[k]) break;
        }
        ans += k;
    }
    cout << ans << '\n';
    return 0;
}
/// x = i - 10^k(i-1)  (mod n)

N

題解

知識點：位運算，思維，數學。

遍歷輸入數位的每位，最終得到每位一共有多少二進位制 \(1\) 存在，隨後儘可能組成最大的數（因為根據與和或運算最終一定能將二進位制為集中起來），隨後計算方差即可。方差有如下公式：

\[\begin{aligned} \frac{1}{n} \sum_{i=1}^{n} (x_i-\mu)^2 &= \frac{1}{n}\left (\sum_{i=1}^{n} x_i^2 - 2\mu\sum_{i=1}^{n}x_i + n\mu^2 \right)\\ &= \frac{1}{n^2}\left(\sum_{i=1}^{n} x_i^2-(\sum_{i=1}^{n} x_i)^2 \right) \end{aligned} \]

這樣分子分母可以分別用整數計算。

時間複雜度 \(O(n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int bit[20], a[100007];

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1, tmp;i <= n;i++) {///拆二進位制
        cin >> tmp;
        for (int j = 0;j < 15;j++)
            if ((tmp >> j) & 1) bit[j]++;
    }
    for (int i = 1;i <= n;i++)///重組
        for (int j = 0;j < 15;j++)
            if (bit[j]) a[i] += 1 << j, bit[j]--;
    ll sum = 0, sum2 = 0;
    for (int i = 1;i <= n;i++) {
        sum += a[i];///雖然a&b + a|b = a+b，但為了好看在這裡加
        sum2 += a[i] * a[i];
    }
    ///1/n^2 (n*sum2 - sum^2) = 方差
    ll x = n * sum2 - sum * sum;
    ll y = 1LL * n * n;
    ll d = __gcd(x, y);
    cout << x / d << '/' << y / d << '\n';
    return 0;
}

蔚來杯2022牛客暑期多校訓練營4

A

題解

程式碼

D

題解

方法一

方法二

程式碼

方法一

方法二

H

題解

程式碼

K

題解

程式碼

N

題解

程式碼