牛客小白月赛85

A	ACCEPT	点击查看	943/1484	通过
B	咕呱蛙	点击查看	853/2130	通过
C	得分显示	点击查看	526/2489	通过
D	阿里马马与四十大盗	点击查看	269/1993	通过
E	烙饼	点击查看	56/322	通过

A

解题思路:

统计每个字符的数量，算。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> cnt(30);
    for (auto c : s)
    {
        cnt[c - 'A']++;
    }
    int ans = 1e5;
    ans = min(ans, cnt['A' - 'A']);
    ans = min(ans, cnt['C' - 'A'] / 2);
    ans = min(ans, cnt['E' - 'A']);
    ans = min(ans, cnt['P' - 'A']);
    ans = min(ans, cnt['T' - 'A']);
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B

解题思路:

观察可知，前缀规律为\(奇数，奇数，偶数，偶数，奇数，奇数，。。。\)

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    ll n;
    cin >> n;
    ll cnt = 0;
    if (n & 1)
    {
        cnt = n * 2 + 1;
    }
    else
    {
        cnt = n * 2;
    }
    cout << cnt << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C

解题思路:

浮点出二分即可。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
const double eps = 1e-5 ;
void solve()
{
    ll n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    double l = 0;
    double r = 1e9 + 1;
    auto check = [&](double mid)
    {
        double cur = 0;
        for (int i = 1; i <= n; i++)
        {
            cur += mid;
            if (cur < a[i])
            {
                return true;
            }
            if (cur >= a[i] + 1)
            {
                return false;
            }
        }
        return true;
    };
    while (r - l >= eps)
    {
        double mid = (l + r) / 2;
        if (check(mid))
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    printf("%.10lf\n", r);
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D

解题思路:

预处理前缀和。

枚举每个合法的零点到终点，去最小值即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
const double eps = 1e-5;
void solve()
{
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    ll ans = 1e18;
    ll cur = 0;
    for (int i = 2; i <= n; i++)
    {
        if (a[i])
        {
            cur += a[i];
        }
        else
        {
            if (cur >= m)
            {
                puts("NO");
                return;
            }
            cur = 0;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] += a[i - 1];
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] - a[i - 1] == 0 && (a[n] - a[i - 1]) < m)
        {
            // cout << i << ' ' << a[i] << endl;
            ans = min(ans, n - 1 + a[i]);
        }
    }
    // puts("YES");
    cout << ans;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E

解题思路:

\(最短时间 = max(\lceil\frac{\sum a}{m}\rceil,max(a[i]))\)。

如果烙饼机的数量大于饼数，那么所有饼一起烙。否则，有空位就放上去，均摊。

每个饼最多被烙两次，因为只有\(a[i] \geq 最短时间 + 2\)，一个饼才会要被迫均摊到三份上，但与设定矛盾。

所以，对于每个烙饼机，我们直接锁定时间上界为最短时间，然后贪心构造即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
const double eps = 1e-5;

struct node
{
    ll a, b, c, d;
};

void solve()
{
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n + 1);
    ll s = 0;
    ll mx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s += a[i];
        mx = max(mx, a[i]);
    }
    vector<node> ans;
    vector<ll> cnt(m + 1);
    ll res = max(mx, (s + m - 1) / m);
    int idx = 1;
    for (int i = 1; i <= m; i++)
    {
        while (idx <= n && a[idx] + cnt[i] <= res)
        {
            ans.push_back({idx, i, cnt[i], cnt[i] + a[idx]});
            cnt[i] += a[idx];
            idx++;
        }
        if (idx > n)
        {
            break;
        }
        if (cnt[i] == res)
        {
            continue;
        }
        else
        {
            ans.push_back({idx, i, cnt[i], res});
            a[idx] -= res - cnt[i];
            cnt[i] = res;
        }
    }
    cout << ans.size() << endl;
    for (auto v : ans)
    {
        cout << v.a << ' ' << v.b << ' ' << v.c << ' ' << v.d << endl;
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}