[USACO18DEC] S 补题报告

本文主要是介绍[USACO18DEC] S 补题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 AC情况

Convention S	Convention II S	Mooyo Mooyo S
$\text{Accepted}$	$\text{Accepted}$	$\text{Unaccepted}$（$\text{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$ 个干草组成，那么这个连通块可以被消除。消除后剩下的干草又会因为重力下落，它们当中有可能会组成新的可以消除的连通块……循环往复，直到所有干草都无法消除为止。

问最后屏幕的布局。

赛时经历

1. 没有想到连通块在屏幕任何地方都可以删，而是只删了屏幕底下的连通块

2. 没有发现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()干草下落到底部elses[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;
}

这篇关于[USACO18DEC] S 补题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---