题解：P1711 [USACO18FEB] Taming the Herd B

xuan_never · 2024-05-05 09:49:21 · 题解

题目传送门
题意明确，不在此赘述。

思路

我们要根据残留记录，反推出能确定的丢失的记录，求出最多与最少出逃次数。在我们确定了能确定的全部记录后，最少出逃次数即为记录中确定的出逃次数，最多出逃次数则要加上不确定记录的个数。

做法

枚举 1 从 n 至 1，对于 a_{i+1} 有记录的，理想 a_i=a_{i+1}-1（若 a_{i+1} 记录为 0 也正好使理想 a_i 为 -1）。
当 a_i 原本就有记录，但与理想记录不相等时，就出现了记录错误的情况，此时直接输出 -1。

最后记录记录中 \text{0},\text{-1} 的个数即可。

不要忘了记录第一天的出逃哦。

代码

// 码风很丑，勿喷

#include <iostream>
using namespace std;
int n, a[102], ans1, ans2; // ans1记录0，ans2记录-1
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    if (~a[1] && a[1]) { // 记录第一天的出逃，也要判断
        cout << -1;
        return 0;
    } a[1] = 0;
    for (int i = n, j; i >= 1; --i) {
        j = (~a[i + 1] ? a[i + 1] - 1 : -1); // 同上，理想ai
        if (~j) {
            if (~a[i] && a[i] != j) {
                cout << -1;
                return 0;
            } a[i] = j;
        } if (!a[i]) ++ans1; // 记录0和-1
        else if (a[i] == -1) ++ans2;
    } cout << ans1 << ' ' << ans1 + ans2;
    return 0;
}

赛前&第一次写题解，RP++。