CodeChef RRCOPY 题解:用"复制粘贴"操作逆向推导最小原数组(Cosmos 仓库 C 实现解析)
CodeChef RRCOPY 题解:用"复制粘贴"操作逆向推导最小原数组(Cosmos 仓库 C 实现解析)
导读
RRCOPY 是 CodeChef 上的一道经典思维型数组构造题:给定一个可通过任意多次"Copy-Paste"(复制粘贴连续子序列)操作得到的数组 A,要求反推出能够生成它的最短初始数组的长度。本文以 问题原文 为骨架,结合仓库中的 RRCOPY.c 完整实现,讲解问题转化、算法正确性证明、C 语言实现要点、复杂度分析与边界情况,并给出可直接提交的完整代码。读完本文,你将掌握"用去重计数解决区间复制类逆向题"的通用思路,并能在 CodeChef 上独立复现该题解。
一、问题重述与形式化建模
1.1 题目原文
根据仓库内 问题文档 的描述:
你有一个整数数组,并拥有一种称为"Copy-Paste"的优美操作:可以复制数组中任意一段连续子序列(contiguous subsequence),并粘贴到数组的任意位置。例如,对数组
[1, 2, 3, 4, 5],复制第 2 到第 4 个元素(即[2, 3, 4])并粘贴到第 3 个元素之后,得到[1, 2, 3, 2, 3, 4, 4, 5]。
你记得对初始数组进行了有限次(可能为零次)这样的操作后,得到了数组 A。由于不记得初始数组本身,你需要求出能够通过 Copy-Paste 操作生成 A 的最短初始数组的长度(大小)。
1.2 关键观察:操作的实质是"复制已有内容"
"Copy-Paste"操作有一个极其重要的性质:粘贴进去的元素,一定是数组中已经存在过的元素。因为粘贴的内容来源于"复制"——复制的是当前数组中某个连续子序列,而不是凭空生成新元素。
因此可以推断:
- 整个操作过程中,数组的元素种类集合(值域)永远不会扩大,只会保持不变;
- 每一次操作只是把已出现的元素以新的排列/重复形式"再放一遍";
- 反过来,任何一个由 Copy-Paste 生成的数组 A,其中出现的所有不同值,必然都来自最初的数组。
1.3 逆向推导:最短初始数组 = 去重后的不同元素个数
现在做逆向思考。设初始数组为 B,最终数组为 A。
- 下界(必要性):初始数组 B 中必须包含 A 中出现的每一个不同值。否则,B 无法通过复制粘贴生成出 A 中那个"从未出现过"的值。所以
|B| ≥ 不同元素的个数。 - 上界(充分性):令初始数组 B 恰好为 A 中所有不同值各出现一次的排列(即 B 是 A 的去重集合)。接下来,我们从左到右逐步构造 A:对于 A 中需要重复出现的每个值,总能在 B(以及后续不断增长的数组)中找到一个连续子序列来复制粘贴。事实上,更简单的构造是:先把 B 中的每个元素按 A 中出现的顺序复制粘贴,逐步把 A 完整拼出来。由于 B 已经包含全部所需的值,任何出现在 A 中的值都可以从已有的数组中复制得到,因此构造必然可行。
所以最短初始数组长度 = A 中不同元素的个数(即 distinct count)。
这一结论正是整个题解的核心:RRCOPY 本质上是一道"数不同元素"的题,与"复制粘贴"操作本身无关。
二、示例验证
用题目文档中的例子验证:
- 初始数组
[1, 2, 3, 4, 5],其不同元素个数为 5; - 执行一次复制粘贴后得到
[1, 2, 3, 2, 3, 4, 4, 5],其不同元素个数依然为 5。
无论做多少次操作,不同元素个数不变,始终等于初始数组的长度 5。反向来看,任意数组 A,其不同元素个数即为最小可能初始长度。这个例子直观印证了上述结论。
三、算法设计
3.1 算法步骤
对于每一个测试用例:
- 读入数组长度 n;
- 依次读入 n 个整数;
- 用一个布尔标记数组(哈希表)记录某个值是否已经出现过;
- 若当前值第一次出现,则计数器加 1,并标记为已出现;
- 输出计数器值,即不同元素个数。
3.2 复杂度分析
- 时间复杂度:O(n),每个元素只处理一次,哈希表查询/写入均为 O(1);
- 空间复杂度:O(V),V 为值域大小。在下面给出的实现中,值域为
0 ~ 999999,因此使用大小为 1000000 的数组。
四、仓库源码逐行解析
仓库中给出的 RRCOPY.c 是一个简洁的完整实现,其逻辑完全对应上述算法:
#include <stdio.h>
#include <string.h>
int main(void)
{
int t;
scanf("%d", & t);
while (t--)
{
int n, h[1000000] = {0};
scanf("%d", & n);
int count = 0;
while (n--)
{
int temp;
scanf("%d", & temp);
if (h[temp] == 0)
{
count++;
h[temp]++;
}
}
printf("%d\n", count);
}
return 0;
}
逐行解读:
| 代码 | 作用 |
|---|---|
int t; scanf("%d", &t); |
读入测试用例组数 t(CodeChef 多组测试用例的标准输入格式) |
while (t--) |
逐组处理,每组开始时重置变量 |
int n, h[1000000] = {0}; |
读入数组长度 n;h 为哈希数组,{0} 初始化全部元素为 0,表示"未出现过";1000000 覆盖值域 0~999999(若题目值域更大需相应扩大) |
int count = 0; |
不同元素计数器 |
while (n--) |
逐个读入 n 个元素 |
scanf("%d", &temp); |
读入当前元素 |
if (h[temp] == 0) { count++; h[temp]++; } |
若该值第一次出现,计数加 1 并标记;重复出现则跳过 |
printf("%d\n", count); |
输出该用例的答案:不同元素个数 |
return 0; |
正常退出 |
实现要点:
- 哈希数组代替
std::set/unordered_set:值域已知且不大时,用数组做标记比哈希表/平衡树更快更简单,避免了动态内存分配的开销; {0}全零初始化:保证每个测试用例开始时标记数组是干净的(注意该数组声明在while (t--)循环体内部,因此每组用例都会重新初始化);- 边读边处理:无需把整个数组存下来,流式处理即可完成计数,节省内存;
h[temp]++而非h[temp] = 1:写成自增同样达到标记目的,语义为"出现次数",若题目后续需要频次信息可复用。
说明:该实现假设数组元素为非负且值域不超过 999999。若题目输入包含负数或更大值域,应将哈希数组换用
unordered_map/字典,或将元素统一加偏移量处理。
五、测试用例验证
用几组手写用例验证实现的正确性(假设编译为可执行文件 rrcopy):
用例 1:无重复(最少操作次数为 0 的场景)
输入:
1
5
1 2 3 4 5
输出:
5
5 个元素各不相同,无法通过任何操作减少初始长度,答案为 5,与题目文档中的例子一致。
用例 2:全部相同
输入:
1
7
3 3 3 3 3 3 3
输出:
1
所有元素都是 3,初始数组只需 [3] 一个元素,复制粘贴 6 次即可生成目标数组。
用例 3:混合重复
输入:
1
8
1 2 3 2 3 4 4 5
输出:
5
与文档示例 [1, 2, 3, 2, 3, 4, 4, 5] 完全一致,答案为 5(不同元素为 1、2、3、4、5)。
用例 4:多组测试
输入:
2
3
7 7 7
4
10 20 10 30
输出:
1
3
六、题目在 Cosmos 仓库中的位置与扩展阅读
- 题目与题解文档:RRCOPY/README.md
- C 语言完整实现:RRCOPY.c
- CodeChef 题目索引:codechef/README.md
- 仓库在线挑战题合集总览:online_challenges/src/README.md
从源码结构看,code/online_challenges/src/codechef/ 目录按题目 ID 组织,每个子目录存放题目 README 与对应语言实现,方便读者按题号检索和学习。
延伸思考
RRCOPY 的结论"最短初始数组 = 不同元素个数"可以推广到一类"只能复制已有内容"的构造问题:
- 若题目要求每个元素至少出现一次的初始数组,答案就是不同元素个数;
- 若题目限制复制区间长度/粘贴位置,则需要额外考虑区间覆盖问题,不再是简单的去重计数;
- 若题目允许删除、交换等其他操作,则"最小初始数组"的定义需要重新建模。
掌握"从操作性质反推必要/充分条件"的思维方式,是解决这类 CodeChef 思维题的关键。
七、总结
RRCOPY 是一道"披着 Copy-Paste 外衣"的简单计数题:由于复制粘贴不会产生新值,逆向推导可知最短初始数组恰好包含 A 中所有不同值各一次,因此答案为不同元素个数。仓库提供的 C 实现 用 1000000 大小的哈希数组实现了 O(n) 的流式计数,代码简洁、可直接提交至 CodeChef 评测。