编程竞赛题解：ZOJ 1610 - 计数不同颜色的可见段

"题目描述：Zoj 1610 Count the Colors 是一道ACM（算法竞赛）中的问题，主要涉及线性数据结构和区间覆盖问题。该题目要求解决一个关于在一条直线上绘制不同颜色的涂色段落的问题。输入是一系列非负整数，每行包含三个元素，分别代表每个涂色段落的起始位置（x1）、结束位置（x2）和颜色编号（c）。每个数据集的第一行是一个整数 n，表示有 n 个涂色段落，范围是 1 到 8000。你需要计算最后能从上方看到的不同颜色的段落数量，并按照颜色的索引顺序输出，对于看不到的颜色不作输出。每处理完一个数据集后，应打印一个空行。 例如： 输入： 5 044 031 342 022 023 4 011 341 132 131 6 010 121 231 120 230 121 输出： 11 21 31 11 11 解答思路： 1. 首先，这个问题可以转换为区间覆盖问题，将颜色视为不同的区间，每个颜色对应一个区间 [x1, x2]。题目要求的是最后能从上方看到的每个颜色覆盖区域的数量。 2. 为了高效地处理这个问题，可以使用一种叫做前缀和（Prefix Sum）的数据结构。前缀和数组可以帮助我们快速查询某个位置之前有多少个相同颜色的区间。对于每个颜色 c，我们需要维护两个数组，一个记录到当前位置为止，颜色 c 的区间覆盖数量（count_c），另一个记录颜色 c 的区间起点（start_c）。 3. 遍历输入数据，每次遇到新的颜色 c，将其区间起点更新为当前位置，然后更新其覆盖数量 count_c。如果新的颜色与之前的颜色相同，只增加 count_c，如果不同，则更新 start_c 并重新设置 count_c 为 1。同时，更新前缀和数组，记录到当前位置为止，颜色 c 的总覆盖数量。 4. 最后，遍历颜色计数数组，输出所有能看到的颜色及其对应的覆盖数量。如果颜色没有被看到（即 count_c 为 0），则跳过。 参考代码实现如下（使用 C++）： ```cpp #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 8000 + 10; int n, x1[MAXN], x2[MAXN], c[MAXN], count[MAXN], start[MAXN], prefix[MAXN]; void process() { memset(count, 0, sizeof(count)); memset(start, -1, sizeof(start)); for (int i = 0; i < n; ++i) { scanf("%d%d%d", &x1[i], &x2[i], &c[i]); if (start[c[i]] == -1) { start[c[i]] = x1[i]; } count[c[i]]++; // 更新前缀和 prefix[i + 1] = prefix[i] + count[c[i]]; } // 计算每个颜色在可视范围内的覆盖数量 for (int i = 0; i < n; ++i) { if (start[c[i]] != -1 && x1[i] >= start[c[i]]) { int visible_count = prefix[x2[i] + 1] - prefix[start[c[i]]]; printf("%d %d", c[i], visible_count); // 如果有下一个颜色，打印空格 if (i < n - 1 && start[c[i] + 1] != -1) { printf(" "); } } // 每个数据集结束后换行 if (i == n - 1) { printf("\n"); } } } int main() { while (scanf("%d", &n) != EOF) { process(); } return 0; } ``` 这个代码首先读取数据集，然后计算每个颜色的区间覆盖，并通过前缀和数组快速查询可视范围内的覆盖数量。最后按照题目要求输出结果。"