526互联

Educational Codeforces Round 152 (Rated for Div. 2)

发布时间 2023-07-29 20:14:56作者: ljfyyds

传送阵

T1 Morning Sandwich

题目大意

\(t\) 个测试，每个测试给三个正整数 \(b,c,h\)，分别表示面包和两种馅料的个数，每两个面包之间必须放一个馅料，问最多能摆几层?

思路

我们发现 \(c,h\) 所表示的两种馅料其实相差不大，所以我们可以分两种情况

  1. \(a>c+h\)

    因为开头总是面包，所以要+1，我们把(馅料+面包)看成一组，一共有 \((c+h)\) 组，每组 \(2\) 层，一共有 \(1+2(c+h)\) 层

  2. \(a≤c+h\)

    我们不停放面包，直到把面包放完，同样把(馅料+面包)看成一组，这里就有 \(2n\) 层，但由于开头要放一个，无法配对，所以只有 \(2n-1\) 层

#include <bits/stdc++.h>
using namespace std;
int n, a, b, c;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a >> b >> c;
        if (a > b + c)
            cout << 1 + (b + c) * 2 << endl;
        else if (a <= b + c)
            cout << a * 2 - 1 << endl;
    }
    return 0;
}

T2 Monsters

题目大意

已知 \(n\) 个怪的血量序列 \(a\)，每次可以对最高血量的怪造成 \(k\) 点伤害，求怪死亡的顺序。

思路

我们发现总有一个状态是所有怪物都没死，但是所有怪物的血量都小于等与 \(k\) ,这个时候易得所有怪物的血量为 \(a_i \bmod k\) ，但当 \(a_i\) 是 \(k\) 的倍数时，此时的血量为 \(k\)。

我们可以根据这个状态的血量进行排序，排序优先级为先排 \(a_i \bmod k\) ，若血量相同则按顺序排。

#include <bits/stdc++.h>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}

void solve()
{
    vector<pair<int, int>> a;
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        int start;
        cin >> start;
        if (start > k)
            start = start % k == 0 ? k : start % k;
        a.push_back({start, i});
    }
    sort(a.begin(), a.end(), cmp);
    for (auto p : a)
        cout << p.second << ' ';
    cout << endl;
}

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

T3 Binary String Copying

题目大意

给 \(t\) 个询问，每个询问给两个正整数 \(n, m\) 分别表示字符串 \(s\) 长度，操作次数

每次操作给两个数 \(l,r\) 表示将 \(l,r\) 区间进行排序，问在这些操作中字符串有多少可能

思路

\(000...111...\) 明显进行排序时是不会变的我们把它记为一个特殊的状态

我们建立两个数组 \(pre,next\) 分别代表第 \(i\) 个数之前的第一个 \(0\), 第 \(i\) 个数之后的第一个 \(1\)

然后我们发现对于每一个区间都有一个有效区间为\([l,r]\) 中的第一个 \(1\) 到最后一个 \(0\) 也就是

\[000...[101001....0]111... \]

接下来对于同一个区间进行排序显然只会有同一种结果，所以我们用\([next_l,pre_r]\) 为一个状态

这里对于产生同一种状态的话显然只能保留 \(1\) 种。

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n, m;
    cin >> n >> m;
    string str;
    cin >> str;
    vector<int> pre0(n, -1), next1(n, n);
    for (int i = 0; i < n; i++)
    {
        if (i > 0)
            pre0[i] = pre0[i - 1];
        if (str[i] == '0')
            pre0[i] = i;
        if (n - i - 1 < n - 1)
            next1[n - i - 1] = next1[n - i];
        if (str[n - i - 1] == '1')
            next1[n - i - 1] = n - i - 1;
    }
    set<pair<int, int>> st;
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        if (next1[l - 1] > pre0[r - 1])
            st.emplace(-1, -1);
        else
            st.emplace(next1[l - 1], pre0[r - 1]);
    }
    cout << st.size() << endl;
}

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

T4 Array Painting

题目大意

有 \(n\) 个格子，第 \(i\) 个格子上的数字为 \(a_i\)。一开始，所有格子都是蓝色的。你可以进行以下两种操作若干次：

一、花费一枚硬币，把一个蓝色的格子染成红色。

二、选择一个红色的且数字不为 \(0\) 的格子以及其旁边的一个蓝色的格子，把红色格子上面的数字减一，并把蓝色格子染成红色。

求至少要花费多少枚硬币，使得所有格子都被染成红色？

思路

我们考虑 \(dp\)

设 \(dp_{i,j}\) 为考虑前 \(i\) 个，第 \(i\) 格状态为 \(j\) 的最小代价。

首先我们肯定要先将第 \(i\) 个自己涂了，这里只有两种涂法，一个是直接涂，一个是从别人那里拿过来过来

\[dp_{i,a_i}=\min\{dp_{i-1,0}+1,dp_{i-1,1},dp_{i-1,2}\} \]

然后我们发现一种情况

\[101112 \]

当我们从 \(2\) 这个地方开始时，往左覆盖，直到覆盖到 \(0\) 这个位置，因为如果不是 \(0\) 就一定 \(>0\) 能够继续往前覆盖(自力更生)

设 \(pre0_i\) 为 从 \(i\) 往前走第一个出现 \(0\) 的位置

\[dp_{i,j}=\min\{dp_{pre_i-1,1},dp_{pre_i-1,2},dp_{pre_i-1,0}\}+1 \]

这里这么写其实是把 \([1,i]\) 分成了两个部分，其中 \([1,pre_i-1]\) 的价值为 \(dp_{pre_i-1,(0/1/2)}\)

\([pre_i,i]\) 的价值为 \(1\) ，然后两者相加即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
 
int n;
int a[N], pre0[N], dp[N][3];
int main()
{
    //输入
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    // 初始化
    memset(dp, 0x3f, sizeof(dp));
    dp[0][1] = dp[0][0] = dp[0][2] = 0;
    dp[1][a[1]] = 1;
    //处理数据
    for (int i = 1; i <= n; i++)
        pre0[i] = a[i] ? pre0[i - 1] : i;
    //动态规划解决问题
    for (int i = 2; i <= n; i++)
    {
        dp[i][a[i]] = min(dp[i - 1][0] + 1, min(dp[i - 1][1], dp[i - 1][2]));
        if (a[i] > 0)
            dp[i][a[i] - 1] = min(dp[pre0[i] - 1][0], min(dp[pre0[i] - 1][1], dp[pre0[i] - 1][2])) + 1;
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2]});
    return 0;
}