Educational Codeforces Round 97 (Rated for Div. 2) （A - C题个人题解）

1437A. Marketing Scheme

题意：最近猫粮店正在打折销售猫粮罐头，在给定客人能买的罐头数量区间内求合适包装大小

思路：说实话，在比赛刚开始没看懂题，最后放弃读题直接研究给出的样例解释发现，我们可以假设 \(a = r + 1\) 再进行比较 \(l \% a >= \frac{(a + 1)} 2\)

void solve() {
    ll l, r;
    cin >> l >> r;
    ll a = r + 1;
    if (l % a >= (a + 1) / 2) cout << "YES\n";
    else cout << "NO\n";
}

1437B. Reverse Binary Strings

题意：给定一个偶数长度的01字符串，求如何在最少的区间反转使得 字符串变为 “101010..."样式

思路：想清楚我们需要得到的是 10"串，那么对于其他情况都是不合法的 ”11，00“对于这些我们进行统计，最后只需要 \(k / 2\)即可

这个思路是比赛过程中观察而来的，证明待补。。。

void solve() {
    cin >> n >> s, k = 0;
    s[n] = s[0];
    for (int i = 0; i < n; ++i)
        if (s[i] == s[i + 1]) k++;
    cout << k / 2 << endl;
}

1437C. Chef Monocarp

题意：我们有一位高级厨师，他知道每一道菜的美味时间 \(t_i\)，但他每一分钟只能端出一道菜（已经拿出来的不能放回），如果拿出则回产生一个不愉快值 \(|T - t_i|\) ,求问怎么取出所有的菜的同时使总的不愉快值最小

思路：经典动态规划问题（脑抽写错了），这道题建议直接看代码理解。

// Author : RioTian
// Time : 20/10/28
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 210;
int dp[N][N << 1], n, _;
void solve() {
    cin >> n;
    int a[n + 1];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    //模拟时间变化
    for (int j = 1; j <= n; ++j)
        for (int i = j; i <= 2 * n; ++i) {
            int c = 1e6;
            for (int k = j; k <= i; ++k)  //求出每道菜最小的不愉快值
                c = min(c, abs(k - a[j]) + dp[j - 1][k - 1]);
            dp[j][i] = c;
        }
    cout << dp[n][n << 1] << endl;
}
int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> _;
    while (_--) solve();
}

Educational Codeforces Round 97 (Rated for Div. 2) （A - C题个人题解）

原文：https://www.cnblogs.com/RioTian/p/13892935.html