[USACO18DEC] S 补题报告

1 AC情况

Convention S	Convention II S	Mooyo Mooyo S
$\texttt{\color{green}{Accepted}}$	$\texttt{\color{green}{Accepted}}$	$\texttt{\color{red}{Unaccepted}}$ （ $\texttt{\color{green}{Accepted}}$ ）

2 题目详情

Convention S

P5119 [USACO18DEC] Convention S - 洛谷

题目描述

$N$ 头奶牛，奶牛 $i$ 在时刻 $t_i$ 到达。安排 $M$ 辆车，每辆最多能坐 $C$ 头奶牛。

安排奶牛乘车。当最后一头乘坐某辆车的奶牛到达的时候，这辆车就可以发车了。如果没有到达，那么其他要乘坐这辆车的奶牛就要等待到发车的时刻。

求等待时间最长的奶牛等待的时间的最小值。

赛时经历

二分，思路正确。但调试时出现了一些细节问题。

题解

等待时间最长的奶牛等待的时间的最小值

经典二分。

#include <bits/stdc++.h>
#define endl '\n'
#define CLOSE ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, m, c, t[N], ans, maxn;
bool check(ll mid) {
    ll bus = 0, cnt = t[1], num = 0;
    for (int i = 1; i <= n; i++) {
        if (num >= c || t[i] - cnt > mid)
            bus++, num = 0, cnt = t[i];
        num++;
    }
    bus++;
    return (bus <= m);
}
int main() {
    CLOSE;
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i++) 
        cin >> t[i];
    sort(t + 1, t + n + 1);
    ll l = 0, r = t[n];
    while (l < r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l;
    return 0;
}

Convention II S

P5120 [USACO18DEC] Convention II S - 洛谷

题目描述

$N$ 头牛排队吃草，编号为 $i$ 的奶牛来排队的时刻为 $a_i$ ，吃草的时长为 $t_i$ 。

当轮到一头牛吃完草后，会从队伍中选择编号最靠前（最小）的奶牛先吃。

求所有奶牛在队伍里等待时间的最大值。

赛时经历

考场做法和赛后做法基本一致，唯一不同是赛时使用的是set来模拟队伍，稍繁琐一些。

题解

模拟。

首先把这些奶牛按照到达的时间排序，保证时间正确。

对于队伍里的吃草优先级问题，用priority_queue来模拟队伍是最简单的。结构体里面以编号为索引重载运算符。

具体模拟思路见代码。

#include <bits/stdc++.h>
#define endl '\n'
#define CLOSE                    \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
struct cow {
    ll i, a, t;
    bool operator<(const cow& x) const { return i > x.i; }  //吃草优先级
} a[N];
bool cmp(cow a, cow b) {  //到达时间排序
    return (a.a < b.a);
}
priority_queue<cow> q;  //模拟队伍
int main() {
    CLOSE;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].a >> a[i].t, a[i].i = i;
    sort(a + 1, a + n + 1, cmp);  //按到达时间排序
    ll cnt = a[1].a, i = 1, ans = 0; 
    //i表示前(i-1)头奶牛都进入队伍过了，轮到第i头了；
    //cnt表示当前的时刻；
    //ans记录答案
    while (i <= n || !q.empty()) { 
        //i <= n说明有奶牛没进过队伍；!q.empty()说明队伍里的奶牛还没有处理完
        if (q.empty() && i <= n)  //队伍空了，且还有没入队过的，放进去一个
            q.push(a[i]), i++;
        cow k = q.top();  //取出队头，吃草优先级最大的那头奶牛
        q.pop();
        while (a[i].a <= (max(cnt, k.a) + k.t) && i <= n)  
            //如果奶牛i在奶牛k吃完之前（或正好吃完时）到达，把奶牛i放进队伍
            q.push(a[i]), i++;
        ans = max(ans, cnt - k.a); //ans记录奶牛k等待最大值
        cnt = max(cnt, k.a) + k.t; //cnt时间更新
        //补充解释一下cnt更新的策略:
        //一种情况是奶牛k之前的奶牛用掉的总时长超过了奶牛k的到达时间，应该取更长的时间cnt + k.t
        //另一种情况是奶牛k到达时队伍里没有人，取更长的时间k.a + k.t
    }
    cout << ans;
    return 0;
}

Mooyo Mooyo S

P5121 [USACO18DEC] Mooyo Mooyo S - 洛谷

题目描述

$N$ 行 $10$ 列的屏幕，其中有类型 $1\sim 9$ 的不同类型的干草（每一捆干草占 $1$ 格，没有干草用 $0$ 表示)。受重力作用，它们落在所在列的最下面。

相同类型的且相连（上下左右方向相邻) 的若干干草成为一个连通块。如果一个连通块有由不少于 $K$ 个干草组成，那么这个连通块可以被消除。消除后剩下的干草又会因为重力下落，它们当中有可能会组成新的可以消除的连通块……循环往复，直到所有干草都无法消除为止。

问最后屏幕的布局。

赛时经历

没有想到连通块在屏幕任何地方都可以删，而是只删了屏幕底下的连通块
没有发现dfs()代码的隐藏漏洞，还是样例造的不够好
```
void dfs(int x, int y, char c, bool flag) {
    if (x < 1 || y < 1 || x > n || y > 10 || s[x][y] != c || vis[x][y])
        return;
    vis[x][y] = 1;
    cnt++;
    dfs(x - 1, y, c, flag);
    dfs(x + 1, y, c, flag);
    dfs(x, y - 1, c, flag);
    dfs(x, y + 1, c, flag);
    if (flag)
        vis[x][y] = 0;
}
```
这是赛时的dfs()代码，该代码希望在flag为true时用cnt来统计连通块内干草的数量。看起来思路没有错误，样例也没有问题，但在大测试点下很容易地出现了纰漏。

思考一个简单的矩形连通块:
```
11
11
```
很显然，从左上开始，进行dfs(左上)，然后进入dfs(左下)，接着到dfs(右下)，最后是dfs(右上)，cnt增加到了 $4$ ，然后最终回溯到了dfs(左上)。这一次搜索到这里就应该结束了。但是，在回溯过程中vis标记数组又还原成了 $0$ ，这看似合乎寻常，但其中隐藏着巨大的缺陷——那就是回溯到dfs(左上)后不知道右上已经被搜过了，又进入了dfs(右上)，然后依次是dfs(右下)、dfs(左下)，cnt增加到了 $7$ 才停止。

所以，这段代码的漏洞就在于，vis没有标记好搜索路线，因为迅速更新覆盖了搜索路径痕迹，导致出现多次访问。

题解

模拟。

dfs()：统计连通块干草数量。为了保证记录不重复，我们不对vis数组进行还原操作。

void dfs(int x, int y, char c) {
    if (x < 1 || y < 1 || x > n || y > 10 || s[x][y] != c || vis[x][y])
        return;
    vis[x][y] = 1;
    cnt++;
    dfs(x - 1, y, c);
    dfs(x + 1, y, c);
    dfs(x, y - 1, c);
    dfs(x, y + 1, c);
}

recover()：如果连通块干草数量少于 $K$ 个，执行此操作。此函数会把先前dfs()的搜索痕迹删除掉，即还原vis数组。没有被还原的vis数组标记的地方视为要删除的干草位置。

void recover(int x, int y, char c) {
    if (x < 1 || y < 1 || x > n || y > 10 || s[x][y] != c || !vis[x][y])
        return;
    vis[x][y] = 0;
    recover(x - 1, y, c);
    recover(x + 1, y, c);
    recover(x, y - 1, c);
    recover(x, y + 1, c);
}

organize()：搜索并标记完所有需要删除的连通块后执行此操作。它将删除vis数组标记的位置的干草，并整理屏幕。

void organize() {
    queue<char> q;  //q保存的是每一列没有删除的干草
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 10; j++)
            if (vis[i][j])
                s[i][j] = '0';  //删除被vis标记的干草
    for (int i = 1; i <= 10; i++) {
        for (int j = n; j >= 1; j--)
            if (s[j][i] != '0')
                q.push(s[j][i]);  //如果还有干草，放到q里准备下落
        for (int j = n; j >= 1; j--) {
            if (!q.empty())
                s[j][i] = q.front(), q.pop();  //把q.top()干草下落到底部
            else
                s[j][i] = '0';  //下落完了，更新旧屏幕单元格
        }
    }
    memset(vis, 0, sizeof vis);  //重置vis数组
}

主函数main()：不断重复搜索连通块、标记可删除连通块、整理屏幕过程，知道无可删除连通块为止。

int main() {    
    CLOSE;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> s[i], s[i] = " " + s[i];
    int flag = 1;
    while (flag) {
        flag = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 10; j++) {
                if (s[i][j] == '0' || vis[i][j])  //如果是空白单元格或者已经被标记过了，无需搜索
                    continue;
                cnt = 0;
                dfs(i, j, s[i][j]);  //搜索
                if (cnt < k) {  //清除搜索区域痕迹
                    recover(i, j, s[i][j]);
                } else {
                    flag = 1;  //有可以删除的连通块，标记
                }
            }
        }
        organize();  //整理屏幕
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 10; j++)
            cout << s[i][j];
        cout << endl;
    }
    return 0;
}