[C++知识库]Educational Codeforces Round #71 (Rated for Div. 2) A~C

A. There Are Two Types Of Burgers (模拟)

题意：

制作汉堡分配题。

已知要制作一个汉堡包，需要两个面包和一个牛肉饼，制作一个鸡肉汉堡，需要两个面包和一个鸡排。

给定 b 个面包，p 个牛肉饼，f 个鸡排，一个汉堡包 h 元，一个鸡肉汉堡 c 元。

问你最大利润是多少。

思路：

不同的汉堡用的相同数量的面包，那么就先比较馍的性价比，先卖价值高的汉堡。

代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;

void solve()
{
    int b, p, f;
    cin >> b >> p >> f;
    int h, c;
    cin >> h >> c;

    int res = 0;
    if (h >= c){
        while (p && b > 1){
            res += h;
            b -= 2;
            p--;
        }
        while (f && b > 1){
            res += c;
            b -= 2;
            f--;
        }
    }
    else {
        while (f && b > 1){
            res += c;
            b -= 2;
            f--;
        }
        while (p && b > 1){
            res += h;
            b -= 2;
            p--;
        }
    }

    cout << res << endl;
}

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

    return 0;
}

B. Square Filling (暴力)

题意：

给定两个矩阵 A ,B，其中 B 中元素全都为 0，A 中元素既有 0 也有 1。

每次操作可以选定一个 2 × 2 的网格，将其中元素全部变为 1。问需要操作多少次才能将 B 变为 A。

思路：

由于题中并未要求最优解，且数据范围较小，可以直接暴力枚举。

枚举矩阵 A 中的每一个元素，如果该元素为 1，且右、下、右下元素均为 1，即将相对应的 B 中元素都变为 1，操作数 +1，并用 vector<pair<int, int> > 存储该元素的横纵坐标。最后逐个判断构造的 B 矩阵是否与 A 矩阵相同即可。

代码如下：

#include <bits/stdc++.h>
#define ll long long
#define PII pair<int, int>
using namespace std;
const int N = 55;

int n, m;
int a[N][N]; //目标矩阵A
int b[N][N]; //构造矩阵B

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    vector<PII> v;
    int res = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <=m; j++){
            if (a[i][j] && a[i + 1][j] && a[i][j + 1] && a[i + 1][j + 1]){
                b[i][j] = 1;
                b[i + 1][j] = 1;
                b[i][j + 1] = 1;
                b[i + 1][j + 1] = 1;

                v.push_back({i, j});
                res++;
            }
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (b[i][j] != a[i][j]){
                puts("-1");
                return 0;
            }
        }
    }

    cout << res << endl;
    for (auto [x, y] : v){
        cout << x << ' ' << y << endl;
    }

    return 0;
}

C. Gas Pipeline (模拟)

题意：

给定一个长度为 n 的 01 字符串，区间 (x, x + 1) 表示一个路口，其中 0 表示当前区间不包含路口，1 表示有路口。

通常我们将管道安装在 1 的高度上，如果有路口，则需要安装在 2 的高度上。

其中单位管道的费用为 a ，单位高度的支柱费用为 b ，求搭建管道的最小费用。

思路：

我看好多题解都是用的 dp，但其实贪心模拟也可以做。

设费用为 res ，初始状态下管道的高度一定为 1，因为管道和支柱是一种相互穿插的关系，每一单位管道其左右两边必定有支柱，即 n 条单位管道有 n + 1 条单位支柱，所以初始费用 res = n * a + (n + 1) * b 。

接着用 l 表示字符串中 1 第一次出现的位置，用 r 表示 1 最后一次出现且再后一位的位置，即 0 的位置，因为后面遍历的时候要加上此处 1 和 0 之间的支柱费用。

然后开始遍历，如果出现 1 ，高度升为 2，加上其费用 res += b ；如果出现 0 ，用 cnt 记录其连续出现的次数。

再判断 0 的连续个数：如果只是一个 0 ，就没必要将高度降为 1，即 res += b ，如果有多个 0 ，就要比较是将高度降为 1 还是保持高度 2 划算，即 res += min(2 * a, (cnt - 1) * b) 。

最后再加上头尾的 1 处升降的支柱费用。

代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;

void solve()
{
    ll n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    s = ' ' + s;

    ll res = (n + 1) * b + n * a; //初始化费用

    int l = 1, r = n;
    while (s[l] == '0' && l <= n) //找到第一个1
        l++;
    while (s[r] == '0' && r >= 1) //找到最后一个1
        r--;

    r++; //右移一位，将r定位到1右边的0


    int flag = 0;  //判断是否有1
    int cnt;       //记录连续0的个数
    for (int i = l; i <= r; )
    {
        cnt = 0;   //每次将个数重置为0
        while (s[i] == '1')
        {
            res += b;
            i++;
            flag = 1;
        }
        while (s[i] == '0' && i <= r)
        {
            cnt++;
            i++;
        }

        //连续的1后出现0，其左边必定是2的高度，先加上第二层的费用
        if (cnt > 0) res += b;  

        //如果有多个0，比较管道一次升降和加上第二层的费用
        if (cnt > 1) res += min(2 * a, (cnt - 1) * b);
    }

    if (flag) //存在1，则左右两端还要加上升降的费用
        res += 2 * a;

    cout << res << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    return 0;
}