USACO 2025年2月铜牌

[USACO25FEB] Reflection B

题目描述

Farmer John 有一块正方形画布，由一个 $N$ 行 $N$ 列的方阵表示（ $2 \leq N \leq 2000$ ， $N$ 为偶数）。他按照以下步骤来绘制画布：

首先，他将画布分成四个等大的象限，由通过画布中心的水平和垂直直线分隔。其次，他在画布的右上象限中绘制了一幅美丽的画作。右上象限的每个方格或者被涂色（以 # 表示），或者未被涂色（以 . 表示）。最后，由于他对自己的画作感到非常自豪，他将其沿此前提到的水平和垂直直线翻转到画布的其他象限中。例如，假设 $N = 8$ ，且 FJ 在步骤 2 中于右上象限绘制了以下画作：

plain

.#..
.#..
.##.
....

在步骤 3 中沿水平和垂直直线翻转过后，画布将如下所示：

plain

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

然而，当 FJ 熟睡时，Bessie 闯入了他的牛棚，偷走了他珍贵的画布。她彻底破坏了画布——移除了某些涂色的单元格，同时添加了某些涂色的单元格！在 FJ 醒来之前，她将画布归还给了 FJ。JFK的

FJ 想要修改他的画布，使其再次满足翻转条件：即，它是将右上象限翻转到其他各象限的结果。由于他只有有限的资源，他希望以尽可能少的操作来实现这一点，其中单次操作包括为一个方格涂色或移除一个方格的涂色。

给定 Bessie 破坏后的画布，以及一系列 $U$ （ $0 \leq U \leq 10^{5}$ ）次对画布的更新，每次更新切换单个方格的状态，若它是 '#' 则切换为 '.'，反之亦然。在所有更新之前，以及在每次更新之后，输出 FJ 为满足翻转条件所需要执行的最小操作数量 $x$ 。

输入格式

输入的第一行包含整数 $N$ 和 $U$ 。

以下 $N$ 行，每行包含 $N$ 个字符，表示 Bessie 破坏后的画布。每个字符均为 # 或 .。

以下 $U$ 行，每行包含整数 $r$ 和 $c$ ，其中 $1 \leq r, c \leq N$ ，表示一次对画布从上到下第 $r$ 行，从左到右第 $c$ 列的方格的更新。

输出格式

输出 $U + 1$ 行，为在所有更新之前以及在每次更新之后的 $x$ 。

输入输出样例 #1

输入 #1

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

输出 #1

说明/提示

样例 1 解释：

以下画布满足翻转条件，并且可由原画布经过 4 次操作得到：

plain

....
####
####
....

使用少于 4 次操作使原画布满足翻转条件是不可能的。

在更新 $(1, 3)$ 之后，画布看起来是这样的：

plain

....
##.#
####
..##

现在需要 3 次操作使画布满足翻转条件。

在更新 $(2, 3)$ 之后，画布看起来是这样的：

plain

....
####
####
..##

现在需要 2 次操作使画布满足翻转条件。

测试点 $2 \sim 3$ ： $N \leq 4$ 。
测试点 $4 \sim 6$ ： $U \leq 10$ 。
测试点 $7 \sim 16$ ：没有额外限制。

代码案例

c++

#include "iostream"
#include "algorithm"
using namespace std;

int n, u, ans; // 定义变量 n（画布大小），u（更新次数），ans（最小操作次数）
char a[2005][2005]; // 定义二维数组 a 存储画布状态

int main () { 
	cin >> n >> u; // 输入画布的大小 n 和更新次数 u
	// 读取画布的初始状态
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			cin >> a[i][j]; // 输入每个方格的状态（'#' 或 '.'）

	// 计算初始的最小操作次数
	for (int i = 1; i <= n / 2; ++i)
		for (int j = 1; j <= n / 2; ++j) {
			// 计算当前象限及其翻转象限的涂色状态
			int cnt = (a[i][j] == '.') + (a[i][n + 1 - j] == '.') +
					  (a[n + 1 - i][j] == '.') + (a[n + 1 - i][n + 1 - j] == '.');
			// 更新最小操作次数
			ans += min(cnt, 4 - cnt);
		}
	cout << ans << '\n'; // 输出初始的最小操作次数

	// 处理每次更新
	for (int x, y; u--; ) {
		cin >> x >> y; // 输入更新的方格位置
		// 计算更新前的涂色状态
		int cnt1 = (a[x][y] == '.') + (a[x][n + 1 - y] == '.') +
				   (a[n + 1 - x][y] == '.') + (a[n + 1 - x][n + 1 - y] == '.');
		// 切换方格的涂色状态
		if (a[x][y] == '.')
			a[x][y] = '#'; // 如果是未涂色，则涂色
		else
			a[x][y] = '.'; // 如果是涂色，则未涂色

		// 计算更新后的涂色状态
		int cnt2 = (a[x][y] == '.') + (a[x][n + 1 - y] == '.') +
				   (a[n + 1 - x][y] == '.') + (a[n + 1 - x][n + 1 - y] == '.');
		// 更新最小操作次数
		ans = ans + min(cnt2, 4 - cnt2) - min(cnt1, 4 - cnt1);
		cout << ans << '\n'; // 输出更新后的最小操作次数
	}
	return 0; // 程序结束
}

[USACO25FEB] Making Mexes B

题目描述

给定一个包含 $N$ 个非负整数的数组 $a$ ， $a_{1}, a_{2}, \dots, a_{N}$ （ $1 \leq N \leq 2 \cdot 10^{5}$ ， $0 \leq a_{i} \leq N$ ）。在一次操作中，你可以将 $a$ 的任一元素修改为任意非负整数。

一个数组的 mex 是它不包含的最小非负整数。对于范围 $0$ 到 $N$ 内的每一个 $i$ ，计算使 $a$ 的 mex 等于 $i$ 所需要的最小操作次数。

输入格式

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

以下一行包含 $a_{1}, a_{2}, \dots, a_{N}$ 。

输出格式

对于范围 $0$ 到 $N$ 内的每一个 $i$ 输出一行，包含对于 $i$ 的最小操作次数。注意， $a$ 的 mex 对于范围 $0$ 到 $N$ 内的任意 $i$ 值都是可以通过修改取到的。

输入输出样例 #1

输入 #1

4
2 2 2 0

输出 #1

说明/提示

样例 1 解释：

为使 $a$ 的 mex 等于 $0$ ，我们可以将 $a_{4}$ 修改为 $3$ （或任何正整数）。在得到的数组 $[2, 2, 2, 3]$ 中， $0$ 是数组不包含的最小非负整数，因此 $0$ 是数组的 mex。
为使 $a$ 的 mex 等于 $1$ ，我们不需要进行任何修改，因为 $1$ 已经是 $a = [2, 2, 2, 0]$ 中不包含的最小非负整数。
为使 $a$ 的 mex 等于 $2$ ，我们需要修改 $a$ 的前三个元素。例如，我们可以将 $a$ 修改为 $[3, 1, 1, 0]$ 。
测试点 $2 \sim 6$ ： $N \leq 10^{3}$ 。
测试点 $7 \sim 11$ ：没有额外限制。

代码案例

c++

#include"iostream"
#include"algorithm"
using namespace std;

/**
 * @const {number} N - 定义数组最大长度，2e5 + 10 保证足够大的空间
 */
const int N = 2e5 + 10;

/**
 * @array a - 记录每个数字出现的次数
 * a[i] 表示数字i在输入序列中出现的次数
 */
int a[N];

int main()
{
	int i,j,k,n;
	cin >> n;  // 输入序列长度n
	
	// 统计每个数字出现的次数
	for(i = 1;i <= n; ++ i){
		cin >> j;     // 输入一个数字
		a[j]++;       // 将这个数字的出现次数加1
	}
	
	/**
	 * cnt 用于记录当前mex值
	 * 如果某个数字i不存在于序列中(a[i]=0)，cnt就会增加
	 * cnt实际上就是记录了有多少个比当前数字小的数不存在于序列中
	 */
	long long cnt = 0;
	
	// 遍历0到n，计算将序列的mex变为i所需的最小操作次数
	for(i = 0;i <= n; ++ i)
	{
		// 如果cnt > a[i]，说明需要cnt次操作
		// 否则需要a[i]次操作
		if(cnt > a[i])
			cout << cnt << endl;  // 输出需要的最小操作次数
		else 
			cout << a[i] << endl;
			
		// 如果数字i在序列中不存在，cnt增加
		if(a[i] == 0)
			cnt ++;
	}
	return 0;
}

[USACO25FEB] Printing Sequences B

题目描述

Bessie 正在学习使用一种简单的编程语言进行编程。她首先定义一个合法的程序，然后执行该程序以产生一些输出序列。

定义：

一个程序是一个非空的语句序列。

一个语句的形式或者是 "PRINT $c$ "，其中 $c$ 是一个整数，或者是 "REP $o$ "，随后是一个程序，随后是 "END"，其中 $o$ 是一个不小于 1 的整数。

执行：

执行一个程序将依次执行其语句。

执行语句 "PRINT $c$ " 将使 $c$ 追加到输出序列中。

执行以 "REP $o$ " 开始的语句将依次执行内部程序共 $o$ 次。

Bessie 知道如何编写的一个程序示例如下。

plain

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

该程序输出序列 $[1, 2, 2, 1, 2, 2, 1, 2, 2]$ 。

Bessie 想要输出一个包含 $N$ （ $1 \leq N \leq 100$ ）个正整数的序列。Elsie 挑战她使用不超过 $K$ （ $1 \leq K \leq 3$ ）个 "PRINT" 语句。注意，Bessie 可以使用任意数量的 "REP" 语句。同时注意，序列中的每个正整数都不超过 $K$ 。

对于 $T$ （ $1 \leq T \leq 100$ ）个独立的测试用例中的每一个，求 Bessie 是否可以编写一个程序，使用至多 $K$ 个 "PRINT" 语句输出给定的序列。

输入格式

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

每一个测试用例的第一行包含空格分隔的两个整数 $N$ 和 $K$ 。

每一个测试用例的第二行包含一个由 $N$ 个空格分隔的正整数组成的序列，每个数都不超过 $K$ ，为 Bessie 想要产生的序列。

输出格式

对于每一个测试用例输出一行，包含 "YES" 或 "NO"（大小写敏感）。

输入输出样例 #1

输入 #1

输出 #1

YES
YES

输入输出样例 #2

输入 #2

11
4 2
1 2 2 2
4 2
1 1 2 1
4 2
1 1 2 2
6 2
1 1 2 2 1 1
10 2
1 1 1 2 2 1 1 1 2 2
8 3
3 3 1 2 2 1 2 2
9 3
1 1 2 2 2 3 3 3 3
16 3
2 2 3 2 2 3 1 1 2 2 3 2 2 3 1 1
24 3
1 1 2 2 3 3 3 2 2 3 3 3 1 1 2 2 3 3 3 2 2 3 3 3
9 3
1 2 2 1 3 3 1 2 2
6 3
1 2 1 2 2 3

输出 #2

YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO

说明/提示

样例 1 解释：

对于第二个测试用例，以下代码使用了 $1$ 个 "PRINT" 语句输出了序列 $[1, 1, 1, 1]$ 。

plain

REP 4
    PRINT 1
END

样例 2 解释：

对于第一个测试用例，以下代码使用了 $2$ 个 "PRINT" 语句输出了序列 $[1, 2, 2, 2]$ 。

plain

PRINT 1
REP 3
    PRINT 2
END

对于第二个测试用例，答案是 "NO"，因为使用不超过 $2$ 个 "PRINT" 语句输出序列 $[1, 1, 2, 1]$ 是不可能的。

对于第六个测试用例，以下代码使用了 $3$ 个 "PRINT" 语句输出了序列 $[3, 3, 1, 2, 2, 1, 2, 2]$ 。

plain

REP 2
    PRINT 3
END
REP 2
    PRINT 1
    REP 2
        PRINT 2
    END
END

测试点 $3$ ： $K = 1$ 。
测试点 $4 \sim 7$ ： $K \leq 2$ 。
测试点 $8 \sim 13$ ：没有额外限制。

代码案例

c++

#include "iostream"
#include "algorithm"
using namespace std;

/**
 * @const {number} MAXN - 定义最大数组长度
 */
const int MAXN = 105;

/**
 * @var T - 测试用例数量
 * @var n - 每个测试用例的序列长度
 * @var k - 允许使用的PRINT语句数量
 * @var a - 存储输入的序列
 */
int T, n, k;
int a[MAXN];

/**
 * @struct Pair - 用于替代vector<pair>的结构体
 * @member num - 数字值
 * @member cnt - 数字连续出现的次数
 */
struct Pair {
    int num, cnt;
} b[MAXN];

/**
 * @function sol1 - 检查区间[l,r]内的数是否都相同
 * @param l - 左边界
 * @param r - 右边界
 * @return bool - 如果区间内所有数相同返回true，否则返回false
 */
bool sol1(int l, int r) {
    for (int i = l + 1; i <= r; ++i)
        if (a[i] != a[i-1])
            return 0;
    return 1;
}

/**
 * @function sol2 - 检查区间[l,r]是否满足k=2的条件
 * @param l - 左边界
 * @param r - 右边界
 * @return bool - 如果满足条件返回true，否则返回false
 */
bool sol2(int l, int r) {
    // bSize是用来记录连续相同数字的段的数量
    int bSize = 0;
    for (int i = l; i <= r; ++i) {
        if (bSize && a[i] == a[i-1])
            b[bSize-1].cnt++;
        else {
            bSize++;
            b[bSize-1].num = a[i];
            b[bSize-1].cnt = 1;
        }
    }
    
    // 检查段数是否满足条件（<=2或为偶数）
    if (bSize <= 2 || bSize % 2 == 0) {
        // 检查是否每隔两段就重复
        for (int i = 0; i + 2 < bSize; ++i)
            if (b[i].num != b[i+2].num || b[i].cnt != b[i+2].cnt)
                return 0;
        return 1;
    }
    return 0;
}

/**
 * @function sol3 - 检查区间[l,r]是否满足k=3的条件
 * @param l - 左边界
 * @param r - 右边界
 * @return bool - 如果满足条件返回true，否则返回false
 */
bool sol3(int l, int r) {
    // 枚举可能的周期长度
    for (int len = 1; l + len - 1 <= r; ++len) {
        if ((r - l + 1) % len == 0) {
            bool f = 1;
            // 检查是否存在周期性
            for (int i = l; i + len <= r; ++i)
                f &= (a[i] == a[i+len]);
            if (!f)
                continue;
            // 检查每个周期内是否可以用sol1和sol2的组合表示
            for (int i = l; i <= l + len; ++i)
                if ((sol1(l, i) && sol2(i+1, l+len-1)) || 
                    (sol2(l, i) && sol1(i+1, l+len-1)))
                    return 1;
        }
    }
    return 0;
}

int main() {
    cin >> T;
    while (T--) {
        // 读入每个测试用例的数据
        cin >> n >> k;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
            
        // 根据k的值调用对应的判断函数
        if (k == 1) puts(sol1(1, n) ? "YES" : "NO");
        if (k == 2) puts(sol2(1, n) ? "YES" : "NO");
        if (k == 3) puts(sol3(1, n) ? "YES" : "NO");
    }
    return 0;
}

USACO 2025年2月铜牌 ​

[USACO25FEB] Reflection B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

说明/提示 ​

代码案例 ​

[USACO25FEB] Making Mexes B ​

题目描述 ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

说明/提示 ​

代码案例 ​

[USACO25FEB] Printing Sequences B ​

题目描述 ​

定义： ​

执行： ​

输入格式 ​

输出格式 ​

输入输出样例 #1 ​

输入 #1 ​

输出 #1 ​

输入输出样例 #2 ​

输入 #2 ​

输出 #2 ​

说明/提示 ​

代码案例 ​

USACO 2025年2月铜牌

[USACO25FEB] Reflection B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

代码案例

[USACO25FEB] Making Mexes B

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

代码案例

[USACO25FEB] Printing Sequences B

题目描述

定义：

执行：

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

代码案例