题解 | #牛客小白月赛85#

声明：刚学编程的本人通过题目较少，如果不是自己比赛时AC的代码会在代码块末尾表明参考来源。

A-ACCEPT

只需要求出这五个字母中数量最小的就行了（C字符的数量一对算一个）

#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 1e6 + 10, M = 2e1 + 8;
const int mod = 1e9 + 7;
// setw(n) setfill('0') ## Add leading '0'
//===================================================
string s;
int a[30];
//===================================================

//===================================================
int main()
{
    int t, n;
    ios;
    cin >> t;
    while(t --)
    {
        int ans = INT_MAX;
        fill(a, a + 27, 0);
        cin >> n >> s;
        for(int i = 0; i < n; i ++)
            a[s[i] - 'A'] ++;
        int A = a[0];
        int C = a[2] / 2;
        int E = a[4];
        int P = a[15];
        int T = a[19];
        ans = min(A, min(C, min(E, min(P, T))));

        cout << ans << endl;
    }

    return 0;
}

B-咕呱蛙

简单的找规律题

alt

sum的排列规则为 “奇数奇数偶数偶数奇数奇数偶数偶数 …………”

可以得出来两个奇数，两个偶数的循环下去。所以可以直接写关系式做出来。

请看主要代码--

int main()
{
    ll n;
    cin >> n;
    if (n & 1) cout << 2 * n + 1 << endl;
    else cout << n * 2 << endl;

    return 0;
}

C-得分显示

解题思路

在int取整数时 $0.999……$ 会取为 $0$ , 而在做除法及输出时 $0.999……$ 就是 $1$ ，于是可以得出：
当（最末尾的数 + 1）/ （数量）时，算出来是最大的情况，答案会受前面的数的影响
比如“0 0 0 1” 最大为约为 $0.333……$ 从第一个数开始为 $0.99…， 0.99…， 0.33…， 0.50…$
每次除出来的都是最大的情况，取最大的时候的最小值即可。

#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 1e6 + 10, M = 1e9 + 8;
const int mod = 1e9 + 7;
// setw(n) setfill('0') ## Add leading '0'
//===================================================
int dp[N];
//===================================================

//===================================================
int main()
{
    int n;
    double res = M;
    ios;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> dp[i];
        res = fmin(1.0 * (dp[i] + 1) / i, res);
    }

    cout << LF(10) << res << endl;

    return 0;
}

D-阿里马马与四十大盗

思路

我一开始用前缀和贪心导致错误注意状态分析，用前缀和 + dp貌似也行（没试过）

贪心

如果要恢复血量，那么在可以走出迷宫的情况下，一定是越早恢复越好（需要恢复的血量少，时间花费少）。
所以每次都早早恢复血量，在判断后面能不能一次通过迷宫就好了。

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 2e5 + 10;
int mp[N];
ll a[N];
int main()
{
    int n, m;
    
    ios;
    cin >> n >> m;
    //花费的时间       血量
    ll cost_t = n - 1, temp;//若无需恢复就可通过，则消耗时间为n - 1
    for(int i = 1; i <= n; i ++) cin >> mp[i];
    //求后缀和
    for(int i = n; i >= 1; i --) a[i] = a[i + 1] + mp[i];
    //给血量赋初值
    temp = m;
    for(int i = 1; i <= n; i ++)
    {
      //=========以下判断是否无法走出迷宫===============
        if(mp[i] == 0)
        {
            cost_t += m - temp;
            temp = m;
        }
        else
        {
            temp -= mp[i];
            if(temp <= 0)
            {
                cout << "NO" << endl;
                break;
            }
        }
      //=========以上判断是否无法走出迷宫==============
        if(temp > a[i + 1])
        {
            cout << cost_t << endl;
            break;
        }
    }

    return 0;
}

参考代码 ——牛客288141082号

E-烙饼

思路

注意事项

易得所需的最短时间——脑子里自己模拟一下就行了

为 $maxn = max(max(a_i, maxn), (sum ＋ m - 1) / m)$
情况一：当某个烙饼的时间特别长时，那最短时间肯定为它
情况二：机器数比较少时，那时间分配就为均分
PS：+ m - 1的处理相当于 $ceil()$

一个饼最多被处理几次？

已经求出了所需最短时间，当（机器的结束时间）+（饼处理完全所需的时间）大于 $maxn$ 时，饼剩余的时间会到下一个机器中进行处理，所以饼最多处理2次。

模拟

下面请看代码部分

#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10, M = 2 * N;
const int mod = 1e9 + 7;
// setw(n) setfill('0') ## Add leading '0'
//===================================================
//饼的时间 输出结果
ll a[N],  b[M][6];
int len = 1;
//===================================================
//把求出来的数添加到b数组中，并记录长度
void add(ll id_1, ll id_2, ll l, ll r)
{
    b[len][1] = id_1;
    b[len][2] = id_2;
    b[len][3] = l;
    b[len][4] = r;
    len ++;
}
//===================================================
int main()
{
    int n, m;
    ll sum = 0, maxn = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        //计算烙饼最长需要多长时间
        sum += a[i];
        maxn = max(max(a[i], maxn), (sum + m - 1) / m);
    }
    // 烙饼机的序号 每个机器结束的时间  
    ll id_2 = 1,  start_tail = 0;
    for(int i = 1; i <= n; i ++)
    {
        //如果烙饼机结束的时间合法
        if(a[i] + start_tail <= maxn)
        {
            //储存起来
            add(i, id_2, start_tail, a[i] + start_tail);
            //更新这个烙饼机的结束时间
            start_tail += a[i];
            //如果烙饼机的结束时间刚好等于最大值，直接到下一个机器
            if(start_tail == maxn)
            {
                id_2 ++;//下一个机器
                start_tail = 0;//下一个机器的结束时间为0（未使用）
            }
        }
        //如果不合法，说明烙饼要分两次来完成
        else
        {
            //分两次来完成的第一个步骤
            add(i, id_2, start_tail, maxn);
            //剩下的步骤需要完成的时间
            a[i] -= (maxn - start_tail);
            //进行到下一个机器
            id_2 ++;
            //更新机器结束的时间
            start_tail = a[i];
            //储存于数组中
            add(i, id_2, 0, start_tail);
        }
    }
    //输出
    cout << len - 1 << endl;
    for(int i = 1; i < len; i ++)
        cout << b[i][1] << ' ' << b[i][2] << ' ' << b[i][3] << ' ' << b[i][4] << endl;
    return 0;
}

参考代码——牛客288141082号