CodeChef RRCOPY 题解:用"复制粘贴"操作逆向推导最小原数组(Cosmos 仓库 C 实现解析)

原创2026-09-22 10:47:381,333 阅读
文章标签:教程示例工程

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 算法步骤

对于每一个测试用例:

  1. 读入数组长度 n;
  2. 依次读入 n 个整数;
  3. 用一个布尔标记数组(哈希表)记录某个值是否已经出现过;
  4. 若当前值第一次出现,则计数器加 1,并标记为已出现;
  5. 输出计数器值,即不同元素个数。

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; 正常退出

实现要点:

  1. 哈希数组代替 std::set/unordered_set:值域已知且不大时,用数组做标记比哈希表/平衡树更快更简单,避免了动态内存分配的开销;
  2. {0} 全零初始化:保证每个测试用例开始时标记数组是干净的(注意该数组声明在 while (t--) 循环体内部,因此每组用例都会重新初始化);
  3. 边读边处理:无需把整个数组存下来,流式处理即可完成计数,节省内存;
  4. 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 仓库中的位置与扩展阅读

从源码结构看,code/online_challenges/src/codechef/ 目录按题目 ID 组织,每个子目录存放题目 README 与对应语言实现,方便读者按题号检索和学习。

延伸思考

RRCOPY 的结论"最短初始数组 = 不同元素个数"可以推广到一类"只能复制已有内容"的构造问题:

  • 若题目要求每个元素至少出现一次的初始数组,答案就是不同元素个数;
  • 若题目限制复制区间长度/粘贴位置,则需要额外考虑区间覆盖问题,不再是简单的去重计数;
  • 若题目允许删除、交换等其他操作,则"最小初始数组"的定义需要重新建模。

掌握"从操作性质反推必要/充分条件"的思维方式,是解决这类 CodeChef 思维题的关键。

七、总结

RRCOPY 是一道"披着 Copy-Paste 外衣"的简单计数题:由于复制粘贴不会产生新值,逆向推导可知最短初始数组恰好包含 A 中所有不同值各一次,因此答案为不同元素个数。仓库提供的 C 实现 用 1000000 大小的哈希数组实现了 O(n) 的流式计数,代码简洁、可直接提交至 CodeChef 评测。

登录后查看全文
cosmos