USACO 2025 US Open Contest, Bronze

[USACO25OPEN] Hoof Paper Scissors Minus One B

题目描述

在一局蹄子剪刀布游戏中，Bessie 和 Elsie 可以出 $N$ （ $1 \leq N \leq 3000$ ）种不同的蹄子手势，编号为 $1 \dots N$ ，每个手势对应一种不同的材料。不同材料之间的相互关系有一个复杂的表格，基于该表格，可能会：

一种手势获胜，另一种失败。
两种手势平局。

蹄子剪刀布-1.0 的规则类似，但 Bessie 和 Elsie 可以各自出两个手势，每只蹄子出一个。在观察到她们所出的四个手势后，她们各自选择其中一个手势进行游戏。结果根据正常的蹄子剪刀布的规则决定。

给定 Elsie 计划在每局游戏中出的 $M$ （ $1 \leq M \leq 3000$ ）个手势组合，Bessie 想知道有多少种不同的手势组合可以确保战胜 Elsie。一个手势组合定义为一个有序对 $(L, R)$ ，其中 $L$ 为奶牛用左蹄出的手势， $R$ 为奶牛用右蹄出的手势。你能为每局游戏进行计算吗？

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$ ，表示蹄子手势的数量，以及 Bessie 与 Elsie 进行的游戏局数。以下 $N$ 行，第 $i$ 行由 $i$ 个字符 $a_{i, 1} a_{i, 2} \dots a_{i, i}$ 组成，其中 $a_{i, j} \in {D, W, L}$ 。如果 $a_{i, j} = D$ ，则手势 $i$ 平于手势 $j$ 。如果 $a_{i, j} = W$ ，则手势 $i$ 胜于手势 $j$ 。如果 $a_{i, j} = L$ ，则手势 $i$ 负于手势 $j$ 。输入保证 $a_{i, i} = D$ 。

以下 $M$ 行，每行包含两个空格分隔的整数 $s_{1}$ 和 $s_{2}$ ，其中 $1 \leq s_{1}, s_{2} \leq N$ ，表示 Elsie 在该局游戏中的手势组合。

输出格式

输出 $M$ 行，其中第 $i$ 行包含在第 $i$ 局游戏中 Bessie 可以确保战胜 Elsie 的手势组合数量。

输入输出样例 #1

输入 #1

3 3
D
WD
LWD
1 2
2 3
1 1

输出 #1

0
0
5

说明/提示

在样例 1 解释：这对应于原始的蹄子剪刀布，我们可以设蹄子为 $1$ ，布为 $2$ ，剪刀为 $3$ 。布战胜蹄子，蹄子战胜剪刀，剪刀战胜布。Bessie 无法确保战胜蹄子 + 布或布 + 剪刀的组合。然而，如果 Elsie 出蹄子 + 蹄子，Bessie 可以采用以下任一组合进行反击。

布 + 布
布 + 剪刀
布 + 蹄子
蹄子 + 布
剪刀 + 布

如果 Bessie 出这些组合中的任意一个，她可以确保通过出布来获胜。

测试点 $2 \sim 6$ ： $N, M \leq 100$ 。
测试点 $7 \sim 12$ ：没有额外限制。

解题思路

能让Bessie胜利的方式必须为如下的【L，R】
- 【胜利手势，其他手势(平局/失败)】
- 【其他手势(平局/失败)，胜利手势】
- 【胜利手势，胜利手势】
所以找出能够战胜Elsie已给出两种手势的手势数量
然后根据公式统计出能胜利的最终手势组合数量： $a n s * (n * 2 - a n s)$

代码示例

C++

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

int a[3005][3005];//a[i][j]=1,则代表手势i胜于手势j。 

int main(){
	int i,j,k,ans = 0;
	int n,m;
	char c;
	cin >> n >> m;
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){
			cin >> c;
			if(c == 'W'){
				a[i][j] = 1; 
			}else if(c == 'L'){
				a[j][i] = 1;
			}
		}
	} 
	
	while(m--){
		ans = 0; 
		cin >> j >> k;
		for(i=1;i<=n;i++){
			if(a[i][j] && a[i][k]) ans++; 
		}	
		cout << ans*(n*2-ans) << endl; 
	}
	return 0;
}

[USACO25OPEN] More Cow Photos B

题目描述

今天奶牛们的心情特别顽皮！Farmer John 只是想拍摄一张奶牛们排成一行的照片，但她们总是在他得到机会按下快门之前移动位置。

具体地说，FJ 的 $N$ 头奶牛（ $1 \leq N \leq 10^{5}$ ）每一头的身高都是 $1$ 到 $N$ 的整数。FJ 想要拍摄奶牛以一种特定的顺序排成一行的照片。如果奶牛们排成一行时从左到右有身高 $h_{1}, \dots, h_{K}$ ，他希望奶牛们的身高拥有以下三个性质：

他希望奶牛们的身高先递增再递减。形式化地说，必须存在一个整数 $i$ 使得 $h_{1} \leq \dots \leq h_{i} \geq \dots \geq h_{K}$ 。
他不希望任何奶牛与另一头身高完全相同的奶牛相邻。形式化地说，对于所有 $1 \leq i < K$ 有 $h_{i} \neq h_{i + 1}$ 。
他希望照片是对称的。形式化地说，如果 $i + j = K + 1$ ，则 $h_{i} = h_{j}$ 。

FJ 希望照片中包含尽可能多的奶牛。具体地说，FJ 可以移除一些奶牛并重新排列余下的奶牛。计算 FJ 在满足他的限制的情况下可以在照片中包含的奶牛的最大数量。

输入格式

你需要回答多个测试用例。输入的第一行包含一个整数 $T$ （ $1 \leq T \leq 10^{5}$ ），为测试用例的数量。以下为 $T$ 个测试用例。

每一个测试用例的第一行包含一个整数 $N$ 。第二行包含 $N$ 个整数，为可用的 $N$ 头奶牛的身高。奶牛们的身高在 $1$ 到 $N$ 之间。

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

输出格式

输出 $T$ 行，第 $i$ 行包含第 $i$ 个测试用例的答案。每行包含一个整数，表示 FJ 可以在照片中包含的奶牛的最大数量。

输入输出样例 #1

输入 #1

输出 #1

3
1

说明/提示

对于第一个测试用例，FJ 可以选择身高为 $1$ ， $1$ 和 $3$ 的奶牛，并重新排列为 $[1, 3, 1]$ ，满足所有条件。对于第二个测试用例，FJ 可以选择身高为 $3$ 的奶牛以组成一张合法的照片。

测试点 $2 \sim 3$ ： $T \leq 100$ ， $N \leq 7$ 。
测试点 $4 \sim 5$ ： $T \leq 10^{4}$ ，所有奶牛的身高不超过 $10$ 。
测试点 $6 \sim 11$ ：没有额外限制。

解题思路

根据奶牛们的身高拥有以下三个性质，得出结论，奶牛的排列一定是先单调递增和在单调递减，且除了最高点的其他点都是对称出现，同一高度的点也只能出现两次(对称出现，递增一次，递减一次)。
- $h_{1} \leq \dots \leq h_{i} \geq \dots \geq h_{K}$ 。
- $1 \leq i < K$ 有 $h_{i} \neq h_{i + 1}$ 。
- $i + j = K + 1$ ，则 $h_{i} = h_{j}$ 。
利用数组占位思想，统计出相同高度出现的次数。
然后将最高的高度定义为照片的中心点，而照片的最左点从最低高度的牛开始，且该高度的牛必须出现两次才行，因为要对称。

代码示例

c++

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

int a[100005] = {0};

int main(){
	int i,j,k=0;
	int t,n;
	cin >> t;
	while(t--){
		memset(a,0,sizeof(a));
		
		cin >> n;
		for(i=1;i<=n;i++){
			cin >> j;
			a[j]++;
		}

		i=1,j=100000;
		while(a[j]==0) j--;
		k=1;
		while(i<j){
			if(a[i]>=2){
				k+=2;
			}
			i++;
		}
		
		cout<<k<<endl;
	} 
	return 0;
}

[USACO25OPEN] It's Mooin' Time III B

题目描述

Elsie 正在试图向 Bessie 描述她最喜欢的 USACO 竞赛，但 Bessie 很难理解为什么 Elsie 这么喜欢它。Elsie 说「现在是哞哞时间！谁想哞哞？请，我只想参加 USACO」。

Bessie 仍然不理解，于是她将 Elsie 的描述转文字得到了一个长为 $N$ （ $3 \leq N \leq 10^{5}$ ）的字符串，包含小写字母字符 $s_{1} s_{2} \dots s_{N}$ 。Elsie 认为一个包含三个字符的字符串 $t$ 是一个哞叫，如果 $t_{2} = t_{3}$ 且 $t_{2} \neq t_{1}$ 。

一个三元组 $(i, j, k)$ 是合法的，如果 $i < j < k$ 且字符串 $s_{i} s_{j} s_{k}$ 组成一个哞叫。对于该三元组，FJ 执行以下操作计算其值：

FJ 将字符串 $s$ 在索引 $j$ 处弯曲 90 度
该三元组的值是 $Δ i j k$ 的面积的两倍。

换句话说，该三元组的值等于 $(j - i) (k - j)$ 。

Bessie 向你进行 $Q$ （ $1 \leq Q \leq 3 \cdot 10^{4}$ ）个查询。在每个查询中，她给你两个整数 $l$ 和 $r$ （ $1 \leq l \leq r \leq N$ ， $r - l + 1 \geq 3$ ），并询问满足 $l \leq i$ 和 $k \leq r$ 的所有合法三元组 $(i, j, k)$ 的最大值。如果不存在合法的三元组，输出 $- 1$ 。

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

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$ 。以下一行包含 $s_{1} s_{2}, \dots s_{N}$ 。

以下 $Q$ 行每行包含两个整数 $l$ 和 $r$ ，表示每个查询。

输出格式

对于每一个查询输出一行，包含对于该查询的答案。

输入输出样例 #1

输入 #1

12 5
abcabbacabac
1 12
2 7
4 8
2 5
3 10

输出 #1

说明/提示

样例解释：对于第一个查询， $(i, j, k)$ 必须满足 $1 \leq i < j < k \leq 12$ 。可以证明，对于某个合法的 $(i, j, k)$ ， $Δ i j k$ 的最大面积在 $i = 1$ ， $j = 8$ 以及 $k = 12$ 时取到。注意 $s_{1} s_{8} s_{12}$ 是字符串 "acc"，根据前述定义是一个哞叫。 $Δ i j k$ 的直角边长为 $7$ 和 $4$ ，从而它的面积的两倍将等于 $28$ 。对于第三个查询， $(i, j, k)$ 必须满足 $4 \leq i < j < k \leq 8$ 。可以证明，对于某个合法的 $(i, j, k)$ ， $Δ i j k$ 的最大面积在 $i = 4$ ， $j = 5$ 以及 $k = 6$ 时取到。

对于第四个查询，不存在满足 $2 \leq i < j < k \leq 5$ 的 $(i, j, k)$ 使得 $s_{i} s_{j} s_{k}$ 是一个哞叫，所以该查询的输出为 $- 1$ 。

测试点 $2 \sim 3$ ： $N, Q \leq 50$ 。
测试点 $4 \sim 6$ ： $Q = 1$ ，唯一的询问满足 $l = 1$ 且 $r = N$ 。
测试点 $7 \sim 11$ ：没有额外限制。

解题思路

代码示例

c++

#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll; 
const int maxn = 1e5 + 5;
int l[maxn][128], r[maxn][128]; 
char s[maxn]; // 定义字符数组s，用于存储输入的字符串

int main() {
    int i,j,k;
    int n,q;
    char c,c2;
    cin >> n >> q; // 读取字符串长度n和查询次数q
    cin >> (s + 1); // 读取字符串s，从s[1]开始存储

    for(i = 1; i <= n; i++) {
        for(c = 'a'; c <= 'z'; c++) l[i][c] = l[i - 1][c]; // l[i][c]就是代表距离当前位置i左边最近字符c的位置是多少 
        l[i][s[i]] = i; // 更新当前字符s[i]字符出现的最新的位置
    }

    memset(r, 0x3f, sizeof(r)); // 将r数组初始化为一个较大的数，表示未找到字符
    for(i = n; i >= 1; --i) {
        if(i <= n - 1) {
            for(c = 'a'; c <= 'z'; c++) r[i][c] = r[i + 1][c]; // r[i][c]就是代表距离当前位置i右边最近字符c的位置是多少 
        }
        r[i][s[i]] = i; 
    }
    
    // 处理每个查询
    while(q--) {
        int ql, qr; // 定义查询的左边界ql和右边界qr
        cin >> ql >> qr; // 读取查询的左边界和右边界
        ll ans = -1; // 初始化答案为-1，表示未找到合法的三元组

        // 遍历每个可能的中间字符c
        for(c = 'a'; c <= 'z'; c++) {
            int k = l[qr][c]; // 找到字符c在右边界qr之后最后一次出现的位置
            int i = n; // 初始化i为n，表示边界
            // 找到字符c在左边界ql之前第一次出现的位置
            for(c2 = 'a'; c2 <= 'z'; c2++) {
                if(c2 == c) continue; // 如果c2等于c，跳过。因为i不能等于k 
                i = min(i, r[ql][c2]); // 找到一个最远左边界i 
            }
            if(i >= k) continue; // 如果i大于等于k，说明没有找到合适的三元组，跳过

            // 计算可能的三元组值（当直角三角形的两个直角边长度相等时，面积最大。） 
            int j1 = l[(i + k) / 2][c], j2 = r[(i + k) / 2][c];
            if(j1 > i && j1 < k) ans = max(ans, ll(j1 - i) * (k - j1)); 
            if(j2 > i && j2 < k) ans = max(ans, ll(j2 - i) * (k - j2)); 
        }

        cout << ans << '\n';
    }
    return 0;
}

USACO 2025 US Open Contest, Bronze ​

[USACO25OPEN] Hoof Paper Scissors Minus One B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

说明/提示 ​

解题思路 ​

代码示例 ​

[USACO25OPEN] More Cow Photos B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

说明/提示 ​

解题思路 ​

代码示例 ​

[USACO25OPEN] It's Mooin' Time III B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

说明/提示 ​

解题思路 ​

代码示例 ​

USACO 2025 US Open Contest, Bronze

[USACO25OPEN] Hoof Paper Scissors Minus One B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解题思路

代码示例

[USACO25OPEN] More Cow Photos B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解题思路

代码示例

[USACO25OPEN] It's Mooin' Time III B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

解题思路

代码示例