USACO 2024 January Contest, Bronze

[USACO24JAN] Majority Opinion B

题目描述

Farmer John 有一项重要的任务——弄清楚要为他的奶牛们购买什么类型的干草。

Farmer John 的 $N$ 头奶牛（$2\le N\le {10}^5$）编号为 $1$ 到 $N$，每头奶牛喜欢恰好一种类型的干草 $h_i$（$1\le h_i\le N$）。他希望他的所有奶牛都喜欢同一种干草。

为了实现这一目标，Farmer John 可以主持焦点小组访谈。一次焦点小组访谈为让编号从 $i$ 到 $j$ 的连续范围内的所有奶牛聚集在一起参加一次访谈。如果有一种干草是小组中超过一半的奶牛喜欢的，则此次焦点小组访谈结束后，所有奶牛最终都会喜欢这种干草。如果不存在这种类型的干草，那么奶牛们不会改变她们喜欢的干草类型。例如，在由 $16$ 头奶牛组成的焦点小组访谈中，需要有其中 $9$ 头或更多的奶牛具有相同的干草喜好，才能使其余奶牛改变其喜好以与之一致。

Farmer John 想知道哪些类型的干草有可能变为同时受到所有奶牛的喜爱。他一次只能主持一个焦点小组访谈，但为了使所有奶牛都喜欢同一类型的干草，他可以根据需要任意多次地主持焦点小组访谈。

输入格式

输入的第一行包含一个整数 $T$，为独立的测试用例的数量（$1\le T\le 10$）。

每一个测试用例的第一行包含 $N$。

第二行包含 $N$ 个整数，为奶牛们喜爱的干草类型 $h_i$。

输入保证所有测试用例的 $N$ 之和不超过 $2\cdot {10}^5$。

输出格式

输出 $T$ 行，对于每个测试用例输出一行。

如果可能使所有奶牛同时喜欢同一种干草，则以升序输出所有可能的此类干草的类型，否则输出 $-1$。在同一行内输出一列整数时，相邻的数用空格分隔，并确保行末没有多余空格。

输入输出样例 #1

输入 #1

5
5
1 2 2 2 3
6
1 2 3 1 2 3
6
1 2 1 2 2 2
3
3 2 3
2
2 1

输出 #1

2
-1
1 2
3
-1

说明/提示

样例解释

在输入样例中，有 5 个测试用例。

在第一个测试用例中，仅可能使所有奶牛喜欢种类 $2$。FJ 可以通过主持一次所有奶牛的焦点小组访谈达到这一目的。

在第二个测试用例中，可以证明没有奶牛会改变她们喜爱的干草种类。

在第三个测试用例中，有可能使所有奶牛喜欢种类 $1$，可以通过主持三次焦点小组访谈达到这一目的——首先使奶牛 $1$ 到 $4$ 进行一次焦点小组访谈，随后使奶牛 $1$ 到 $5$ 进行一次焦点小组访谈，随后使奶牛 $1$ 到 $6$ 进行一次焦点小组访谈。以类似的逻辑，依次操作奶牛 $3$ 到 $6$，随后是奶牛 $2$ 到 $6$，随后是奶牛 $1$ 到 $6$，我们可以使所有奶牛喜欢种类 $2$。

在第四个测试用例中，有可能使所有奶牛喜欢种类 $3$，可以通过主持一次所有奶牛的焦点小组访谈达到这一目的。

在第五个测试用例中，可以证明没有奶牛会改变她们喜爱的干草种类。

测试点性质

• 测试点 $2$：$N=2$。
• 测试点 $3-4$：$N\le 50$。
• 测试点 $5-6$：对于所有的 $1\le i\le N-1$，有 $h_i\le h_{i+1}$。
• 测试点 $7-15$：没有额外限制。

代码样例

#include<iostream>
using namespace std;
int T,n,h[100005];
bool f[100005];//用于标记此干草类型是否可能受到所有奶牛的喜爱 
int main(){
	scanf("%d",&T);//输入操作次数
	while(T--){
		scanf("%d%d",&n,&h[1]);
		for(int i=2;i<=n;i++){
			scanf("%d",&h[i]);
			if(!f[h[i]]&&(h[i]==h[i-1]||h[i]==h[i-2]))//判断h[i]是否符合要求
				f[h[i]]=true;//符合要求时打标记 
		}bool flag=true;//用于判断是否无解 
		for(int i=1;i<=n;i++)
			if(f[i])printf("%d ",i),f[i]=flag=false;//别忘记将f数组清零
		if(flag)printf("-1");//无解时，输出-1
		putchar('\n');//最后注意要输出换行符
	}
return 0;
}

[USACO24JAN] Cannonball B

题目描述

Bessie 已经精通了变成炮弹并沿着长度为 $N$（$1\le N\le {10}^5$）的数轴弹跳的艺术，数轴上的位置从左到右编号为 $1,2,\cdots ,N$。她从某个整数位置 $S$（$1\le S\le N$）开始，以 $1$ 的起始能量向右弹跳。 如果 Bessie 的能量为 $k$，则她将弹跳至距当前位置向前距离 $k$ 处进行下一次弹跳。

从 $1$ 到 $N$ 的每个整数位置上均有炮击目标或跳板。每个炮击目标和跳板都有一个在 $0$ 到 $N$ 范围内的整数值。一个数值为 $v$ 的跳板会使 Bessie 的能量增加 $v$ 并反转她的方向。一个数值为 $v$ 的炮击目标会当着陆时能量不小于 $v$ 时被击破。着陆在炮击目标上不会改变 Bessie 的能量和方向。被击破的炮击目标将保持击破状态，Bessie 依然可以该炮击目标上弹跳，同样不会改变能量和方向。

如果 Bessie 弹跳无限长的时间或直到她离开数轴，她会击破多少个炮击目标？

如果 Bessie 开始时位于一个她可以击破的炮击目标，她会立刻这样做。类似地，如果 Bessie 开始时位于一个跳板，跳板的效果将在她第一次跳跃之前生效。

输入格式

输入的第一行包含 $N$ 和 $S$，其中 $N$ 为数轴的长度，$S$ 为 Bessie 的起始位置。

以下 $N$ 行描述了每一个位置。其中第 $i$ 行包含整数 $q_i$ 和 $v_i$，如果位置 $i$ 上有一个跳板则 $q_i=0$，位置 $i$ 上有一个炮击目标则 $q_i=1$，$v_i$ 是位置 $i$ 上的跳板或炮击目标的数值。

输出格式

输出一个整数，为将被击破的炮击目标数量。

输入输出样例 #1

输入 #1

5 2
0 1
1 1
1 2
0 1
1 1

输出 #1

1

输入输出样例 #2

输入 #2

6 4
0 3
1 1
1 2
1 1
0 1
1 1

输出 #2

3

说明/提示

样例解释 1

Bessie 从坐标 $2$ 开始，这是一个数值为 $1$ 的炮击目标，所以她立刻击破了它。然后她弹跳至坐标 $3$，这是一个数值为 $2$ 的炮击目标，所以她无法击破它。她继续弹跳至坐标 $4$，这改变了她的方向并将她的能量增加了 $1$，达到 $2$。她跳回至坐标 $2$，这是一个已经被击破的炮击目标，所以她继续弹跳。此时，她弹跳至了坐标 $0$，因此她停了下来。她击破了恰好一个炮击目标，位于坐标 $2$。

样例解释 2

Bessie 经过的路径为 $4\to 5\to 3\to 1\to 6$，下一次弹跳将会使她离开数轴（$11$）。她依次击破了炮击目标 $4,3,6$。

测试点性质

• 测试点 $3-5$：$N\le 100$。
• 测试点 $6-10$：$N\le 1000$。
• 测试点 $11-20$：没有额外限制。

代码样例

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long  // 使用 long long 类型，防止数据溢出

using namespace std;

int n, nw, p = 1, ti = 1, a[1000001], b[1000001], pd[1000001], pp[1000001], tt[1000001], ans;

signed main() {
    // 输入数轴长度和起始位置
    cin >> n >> nw;
    // 读取每个位置的物体类型和数值
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }

    // 模拟 Bessie 的弹跳过程
    while (nw >= 1 && nw <= n) {
        // 如果当前位置是炮击目标
        if (a[nw]) {
            // 如果炮击目标未被击破且当前能量足够击破
            if (!pd[nw] && p >= b[nw]) {
                pd[nw] = 1;  // 标记炮击目标已击破
                pp[nw] = p;  // 记录击破时的能量
                tt[nw] = ti; // 记录击破时的方向
                ans++;       // 增加击破的炮击目标数量
            }
            // 如果当前状态与之前击破该炮击目标时的状态相同，说明进入无限循环，直接退出
            else if (pp[nw] == p && tt[nw] == ti) {
                break;
            }
        }
        // 如果当前位置是跳板
        else {
            p += b[nw]; // 增加能量
            ti *= -1;   // 反转方向
        }
        // 计算下一次弹跳的位置
        nw += p * ti;
    }

    // 输出击破的炮击目标数量
    cout << ans;
    return 0;
}

[USACO24JAN] Balancing Bacteria B

题目描述

Farmer John 有 $N$（$1\le N\le 2\cdot {10}^5$）块草地排成一行，其中草地 $i$ 的细菌水平与健康草的细菌水平相差 $a_i$（$-{10}^{15}\le a_i\le {10}^{15}$）。例如，如果 $a_i=-3$，则草地 $i$ 的细菌水平比正常水平低 $3$，需要额外添加恰好 $3$ 个单位的细菌才能将其提高到被认为是健康的程度。

Farmer John 想要确保每一块草地都被修复至健康的细菌水平。方便的是，他有两种品牌的农药可以喷洒在他的田地里，一种可以添加细菌，另一种可以去除细菌。当 Farmer John 喷洒任一类型的农药时，他站在草地 $N$（最右边的草地）并为他的喷雾器选择功率等级 $L$（$1\le L\le N$）。

喷雾器对靠近 Farmer John 的草地效果最大，随着距离增加效果逐渐减弱。如果 Farmer John 选择添加细菌的农药，则 $L$ 单位的细菌将被添加至草地 $N$，$L-1$ 单位添加至草地 $N-1$，$L-2$ 单位添加至草地 $N-2$，以此类推。草地 $1\dots N-L$ 不会得到任何细菌，因为喷雾器设置的功率不足以到达它们。类似地，如果 Farmer John 选择去除细菌的农药，则 $L$ 单位的细菌将被从草地 $N$ 去除，$L-1$ 单位被从草地 $N-1$ 去除，以此类推。同样，草地 $1\dots N-L$ 将不受影响。

求 Farmer John 使用喷雾器的最少次数，使得每块草地都具有健康草的推荐细菌值。输入保证答案不超过 ${10}^9$。

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。

输入格式

输入的第一行包含 $N$。

第二行包含 $N$ 个整数 $a_1\dots a_N$，为每块草地的初始细菌水平。

输出格式

输出一个整数，为使每块草地都具有健康草的推荐的细菌值所需使用喷雾器的最少次数。

输入输出样例 #1

输入 #1

2
-1 3

输出 #1

6

输入输出样例 #2

输入 #2

5
1 3 -2 -7 5

输出 #2

26

说明/提示

样例解释 1

使用去除细菌的农药，功率等级为 $1$，使用五次。然后使用添加细菌的农药，功率等级为 $2$，使用一次。

测试点性质

• 测试点 $3-5$：$N\le {10}^3$，答案不超过 ${10}^3$。
• 测试点 $6-10$：$N\le {10}^3$。
• 测试点 $11-15$：没有额外限制。

代码样例

• 一篇带你速通差分算法（C/C++）-CSDN博客
• 题意：给定数组 a，可以在任意位置 i 加上（或减去）一个首项为 1，公差为 1，长度为 n−i+1（即结束点为 n）的等差数列。问需要加（或减）几个等差数列可使 a 中的值全为 0。

此题正解应为：二阶差分。

观察到

等差数列	1	2	3	4	5
差分一次	1	1	1	1	1
差分两次	1	0	0	0	0

可得结论：在差分两次后的数组的 i 位置上加 1，就等价于在原数组 i 至 n 上加上了一个首项为 1 公差为 1 的等差数列。

所以，数组 a 两次差分后所有数的绝对值的和，即为将原数列应加上等差数列的个数。

#include <iostream>
#include <cmath>
using namespace std;
long long n,a[200010],s[200010],s2[200010],ans=0;
//别忘了long long
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        s[i]=a[i]-a[i-1];
        s2[i]=s[i]-s[i-1];
        ans+=abs(s2[i]);
    }
    cout<<ans;
}