img

牛客小白月赛85

ACCEPT

A题没什么好说的

统计一下

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
41
42
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 200010;
int a[N];

void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;

    int b = 0,c = 0,d = 0,e = 0,f = 0;

    for(int i = 0;i < s.size();i ++)
    {
        if(s[i] == 'A') b ++;
        if(s[i] == 'C') c ++;
        if(s[i] == 'E') d ++;
        if(s[i] == 'P') e ++;
        if(s[i] == 'T') f ++;
    }

    b = min(b,c / 2);
    b = min(b,d);
    b = min(b,e);
    b = min(b,f);

    cout<<b<<endl;
}
signed main(){
    ios::sync_with_stdio(false);	
	cin.tie(nullptr), cout.tie(nullptr);
    int T;
    //T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

咕呱蛙

规律题，题意卡了一会

1

1+2

1+2+3

1+2+3+4

问出现第x偶数时是第n个?

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;
int main() {
    unsigned long long n;
    cin >> n;
    if(n % 2 == 0) {
        cout << n * 2;
    }else {
        cout << n * 2 + 1;
    }
    return 0;
}

得分显示

第一种做法

明显二分

直接凑即可

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
#include <iostream>
#include <map>
#include <vector>
using namespace std;
#define int long long

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int zh = a[1];
    double l = 0, r = 1;
    while (r - l > 1e-6) {
        double mid = (l + r)/2.0;
        int f = 1;
        double c = 0;
        for (int i = 1; i <= n; i++) {
            c += zh + mid;
            if ((int)c > a[i]) {
                f = 0;
                break;
            }
        }
        if (f) l = mid;
        else r = mid;
    }
    printf("%.10lf", zh + l);
}

signed main() {
    //ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1; //cin >> T;
    while (T--) solve();
    return 0;
}

第二种做法

每次取极限即可：

更优秀做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
#define int long long
double ans =10000000000000;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int now;
        cin>>now;
        ans = min(ans,(now+1)/(double)i);
    }
    printf("%.6lf",ans);
}

阿里马马与四十大盗

能够回血早回血是最好的

不然后面回可能会耗费多余的时间。

注意特判能够一次通过

因此前缀和数组可以改成后缀和数组

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
41
42
43
44
45
46
#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;
}

烙饼

店里有 m 台烙饼机可以同时工作，一台烙饼机同时只能烙一个饼，而不同种类的饼烙制时长是不同的。为了节省时间，小利同学想出了一种独特的烙饼方法：把一张饼分成若干次烙制，即一张饼的烙制过程可以是不连续的（比如一张饼需要烙 8 分钟，可以选择在烙饼机 1 中烙 3 分钟，接着取出，去烙制别的饼，而后再取回该饼继续在任意烙饼机上烙 5 分钟 ）。店里的烙饼机烙制时长只能精确到分钟，因此小利只能在每张饼刚好烙制完整数分钟后将其取出。

由于是网红店，购买订单数量常常爆满，于是小利找到你，希望你根据 n 个饼的订单信息制定一份包含 k 条烙制记录的烙饼计划，使这天完成工作需要花费的时间最短（当然他也不希望这份计划太繁琐，因此在完成上述目标的前提下，还应该满足 1≤k≤2×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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10, M = 2 * N;
const int mod = 1e9 + 7;
//饼的时间 输出结果
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);
        //相当于ceil
    }
    // 烙饼机的序号 每个机器结束的时间  
    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;
}