USACO2023 十二月份铜组比赛题解

Macw07

2024-01-15 10:25:49

发布于：浙江

136阅读

0回复

0点赞

USACO 十二月份铜组比赛题解

Subtitle: USACO December Bronze Problem Solutions

特别提醒：对于本题解的代码有任何的问题，可以在讨论区评论处留言。

第一题 - Candy Cow Feast：

作为USACO的第一道题目，这一题就是一道普普通通的模拟题目。根据题意模拟 $N$ 头奶牛对 $M$ 根糖果棒的进食行为即可。我们通过创建两个变量remainBegin和remainEnd来记录每一根糖果棒剩下的部分的区间即可。

注意事项： 若奶牛的高度为 $H$ ，且remainBegin = 5, remainEnd = 7，如果 $H >= remainBegin$ 即表示这一头奶牛可以吃到这根糖果棒的一部分，我们就需要考虑这头奶牛是否能吃完剩下的所有部分。若 $remainEnd > H >= remainBegin$ ，则代表奶牛无法吃完糖果棒，因此奶牛的新身高应该为 H += (H - remainBegin)。否则奶牛的新身高最多也就只有 H = H + remainEnd - remainbegin + 1。并且当这根糖果棒被吃完后，应当立即停止循环以免增加不必要的运行时间。

优化： 本题通过常规的模拟方法是可以通过官方的所有测试点的，但本题可以在此代码的基础上进一步地进行优化。通过观察题目中所给定的信息和数据来看，可以推断出能吃到糖果棒的奶牛们身高比定是从低到高排列的。举例而言，如果第 $i$ 头牛的身高比第 $i+1$ 头奶牛的身高要高，那么第 $i+1$ 头奶牛比定永远都吃不到糖果棒。也就是说，我们可以通过不断地维护一个单调上升的数组来保存每一头奶牛的信息，确保数组以内的所有奶牛都可以吃到糖果棒。并在每一回合的开始过滤掉那些不满足要求的奶牛，这样子可以大大的降低代码的时间成本。

本题的 C++ 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 2e5;

int n, m;
int cows[MAXN + 5];
struct node{
    int remainBegin;
    int remainEnd;
} arr[MAXN + 5];

signed main(){
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin >> cows[i];
    for (int i=1; i<=m; i++) {
        // 用结构体记录，也可以直接用两个变量记录。
        cin >> arr[i].remainEnd;
        arr[i].remainBegin = 1;

        // 每一头奶牛从头开始吃。
        for (int j=1; j<=n; j++){
            // 吃自己能吃的掉的部分。
            if (cows[j] >= arr[i].remainBegin){
                int length = cows[j] - arr[i].remainBegin + 1;
                cows[j] = min(cows[j] + (arr[i].remainEnd - arr[i].remainBegin + 1), cows[j] + length);
                arr[i].remainBegin += length;  // 闭区间。
                if (arr[i].remainBegin > arr[i].remainEnd) break;
            }
        }
    }
    for (int i=1; i<=n; i++) cout << cows[i] << endl;
    return 0;
}

第二题 - Cowntact Tracting：

这道题可以被理解成一个贪心最优化问题。解题的思路是先对题干中给定的数据进行分组，将连续地且同为受感染的奶牛分为一组并命名为感染块。通过观察预处理后的若干组感染块，为了使得一开始受感染的奶牛的数量尽可能的小，则可以推断出需要让受感染的天数尽可能的大才可以。因此现在的问题就被转换成了最多需要多少天才可以将初始状态感染成最终给定的感染状态。

为了寻找出最长的感染天数，我们就需要找到长度最短的那一个感染块 - 长度最短的感染块的长度限制了奶牛们被感染的最长天数。找到最短的那个长度后就可以随之找到最长感染的天数了。这里需要分类讨论，设 $len$ 为长度最短的感染块的长度：

如果这个长度最短的感染块在奶牛队列的头尾：天数 $T$ 的计算则为： $T = len - 1$ 。
如果这个长度最短的感染块在奶牛队列的中间：需要稍微使用一下数学思维，天数 $T$ 的计算则为： $T = (len-1) / 2$ 。

关于 $T$ 的计算的推导过程就不列举了，可以通过自己手动写几个例子来尝试一下。

在求解出最短天数之后，对于最短天数的那一个感染块来说，只需要最少1头牛就可以在最短天数内感染该感染块中的所有奶牛。那么，若其他的感染块的长度为 $K$ ，可以证明对于一个长度为 $K$ 的感染块来说，只需要最少 $ceil(K / (T \times 2 + 1))$ 头奶牛就可以覆盖完整一个感染块。其中， $T \times 2 + 1$ 表示的是在 $T$ 天内1头奶牛最多可以感染其他奶牛的个数。ceil()函数用于对数字向上取整（半头奶牛要算一头奶牛才行）。

最后根据以上公式逐一计算每一个感染组所需要的最少奶牛个数即可。

本题的C++代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 3e5;
int n, ans;
string str;
int days = 0x7f7f7f7f;

int main(){
    cin >> n >> str;

    int i, j;
    for (i=0; i<n; i++){
        if (str[i] == '1'){
            for (j=i; j<n; j++){
                if (str[j] == '0') break;
            }
            int length = j - i;
            // 计算出最多只能有多少天。
            if (i == 0 || j == n) days = min(days, length-1);
            else days = min(days, (length-1)/2);
            i = j - 1;  // 因为多了一个j++，所以剪掉一个j。
        }
    }

    for (i=0; i<n; i++){
        if (str[i] == '1'){
            for (j=i; j<n; j++){
                if (str[j] == '0') break;
            }
            int length = j - i;
            // 累加答案，对每一个感染块都进行天数的计算。
            ans += ceil(1.0*length/(days*2+1));
            i = j - 1;
        }
    }

    cout << ans << endl;
    return 0;
}

第三题 - Farmer John Actually Farms：

本题不保证解法最优。本题所使用的方法是模拟 + 数学常规不等式（没学过不等式的同学可以在网上搜寻一下有关不等式的一些视频观看）。首先，我们需要对FJ给定的植物数组进行一个排序，使得数组呈单调递增或单调递减的性质，方便后期进行处理。为方便起见，这里将会按照FJ对于植物的预期高度从低到高进行排序。排序完成后，可以保证第 $i$ 盆花的高度必须要小于第 $i+1$ 盆花的高度才可以。并且，第 $i+2$ 盆花的高度也必须要大于第 $i+1$ 盆花。

我们根据每一盆花的信息列出两条直线方程 $y1$ 和 $y2$ ，设 $X$ 为天数。我们需要做的是使得这个 $X$ 尽量的小。

$y1 = arr[i].change*X + arr[i].height$
$y2 = arr[i+1].change*X + arr[i+1].height$

若要保证 $y2 > y1$ ，可列出以下不等式：

$arr[i].change*X + arr[i].height < arr[i+1].change*X + arr[i+1].height$

对该不等式进行移项操作，使得所有的未知数在同一边：

$arr[i].change*X - arr[i+1].change*X < arr[i+1].height - arr[i].height$

因式分解不等式左半部分：

$X * (arr[i].change - arr[i+1].change) < arr[i+1].height - arr[i].height$

若 $arr[i].change - arr[i+1].change$ ，为正数，则不需要变号：

$X < (arr[i+1].height - arr[i].height) / ((arr[i].change - arr[i+1].change))$

如果不等式右半部分为负数，则证明 $X$ 无论如何都没有办法满足条件。说明第 $i+1$ 盆花永远都无法超越第 $i$ 盆花，因此输出 $-1$ 即可。
如果不等式右半部分为正数，则整个程序所能接受的最大天数应为该不等式得解，即第 $i+1$ 盆花在 $X$ 天之后就会被超越。可以求解出X的上限 upperLimit。

若 $arr[i].change - arr[i+1].change$ ，为负数，则不等式符号需要变换方向：

$X > (arr[i+1].height - arr[i].height) / ((arr[i].change - arr[i+1].change))$

如果不等式右半部分为负数，则在任意天数之后花的高度都不会被超越，说明永远都不会被超越。
如果不等式右半部分为正数，则只有等到天数大于解的时候才可以达到FJ的要求，即第 $i+1$ 盆花要超越第 $i$ 盆花至少要经过 $X$ 天。可以求出X的下限 lowerLimit。

只有在 $lowerLimit <= x <= upperLimit$ 的情况下才是合法的，才能保证每一盆花的高度都是符合FJ的心理预期。但同时也会出现 $upperLimit <= lowerLimit$ 的情况，因此也需要输出 $-1$ 。

根据以上不等式方程模拟代码即可。

本题的C++代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

// 需要开long long，int存不下。
#define int long long
const int MAXN = 2e5;
int t, n;

// node用于记录每一盆花的信息。
struct node{
    int height;  // 花的初始高度。
    int change;  // 花高度的变化率。
    int rank;  // FJ心中花的高度排名。
    // 对这些花按照FJ的排名从矮到高排序。
    bool friend operator < (node a, node b){
        return a.rank > b.rank;
    }
} arr[MAXN + 5];

signed main(){
    cin >> t;
    while(t--){
        // 变量初始化。
        int lowerLimit = 0;
        int upperLimit = 0x7f7f7f7f;

        cin >> n;
        for (int i=1; i<=n; i++) cin >> arr[i].height;
        for (int i=1; i<=n; i++) cin >> arr[i].change;
        for (int i=1; i<=n; i++) cin >> arr[i].rank;

        // 对每一盆花进行排序，按照FJ心中的要求排序。
        sort(arr+1, arr+1+n);

        for (int i=1; i<n; i++){
            // 两直线平行的情况：斜率相同。
            // 如果两盆花的增长率相同，就比较两盆花的高度。
            // 判断第i+1朵花是否永远都超越不了第i朵花。
            if (arr[i].change == arr[i+1].change){
                if (arr[i].height >= arr[i+1].height){
                    cout << -1 << endl;
                    goto end;
                }
                continue;
            } 

            // 斜率不同的情况：
            // 1. 如果第i+1朵花可以超过第i朵花的话需要多久？
            // 2. 如果第i+1朵花本身就超过了第i朵花，多久就会被反超？
            if (arr[i].change - arr[i+1].change < 0){
                // 第i+1朵花需要limit天才可以超越第i朵花。
                if (arr[i+1].height - arr[i].height < 0){
                    double limit = ((arr[i+1].height - arr[i].height)*1.0)/(arr[i].change - arr[i+1].change);
                    if ((int)floor(limit) == (int)ceil(limit)) limit = ceil(limit) + 1;
                    else limit = ceil(limit);
                    lowerLimit = max(lowerLimit, (int)limit);
                } else continue;  // 第i朵花永远不会超越第i+1朵花。
            } 

            else{
                if (arr[i+1].height - arr[i].height < 0){
                    // 第i+1朵花永远超不多第i朵花。
                    cout << -1 << endl;
                    goto end;
                } else{
                    // 第i+1朵花经过limit天后就会被第i朵花超越。
                    double limit = ((arr[i+1].height - arr[i].height)*1.0)/(arr[i].change - arr[i+1].change);
                    if ((int)floor(limit) == (int)ceil(limit)) limit = ceil(limit) - 1;
                    else limit = floor(limit);
                    upperLimit = min(upperLimit, (int)limit);
                }
            }

            // 不满足不等式的解。
            if (lowerLimit > upperLimit){
                cout << -1 << endl;
                goto end;
            }
        }

        cout << lowerLimit << endl;
        end: ;
    }
    return 0;
}

本题的Python代码如下：

import math
T = int(input())
cnt = 0

def solve():
	n = int(input())
	height = list(map(int, input().split()))
	change = list(map(int, input().split()))
	rank = list(map(int, input().split()))
	plants = []
	for i in range(n):
		plants.append([height[i], change[i], rank[i]])

	plants.sort(key=lambda x: x[2], reverse=True)
	# 循环10000天，看可以不可以达到目标，否则输出-1
	minimum = 0
	maximum = 100000000000

	for i in range(n-1):
		# 斜率相同
		if plants[i][1] == plants[i+1][1]:
			if plants[i][0] >= plants[i+1][0]:
				print(-1)
				return
			continue

		# 斜率不同
		a = plants[i][1] - plants[i+1][1]
		b =  plants[i+1][0] - plants[i][0]
		if a < 0:
			if b < 0:
				high = b / a
				if int(math.ceil(high)) == int(math.floor(high)):
					high = int(math.ceil(high)) + 1
				else:
					high = int(math.ceil(high))
				minimum = max(minimum, high)
			else:
				continue
		else:
			if b < 0:
				print(-1)
				return
			else:
				low = b / a
				if int(math.ceil(low)) == int(math.floor(low)):
					low = int(math.floor(low)) - 1
				else:
					low = int(math.floor(low))
				maximum = min(maximum, low)

		if minimum > maximum:
			print(-1)
			return

	print(minimum)

while cnt < T:
	cnt += 1
	solve()