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

2022 年 8 月 2 日
筆記
比賽題解

A

題解

知識點：圖論，dp。

暴力建圖，連接所有點的雙向通路，除了原點是單向的，並且把路徑長度作為權值。

隨後，從原點出發（\(f[0] = 0\)，其他點負無窮，保證從原點出發），按照權值從大到小（大的先走小的後走，相等屬於同一階段，滿足拓撲序）進行dp。

對於路徑 \((u,v)\) 的狀態轉移方程是 \(g[v] = max(g[v],f[u]+1)\) ，其中 \(f,g\) 分別存儲上一次結果和這一次結果，做到滾動數組節省空間，隨後把 \(g\) 還給 \(f\)，下次dp前把 \(g\) 初始化負無窮。

最後，找到所有點的最大值。

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

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

程式碼

#include <bits/stdc++.h>

using namespace std;

struct node {
    int u, v, w;
};

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    pair<int, int> p[2007];
    for (int i = 1;i <= n;i++) {
        int u, v;
        cin >> u >> v;
        p[i] = { u,v };
    }
    vector<node> e;
    for (int i = 0;i <= n;i++)///暴力連邊,只從原點出發
        for (int j = 1;j <= n;j++)
            if (i != j)e.push_back({ i,j,(p[i].first - p[j].first) * (p[i].first - p[j].first) + (p[i].second - p[j].second) * (p[i].second - p[j].second) });
    sort(e.begin(), e.end(), [&](node a, node b) {
        return a.w > b.w;
    });///從大到小距離走
    vector<int> f(n + 1, -2e9), g(n + 1, -2e9);
    int i = 0, j = 0;
    f[0] = 0;///解鎖原點
    while (i < e.size()) {
        vector<node> t;
        while (j < e.size() && e[i].w == e[j].w) t.push_back(e[j++]);///把下一個大小的邊都加入
        for (auto ed : t) g[ed.v] = -2e9;///初始化
        for (auto ed : t) g[ed.v] = max(g[ed.v], f[ed.u] + 1);///更新到下一個點吃到最多的數量
        for (auto ed : t) f[ed.v] = max(g[ed.v], f[ed.v]);///滾動
        i = j;
    }
    cout << *max_element(f.begin(), f.end()) << '\n';
    return 0;
}

B

題解

知識點：二分，貪心，排序。

答案單調是可以二分的，所以優先考慮二分。發現對於一個答案要選擇最便宜的去驗證答案，因此每次需要對序列排序（因為排序規則和答案有關），滿足關係式：

\[a_{val} + ka_{id} < b_{val} + kb_{id} \]

取 \(k\) 個如果價值總和小於等於錢數，證明答案可行。

時間複雜度 \(O(n\log^2n)\)

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

程式碼

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

using namespace std;

int n, m;
struct node {
    ll val;
    ll id;
}a[100007];

bool check(int mid) {
    sort(a + 1, a + n + 1, [&](node a, node b) {
        return a.val + mid * a.id < b.val + mid * b.id;
    });
    ll sum = 0;
    for (int i = 1;i <= mid;i++) sum += a[i].val + mid * a[i].id;
    return sum <= m;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i].val, a[i].id = i;
    int l = 0, r = n;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    cout << r << '\n';
    return 0;
}

C

題解

知識點：思維。

對某位Y/N數進行分類討論，如下列表格：

YES數/NO數	0	1	>1
0	-1	-1/0	0
1	-1/1	-1	0
>1	1	1	-1

存在四種情況能確定，兩種可能確定，剩下三種不確定直接 \(-1\)。

確定的四種：

Y > 1且N = 0，不可能是錯誤詢問，直接確定為 \(1\)。
N > 1且Y = 0，同上確定為 \(0\) 。
Y > 1且N = 1，確定唯一錯誤詢問，並確定為 \(1\)。
N > 1且Y = 1，同上確定為 \(0\) 。

可能確定的兩種：

Y = 1且N = 0，最終錯誤詢問被發現時可確定為 \(1\) ，否則不確定，因此將此類計數，最終判斷這種情況。
N = 1且Y = 0，同上可能確定為 \(0\) 。

不確定的三種：

Y = 0且N = 0，顯然不確定。
Y = 1且N = 1，發現錯誤詢問，但依然不確定。
Y > 1且N > 1，錯誤詢問超額。

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

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

程式碼

#include <bits/stdc++.h>

using namespace std;

struct bit {
    int y, n;
}a[100007];

bool ans[100007];

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    int x;
    string s;
    for (int i = 1;i <= 3 * n;i++) {
        cin >> x >> s;
        if (s == "YES") a[x].y++;
        else a[x].n++;
    }
    bool fault = false;
    bool ok = true;
    int cnt = 0;
    for (int i = 0;i < n;i++) {
        if (a[i].y > 1 && a[i].n == 0) ans[i] = 1;
        else if (a[i].y == 0 && a[i].n > 1) ans[i] = 0;
        else if (!fault && a[i].y > 1 && a[i].n == 1) ans[i] = 1, fault = 1;
        else if (!fault && a[i].y == 1 && a[i].n > 1) ans[i] = 0, fault = 1;
        else if (a[i].y == 1 && a[i].n == 0) ans[i] = 1, cnt++;
        else if (a[i].y == 0 && a[i].n == 1) ans[i] = 0, cnt++;
        else ok = false;
    }
    if (!ok || !fault && cnt) cout << -1;
    else for (int i = 0;i < n;i++) cout << ans[i];
    cout << '\n';
    return 0;
}

D

題解

知識點：樹形dp。

題目要求，樹中滿足度為 \(1\) 的節點的權值都相同（0/1）的連通子圖個數。

因為全為 \(0\) 和全為 \(1\) 兩種情況其實解決方法一樣，所以可以同一個方法跑兩次即可。

考慮度為 \(1\) 的節點顏色為 \(flag\) 。設 \(dp[i]\) 表示為以編號 \(i\) 的節點為根的子樹的方案數。對於根 \(u\) 及其子節點 \(v_i\) ，每個子節點 \(v_i\) 都有 \(dp[v_i]\) 種選擇方案使得以 \(v_i\) 為根的子樹符合條件，加上不選 \(v_i\) 分支的一種，共有 \(dp[v_i] + 1\) 種方案。對所有子節點 \(v_i\) ，都可以獨立的選和不選，所以進行乘法原理的運算，得到選擇子節點 \(v_i\) 的所有方案數為 \(\prod (dp[v_i]+1)\) 。

但有一種情況是所有子節點都不選，只留個根。這種方案會使這個節點成為一個度為 \(1\) 的點（因為是子樹），顏色必須要符合 \(flag\) 才可以作為一種方案。因此這種情況要特判，故 \(dp[u] = \prod (dp[v_i]+1) - 1 + [a[u] == flag]\) 。

接下來是記錄答案，如果 \(a[u] = flag\) ，則作為一個獨立的以 \(u\) 為根的樹（不是別的節點的子樹）的所有方案和是子樹的所有方案 \(dp[u]\) 是等價的，因為 \(u\) 無論如何都符合條件；如果 \(a[u] \neq flag\) ，則作為一個獨立樹，當只選了一個子節點的情況是不可行的，此時根節點 \(u\) 是度為 \(1\) 的，與 \(dp[u]\) 的情況不同（因為是子樹，\(u\) 只有在什麼都不選的情況才會度為 \(1\)），因此要從 \(dp[u]\) 中減去 \(\sum dp[v_i]\) 。

值得注意的是，無論 \(a[u]\) 是否同色，當其本身成為一個只有一個節點的圖時，都是滿足條件的。這種情況其實已經算在了 \(a[u] = flag\) 中 \(dp[u]\) 的一種里，不需要額外計算，否則會重複。

無根樹可以以任何節點為根，因此從 \(1\) 開始沒什麼問題。

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

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

程式碼

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
bool a[300007];
vector<int> g[300007];
bool flag;
int dp[300007];
int ans;

void dfs(int u, int fa) {
    int sum = 0, mul = 1;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        mul = 1LL * mul * (dp[v] + 1) % mod;///（子節點方案+不選子節點的一個方案）進行乘法原理
        sum = (0LL + sum + dp[v]) % mod;///只選了一個子節點的方案數
    }
    dp[u] = (mul - 1 + (a[u] == flag)) % mod;///mul減去一個子節點都不選的可能加上自己可能符合要求的可能
    if (a[u] == flag) ans = (0LL + ans + dp[u]) % mod;///當前節點符合要求，答案加上dp[u]即可
    else ans = (0LL + ans + dp[u] - sum + mod) % mod;///當前節點不符合要求，則不能成為度為1的節點，減去選一個子節點的所有方案
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        char ch;
        cin >> ch;
        a[i] = ch - '0';
    }
    for (int i = 1;i <= n - 1;i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    flag = 1;
    dfs(1, 0);
    flag = 0;
    dfs(1, 0);
    cout << ans << '\n';
    return 0;
}

F

題解

知識點：計算幾何。

純純的計算幾何（沒學過，函數都是現場造的，好難qwq。

注意到是從上往下看，因此考慮從下往上遍歷，考慮每一個被上面蓋住的弧長即可。

實現過程上，先考慮兩個圓 \(a[i]\) 被 \(a[j]\) 覆蓋，且是相交的情況。發現只需要用一個餘弦定理計算以 \(a[j]\) 半徑為對邊，\(a[i]\) 與 \(Dist_{C_i,C_j}\) 為鄰邊的三角形的夾角弧度 \(\theta\)，然後乘以二就是被覆蓋的弧長弧度；如果兩個圓相離或者後者包含於前者則弧度為 \(0\) ；如果前者包含於後者，是全覆蓋，弧度為 \(2\pi\)。

但事實上不止一個圓覆蓋，因此要考慮重複覆蓋的問題，這涉及到了區間合併，因此考慮以 \(x\) 軸正半軸為基準，逆時針為正方向，形成區間 \([-\pi,\pi]\) ，同時剛好滿足 atan2 函數的特性。

先計算 \(\overrightarrow {C_iC_j}\) 的區間弧度 \(base\)，然後加減 \(\theta\) ，得到始邊弧度和終邊弧度。同時要考慮始邊弧度 \(<-\pi\) 和終邊弧度 \(>\pi\) 的特判，要把一個角拆成兩個角，比如 \([-1.1\pi,0.5\pi]\) 拆成 \([0.9\pi,\pi]\) 與 \([-\pi,0.5\pi]\) 。

隨後按起邊從小到大排序合併區間，要注意有可能該圓不被任何圓覆蓋，\(cnt\) 為 \(0\) ，因此不能以第一個弧段為初始條件，應該以 \([-\pi-1,-\pi-1]\) 類似的為初始條件，或者以\([\pi+1,\pi+1]\) 額外加入數組作為終止條件，順便還可以把最後一段有效區間加上，我個人喜歡後面這種。

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

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

程式碼

#include <bits/stdc++.h>

using namespace std;

const double pi = acos(-1.0);

struct Point {
    double x;
    double y;
};

struct Circle {
    Point A;
    double r;
}a[1007];

double sqr(double x) {
    return x * x;
}

double dist2(Point A, Point B) {
    return sqr(A.x - B.x) + sqr(A.y - B.y);
}

double rad(double a, double b, double c) {///餘弦定理，a對邊，b，c鄰邊
    return acos((b * b + c * c - a * a) / (2 * b * c));
}

double xrad(Point A, Point B) {///與x軸正方向夾角[-pi，pi]
    return atan2(A.y - B.y, A.x - B.x);///斜率y/x，且由象限決定 
}

struct node {
    double x;
    double y;
}xy[1007 << 1];

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++)
        cin >> a[i].A.x >> a[i].A.y >> a[i].r;
    double ans = 0;
    for (int i = 1;i <= n;i++) {
        int cnt = 0;
        for (int j = i + 1;j <= n;j++) {
            ++cnt;
            double len2 = dist2(a[i].A, a[j].A);
            if (len2 >= sqr(a[i].r + a[j].r) || sqrt(len2) <= a[i].r - a[j].r) {///相離 或 j內含於i
                xy[cnt] = { 0,0 };
                continue;
            }
            else if (sqrt(len2) <= a[j].r - a[i].r) {///i內含於j,全蓋住了
                xy[cnt] = { -pi,pi };
                break;
            }
            double xita = rad(a[j].r, a[i].r, sqrt(len2));
            double base = xrad(a[j].A, a[i].A);
            xy[cnt].x = base - xita;
            xy[cnt].y = base + xita;
            if (xy[cnt].x < -pi) {///起邊小於-pi那就分成[起邊+2pi,pi],[-pi,終邊]
                cnt++;
                xy[cnt] = { xy[cnt - 1].x + 2 * pi, pi };
                xy[cnt - 1].x = -pi;
            }
            else if (xy[cnt].y > pi) {///同上
                cnt++;
                xy[cnt] = { -pi, xy[cnt - 1].y - 2 * pi };
                xy[cnt - 1].y = pi;
            }
        }
        sort(xy + 1, xy + cnt + 1, [&](node a, node b) {
            return a.x < b.x;
        });///按起邊從小到大排序，開始合併區間
        xy[++cnt] = { pi + 1,pi + 1 };///終止特殊判斷，方便把最後一段有效段加上
        ans += 2 * pi * a[i].r;///先加上周長
        double lpre = -pi - 1, rmax = -pi - 1;///初始化負無窮，不能初始化第一個，因為有可能一個都沒有（如果上面加了終止判斷，可以不考慮這個）
        for (int j = 1;j <= cnt;j++) {///合併區間
            if (xy[j].x >= rmax) {
                ans -= (rmax - lpre) * a[i].r;///減去一個區間的周長
                lpre = xy[j].x;
            }
            rmax = max(rmax, xy[j].y);
        }
    }
    cout << fixed << setprecision(15) << ans << '\n';
    return 0;
}

G

題解

方法一

知識點：manachar。

不會qwq。

方法二

知識點：迴文自動機。

模板題。不多說（因為也不會說qwq。

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

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

程式碼

方法一

無

方法二

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5e5 + 10;
char s[N];
int n, lst, len[N];
int now, tot = 1, fail[N], cnt[N], t[N][26];

int getfail(int u, int p) {
    while (p - len[u] - 1 <= 0 || s[p - len[u] - 1] != s[p])	u = fail[u];
    return u;
}

int insert(char c, int id) {
    int p = getfail(now, id);
    if (!t[p][c - 'a']) {
        fail[++tot] = t[getfail(fail[p], id)][c - 'a'];
        t[p][c - 'a'] = tot;
        len[tot] = len[p] + 2;
        cnt[tot] = cnt[fail[tot]] + 1;
    }
    return cnt[now = t[p][c - 'a']];
}

ll ans[3];

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    cin >> s + 1;
    fail[0] = 1, len[1] = -1;
    for (int i = 1;i <= n;i++) {
        lst = insert(s[i], i);
        if (s[i] == 'k') ans[0] += lst;
        else if (s[i] == 'f') ans[1] += lst;
        else if (s[i] == 'c') ans[2] += lst;
    }
    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << '\n';
    return 0;
}

H

題解

知識點：數學，計算幾何。

畫圖，求並集面積。

顯然，\(S_U = 2(\dfrac{n}{2})^2 + \dfrac{1}{2}\pi(\dfrac{n}{2})^2 = \dfrac{n^2}{2} + \dfrac{\pi n^2}{8}\) 。

（把union area看成交集QAQ，要被英語退役了）

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

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

程式碼

#include <bits/stdc++.h>

using namespace std;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    double n;
    cin >> n;
    cout << fixed << setprecision(15) << n * n / 2.0 + n * n * acos(-1.0) / 8.0 << '\n';///圓和多邊形面積並集
    return 0;
}

K

題解

知識點：數學。

首先如果 \(n-k<=k\) 則一定拿不到。

然後根據鴿巢原理。因為一對耳機有兩個頭，最壞情況是每對都只拿了一個頭即 \(n-k\) 個耳機，還要補上 \(k+1\) 個耳機湊成 \(k+1\) 對，因此一共要拿 \(n+1\) 個耳機。

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

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

程式碼

#include <bits/stdc++.h>

using namespace std;

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

Tags: 比賽題解

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

A

題解

程式碼

B

題解

程式碼

C

題解

程式碼

D

題解

程式碼

F

題解

程式碼

G

題解

方法一

方法二

程式碼

方法一

方法二

H

題解

程式碼

K

題解

程式碼

VirMach 便宜 VPS

QNews

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

A

題解

程式碼

B

題解

程式碼

C

題解

程式碼

D

題解

程式碼

F

題解

程式碼

G

題解

方法一

方法二

程式碼

方法一

方法二

H

題解

程式碼

K

題解

程式碼

分享此文：

Related Posts

白話電子簽章原理及風險

內網滲透之Windows認證（二）

造車新勢力頭部玩家易主：「蔚小理」格局瓦解

大理洱海變人山人海：每天1萬人、馬糞遍布景區

VirMach 便宜 VPS

QNews

熱門文章

熱門搜尋