牛客小白月赛85

发表于 更新于 分类于 阅读次数： 本文字数： 761 阅读时长 ≈ 3 分钟
Rome was not built in a day.

A. ACCEPT

思路：

  • ACCEPT中每个字符的个数取最小值(C的个数要除以2)

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    std::map<char, int> cnt;
    for (auto x : s) {
        cnt[x]++;
    }

    std::cout << std::min({cnt['A'], cnt['C'] / 2, cnt['E'], cnt['P'], cnt['T']}) << "\n";
}

B. 咕呱蛙

思路：

  • 打表找规律即可，代码的下面有注释打表的过程，\(\Sigma_{i=1}^{n}\Sigma_{j=1}^{i}\) 的每一项和是两个奇数两个偶数互相交替出现的，然后可以直接得出规律
  • \(n\) 为奇数，\(ans=n \times 2\)
  • \(n\) 为偶数，\(ans=n \times 2 + 1\)​

时间复杂度：\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    i64 n;
    std::cin >> n;

    i64 ans = -1;
    if (n % 2 == 0) {
        ans = n * 2;
    } else {
        ans = n * 2 + 1;
    }
    std::cout << ans << "\n";

    return 0;
}
/*
1 2 3 4  5  6  7  8  9  10 11 12 13 14  15  16  17  18  19  20
1 3 6 10 15 21 28 36 47 57 68 80 93 107 122 138 155 173 192 212
*/

C. 得分显示

思路：

  • 答案为 \(\Sigma_{i=1}^{n}min((a_i+1) \div i)\)

附：\(a_i + 1\)​ 即为当前这个数的右极限

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    double x = 2e9;
    for (int i = 0; i < n; i++) {
        x = std::min(x, (a[i] + 1) * 1.0 / (i + 1));
    }
    std::cout << x << "\n";

    return 0;
}

D. 阿里马马与四十大盗

思路：

  • 会发现只需要维护当前位置的后缀和即可
  • 如果当前位置的后缀和大于当前的血量，并且当前的血量不是满的，那么一定是越早回复花费的时间越少
  • 注意要判断当前位置是否等于0

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + a[i];
    }

    i64 b = m, t = n - 1;
    for (int i = 0; i + 1 < n; i++) {
        i64 suf = s[n] - s[i + 1];

        if (b != m && b - suf <= 0 && a[i] == 0) {
            t += m - b;
            b = m;
        }
        if (b - a[i + 1] > 0) {
            b -= a[i + 1];
        } else {
            std::cout << "NO\n";
            return 0;
        }
    }
    std::cout << t << "\n";

    return 0;
}

E. 烙饼

思路：

  • 可以发现，我们需要维护一个可以在最短时间内完成尽可能多的饼
  • 那么一定要确定一个时间的最大值 \(max(\lceil \frac{\Sigma_{i=1}^{n}a_i}{m} \rceil, max(a_i))\)
  • 然后维护这最大值即可

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    i64 mx = *max_element(a.begin(), a.end());
    i64 sum = std::accumulate(a.begin(), a.end(), 0ll);

    int tot = 1; i64 now = 0;
    mx = std::max((sum + m - 1) / m, mx);
    std::vector<std::array<i64, 4>> ans;
    for (int i = 0; i < n; i++) {
        if (a[i] + now <= mx) {
            ans.push_back({i + 1, tot, now, now + a[i]});
            now += a[i];
            if (now == mx) {
                tot++, now = 0;
            }
        } else {
            ans.push_back({i + 1, tot, now, mx});
            a[i] -= (mx - now);
            tot++, now = a[i];
            ans.push_back({i + 1, tot, 0, now});
        }
    }

    std::cout << ans.size() << "\n";
    for (auto [a, b, c, d] : ans) {
        std::cout << a << " " << b << " " << c << " " << d << "\n";
    }

    return 0;
}