2023牛客寒假算法基础集训营1

https://ac.nowcoder.com/acm/contest/46800
过了7题，写一半没撑住去睡觉了。
官方难度预期：

果然我还是很菜哇qaq

A - World Final? World Cup! (I)

模拟

#include <bits/stdc++.h>

using namespace std;

void solve() {
    string s;
    cin >> s;
    s = ' ' + s;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= 10; i++) {
        if (i & 1)    cnt1 += s[i] == '1';
        else    cnt2 += s[i] == '1';
        if (cnt1 == cnt2)    continue;
        int dx = abs(cnt1 - cnt2), add = (10 - i) / 2;
        if (i & 1) {
            if (cnt2 < cnt1)    add ++;
        }
        if (add < dx) {
            cout << i << endl;
            return;
        }
    }
    //cout << cnt1 << ' ' << cnt2 << endl;
    cout << -1 << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

B - World Final? World Cup! (II)

C - 现在是，学术时间 (I)

贪心。全部放到一个人身上

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, cnt = 0;
    cin >> n;
    while (n --) {
        int x;
        cin >> x;
        if (x)  cnt++;
    }
    cout << cnt << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

D - 现在是，学术时间 (II)

贪心构造，画图模拟点在内部和在外部的情况进行模拟。

#include <bits/stdc++.h>

using namespace std;
double ans;

int main() {
    int t;
    cin >> t;
    while (t --) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        if (a >= x && b >= y)    ans = 1.0 * x * y / (1.0 * a * b);
        else if (a >= x) {
            double j1 = 1.0 * x * b, j2 = 1.0 * x * (y - b), s1 = 1.0 * x * y + 1.0 * b * (a - x), s2 = 1.0 * x * y + 1.0 * (y - b) * (a - x);
            ans = max (j1 / s1, j2 / s2);
        }
        else if (b >= y) {
            double j1 = 1.0 * a * y, j2 = 1.0 * (x - a) * y, s1 = 1.0 * x * y + 1.0 * a * (b - y), s2 = 1.0 * x * y + 1.0 * (x - a) * (b - y);
            //cout << j1 << ' ' << j2 << ' ' << sum << endl;
            ans = max (j1 / s1, j2 / s2);
        }
        else {
            double s1 = 1.0 * a * b, s2 = 1.0 * (x - a) * b, s3 = 1.0 * a * (y - b), s4 = 1.0 * (x - a) * (y - b);
            ans = max ({s1, s2, s3, s4}) / (1.0 * x * y);
        }
        cout << fixed << setprecision (6) << ans << endl;
    }
}

E - 鸡算几何

F - 鸡玩炸蛋人

G - 鸡格线

H - 本题主要考察了DFS

贪心。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    int a[4] = {0};
    for (int i = 1; i < n * n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < 4; j++) { //0,2  1,3
            if (s[j] == '0')    continue;
            if (s[j] == '1')    a[j] ++;
            else    a[(j + 2) % 4] --;
        }
    }
    //for (int i = 0; i < 4; i++)     cout << a[i] << ' ';cout << endl;
    int ans = 0;
    for (int i = 0; i < 4; i++)     ans += a[i];
    cout << 10 + ans << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

I - 本题也主要考察了DFS

J - 本题竟也主要考察了DFS

K - 本题主要考察了dp

贪心绑定 \(001\)，查看剩余即可

#include <bits/stdc++.h>

using namespace std;
int n, m;

void solve() {
    cin >> n >> m;
    if (n - m < 2) {
        cout << max(0, n - 2) << endl;
        return ;
    }
    int cnt = (n - m) / 2 + 1;
    cout << max(0, m - cnt) << endl;
}

int main() {
    solve();
}

L - 本题主要考察了运气

如题。

#include<bits/stdc++.h>

using namespace std;

int main () {
    cout << 32;
}

M - 本题主要考察了找规律

线性dp。f[i][j]: 放完前i个人剩下j个

#include <bits/stdc++.h>

using namespace std;
const int N = 505;
double f[N][N], ans;

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) { //还剩j个
            for (int k = 0; k <= j; k++) { //这个人拿了k个
                if (j)    f[i][j] = max (f[i][j], f[i-1][j-k] + 1.0 * k / j);
            }
            ans = max (ans, f[i][j]);
        }
    }
    cout << fixed << setprecision (7) << ans;
}

//f[i][j]: 放完前i个人剩下j个