1.1 相反数 题目分类:编程基础、排序。 1.1.1 题目描述 有 N 个非零且各不相同的整数。请你编一个程序求出它们中有多少对相反数(a 和 .a 为一对相反数)。 输入格式 第一行包含一个正整数 N (1 . N . 500)。 第二行为 N 个用单个空格隔开的非零整数,每个数的绝对值不超过 1000,保证这些 整数各不相同。 输出格式 只输出一个整数,即这 N 个数中包含多少对相反数。 样例输入 1 5 2 1 2 3 -1 -2 样例输出 1 2 1.1.2 题目分析 本题中由于 n . 500,朴素的方法是直接枚举,使用双重循环枚举所有的数对,并将 绝对值相等的数对计入答案。本解法的时间复杂度为 O(n2),空间复杂度为 O(n)。 注意到题目中给定的整数各不相同,可以将其排成有序的序列 A。分别从两端向中间 扫描,起始时可以令 i = 1,j = n。如果 |Ai| = |Aj |,则计入答案;如果 |Ai| > |Aj |,则 CCF CSP 认证考试历年真题解 令 i ← i + 1;如果 |Ai| < |Aj |,则令 j ← j . 1,直到 i = j。本解法的时间复杂度为 O(n log n),空间复杂度为 O(n)。 进一步考虑,与整数 a 构成相反数的元素只有一个,因而并不需要排序,只需要判断 这个元素是否在序列中出现过就可以。可以使用 map 或 set 来记录,但是注意到本题每个 数的绝对值不超过 1000,所以只需要一个大小为 1001 的数组记录元素的出现情况。本解 法的时间复杂度为 O(n),空间复杂度为 O(m),本题中 m . 1001。 1.1.3 参考实现 C 语言实现 1 #include 2 #define N 510 3 #define M 1010 4 using namespace std; 5 int a[N], cnt[M]; 6 int main() { 7 int n; 8 scanf("%d", &n); 9 for (int i = 1; i <= n; i++) scanf("%d", &a[i]); 10 int ans = 0; 11 // 判 断 当 前 数 的 相 反 数 是 否 在 序 列 中 出 现 过 , 使 用 标 记 数 组 记 录 12 for (int i = 1; i <= n; i++) 13 if (a[i] >= 0) cnt[a[i]]++; 14 for (int i = 1; i <= n; i++) 15 if (a[i] < 0) ans += cnt[-a[i]]; 16 printf("%d\n", ans); 17 return 0; 18 } 1.2 窗口 题目分类:编程进阶。 1.2.1 题目描述 在某图形操作系统中,有 N 个窗口,每个窗口都是一个两边与坐标轴分别平行的矩形 区域。窗口的边界上的点也属于该窗口。窗口之间有层次的区别,在多于一个窗口重叠的 区域里,只会显示位于顶层窗口里的内容。 当你点击屏幕上的一个点时,你就选择了处于被点击位置的最顶层窗口,并且这个窗 口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属 于任何窗口,则系统会忽略你这次点击。 2 第 1 章 第 1 次认证(2014 年 3 月)题解 现在我们希望你写一个程序模拟点击窗口的过程。 输入格式 输入的第一行有两个正整数,即 N 和 M(1 . N . 10, 1 . M . 10)。 接下来 N 行按照从最下层到最顶层的顺序给出 N 个窗口的位置。每行包含 4 个非 负整数 x1, y1, x2, y2,表示该窗口的一对顶点坐标分别为 (x1, y1) 和 (x2, y2)。保证 x1 < x2, y1 < y2。 接下来 M 行每行包含两个非负整数 x, y,表示一次鼠标点击的坐标。 题目中涉及的所有点和矩形的顶点的 x, y 坐标分别不超过 2559 和 1439。 输出格式 输出包括 M 行, 每一行表示一次鼠标点击的结果。如果该次鼠标点击选择了一个窗 口,则输出这个窗口的编号(窗口按照输入中的顺序从 1 编号到 N);如果没有,则输出 “IGNORED”(不含双引号)。 样例输入 1 3 4 2 0 0 4 4 3 1 1 5 5 4 2 2 6 6 5 1 1 6 0 0 7 4 4 8 0 5 样例输出 1 2 2 1 3 1 4 IGNORED 样例说明 第一次点击的位置同时属于第一个和第二个窗口,但是由于第二个窗口在上面,因此 它被选择并且被置于顶层。 第二次点击的位置只属于第一个窗口,因此该次点击选择了此窗口并将其置于顶层。 现在的 3 个窗口的层次关系与初始状态恰好相反。 第三次点击的位置同时属于 3 个窗口的范围,但是由于现在第一个窗口处于顶层,因 此它被选择。 最后点击的 (0, 5) 不属于任何窗口。 3 CCF CSP 认证考试历年真题解 1.2.2 题目分析 本题给定了 N 个矩形窗口以及它们的层次,进行 M 次鼠标点击操作,求每次鼠标点 击在哪个窗口上。被点击的窗口会放到最上面。 本题是一道模拟题,模拟鼠标的点击过程。使用一个数组将窗口保存下来。对于每次 点击,从最顶层的窗口向最底层的窗口扫描,判断点击的坐标是否在窗口内,如果在窗口 内,则将此窗口置顶。将当前窗口置顶的操作可以通过调整数组的顺序实现。本解法的时 间复杂度为 O(NM),空间复杂度为 O(N +M)。 也可以直接将点击的窗口复制一份,作为新窗口添加到数组中,作为最顶层的窗口,这 样编码实现变得更简单了。本解法的时间复杂度为 O((N + M)M),空间复杂度为 O(N +M)。 进一步思考,可以记录每一个窗口最后被点击的时间。对于每一次点击,找到所有包 含该点击位置坐标的窗口,最后被点击的窗口即为所求。最后更新此窗口的最后被点击时 间为本次点击时间。本解法的时间复杂度为 O(NM),空间复杂度为 O(N +M)。 1.2.3 参考实现 C++ 实现 1 #include 2 #define N 20 3 using namespace std; 4 struct Window { 5 int x1 , y1 , x2 , y2; 6 } w[N]; 7 int rank[N]; // 窗 口 的 等 级 。 等 级 值 越 大 , 窗 口 越 靠 上 8 bool check(int x, int l, int r) // 检 查 x 值 是 否 在 [l,r] 中 9 { 10 return x <= r && x >= l; 11 } 12 void ask(int n, int tim , int x, int y) { 13 // 对 于 每 一 次 点 击 , 扫 描 所 有 窗 口 , 记 录 时 间 值 最 大 ( 最 顶 层 ) 的 窗 口 下 标 14 int t = 0; 15 for (int i = 1; i <= n; i++) 16 if (check(x, w[i].x1 , w[i].x2) && 17 check(y, w[i].y1 , w[i].y2) && rank[i] > rank[t]) 18 t = i; 19 if (!t) 20 puts("IGNORED"); 21 else { 22 // 将 每 次 点 击 的 窗 口 时 间 值 设 置 为 最 大 4 第 1 章 第 1 次认证(2014 年 3 月)题解 23 rank[t] = tim; 24 printf("%d\n", t); 25 } 26 } 27 int main() { 28 int n, m, x, y; 29 scanf("%d%d", &n, &m); 30 // 读 入 窗 口 坐 标 , 并 给 每 个 窗 口 设 置 初 始 时 间 , 越 靠 上 的 窗 口 时 间 值 越 大 31 for (int i = 1; i <= n; i++) { 32 scanf("%d%d%d%d", &w[i].x1 , &w[i].y1 , &w[i].x2 , &w[i].y2); 33 rank[i] = i; 34 } 35 // 模 拟 m 次 点 击 操 作 36 for (int i = 1; i <= m; i++) { 37 scanf("%d%d", &x, &y); 38 ask(n, n + i, x, y); 39 } 40 return 0; 41 } 1.3 命令行选项 题目分类:模拟、字符串。 1.3.1 题目描述 请你写一个命令行分析程序,用于分析给定的命令行里包含哪些选项。每个命令行由 若干个字符串组成。它们之间恰好由一个空格分隔。这些字符串中的第一个为该命令行工 具的名字,由小写字母组成,你的程序不用对它进行处理。在工具名字之后可能会包含若 干选项,然后可能会包含一些不是选项的参数。选项有两类:带参数的选项和不带参数的 选项。一个合法的无参数选项的形式是一个减号后面跟单个小写字母,如“-a”或“-b”。 而带参数选项则由两个由空格分隔的字符串构成。前者的格式要求与无参数选项相同;后 者则是该选项的参数,是由小写字母、数字和减号组成的非空字符串。 该命令行工具的作者提供给你一个格式字符串以指定他的命令行工具需要接收哪些选 项。这个字符串由若干小写字母和冒号组成,其中的每个小写字母表示一个该程序接收的 选项。如果该小写字母后面紧跟了一个冒号,就表示一个带参数的选项;否则为不带参数 的选项。例如, “ab:m:”表示该程序接收 3 种选项,即“-a”(不带参数)、“-b”(带参数) 以及“-m”(带参数)。 命令行工具的作者准备了若干条命令行用以测试你的程序。对于每个命令行,你的工 具应当一直向后分析。当你的工具遇到某个字符串既不是合法的选项又不是某个合法选项 5 CCF CSP 认证考试历年真题解 的参数时,分析就停止。命令行剩余的未分析部分不构成该命令的选项,因此你的程序应 当忽略它们。 输入格式 输入的第一行是一个格式字符串,它至少包含一个字符,且长度不超过 52。格式字符 串只包含小写字母和冒号,保证每个小写字母至多出现一次,不会有两个相邻的冒号,也 不会以冒号开头。 输入的第二行是一个正整数 N(1 . N . 20),表示你需要处理的命令行的个数。 接下来有 N 行,每行是一个待处理的命令行,它包括不超过 256 个字符。该命令行一 定是若干个由单个空格分隔的字符串,每个字符串里只包含小写字母、数字和减号。 输出格式 输出有 N 行。其中,第 i 行以“Case i:”开始,然后应当有恰好一个空格,然后应 当按照字母升序输出该命令行中用到的所有选项的名称。对于带参数的选项,在输出它的 名称之后还要输出它的参数。如果一个选项在命令行中出现了多次,则只输出一次。如果 一个带参数的选项在命令行中出现了多次,则只输出最后一次出现时所带的参数。 样例输入 1 albw:x 2 4 3 ls -a -l -a documents -b 4 ls 5 ls -w 10 -x -w 15 6 ls -a -b -c -d -e -l 样例输出 1 Case 1: -a -l 2 Case 2: 3 Case 3: -w 15 -x 4 Case 4: -a -b 1.3.2 题目分析 本题大意是:给出一种命令行选项的描述方法,现指定若干输入的命令,需要按照给 出的规则解析命令参数,去除无效部分,并按顺序输出有效部分。在实际的类 UNIX 操作 系统上,很多实用程序用 getopt() 解析命令行参数,就是使用了类似于本题的算法。本 题则是将上述应用场景提炼和简化,形成了一道具有实际意义的问题。 本题是一道典型的字符串处理的问题。根据题意,将命令行用空格分割后可以得到若 干字符串。依次考虑每一个字符串,可以根据其首字母是否是连字符(-)分为两类:选项 6 第 1 章 第 1 次认证(2014 年 3 月)题解 和参数。根据输入的格式字符串,可以判断选项是带参数的还是不带参数的。对于不带参 数的选项,如果在其后出现了参数,则判断为不合法;对于带参数的选项,其参数应该是 由小写字母、数字和连字符组成的非空字符串。假设输入的命令行数是 n,命令长度不超 过 m,则本解法的时间复杂度为 O(nm),空间复杂度为 O(m)。 实现上述算法时,需要注意的是: . 参数的判定不能遗漏,特别要注意带参数选项后面缺少参数的情况。 . 要注意没有命令行选项的情况。 . 如果一个选项在命令行中出现了多次,只输出一次。 对于具体的实现语言,以下提示可供参考: . 对于 C++,可以使用 std::string 存储字符串,使用 std::cin 读取命令行工具 名,使用 std::getchar() 逐字符读取命令参数,使用换行符 '\n' 作为每行结束 判定条件。 . 对于 Java,读入行可以使用 Scanner.nextLine() 方法,使用 String.split() 方 法将每行字符串分割。分割后依次处理得到的字符串。对于有参数的选项,一次要 处理两个字符串。最后用 HashMap 对各个选项进行排序。 . 对于 Python,使用 input() 函数读入一行字符,使用 String.split() 方法分割 字符串,然后按照上述方法进行解析即可。 1.3.3 参考实现 C++ 实现 1 #include 2 #include 3 #include 4 #define N 20 5 using namespace std; 6 int st [26]; // 选 项 是 否 带 参 数 7 string param [26]; // 合 法 的 字 符 参 数 8 bool vis [26]; // 标 记 数 组 9 int main() { 10 string S; 11 cin >> S; // 读 入 格 式 字 符 串 12 int len = S.size(); 13 for (int i = 0; i <= len - 1; i++) { 14 if (i + 1 < len && S[i + 1] == ':') 15 st[S[i++] - 'a'] = 2; // 带 参 数 选 项 标 记 为 2 16 else 17 st[S[i] - 'a'] = 1; // 不 带 参 数 选 项 标 记 为 1 18 } 7 CCF CSP 认证考试历年真题解 19 char ch; 20 int n, Case = 0; 21 cin >> n; 22 while (n--) { 23 cin >> S; 24 ch = getchar (); // 读 入 命 令 名 称 25 for (int i = 0; i <= 25; i++) { 26 param[i]. clear (); 27 vis[i] = 0; // 清 零 操 作 28 } 29 if (ch == '\n') goto Nex; // 如 果 遇 到 换 行 符 则 停 止 读 入 30 S.clear (); 31 while (ch = getchar (), 32 ch != '\n' && ch != EOF)// 读 入 一 行 字 符 , 遇 到 换 行 符 结 束 33 S.push_back(ch); 34 S.push_back(' '); // 末 尾 加 空 格 35 len = S.size(); 36 for (int i = 0; i <= len - 1; i++) { 37 int t = S[i + 1] - 'a'; 38 // 如 果 字 符 非 法 , 则 停 止 39 if (i + 2 >= len || S[i] != '-' || S[i + 2] != ' ' || 40 S[i + 1] > 'z' || S[i + 1] < 'a' || !st[t]) 41 goto Nex; 42 vis[t] = 1; // 标 记 字 符 存 在 43 if (st[t] == 1) // 不 带 参 数 字 符 44 i += 2; 45 else // 带 参 数 字 符 46 { 47 i += 3; 48 if (i < len) param[t]. clear (); 49 while (i < len && S[i] != ' ') { 50 if (S[i] != '-' && (S[i] > 'z' || S[i] < 'a') && 51 !isdigit(S[i])) // 如 果 字 符 参 数 不 合 法 52 { 53 param[t]. clear (); // 清 空 数 组 并 停 止 54 goto Nex; 55 } 56 param[t].push_back( 57 S[i++]); // 如 果 字 符 参 数 合 法 则 放 入 param 中 58 } 59 } 8 第 1 章 第 1 次认证(2014 年 3 月)题解 60 } 61 Nex:; 62 printf("Case %d: ", ++Case); 63 for (int i = 0; i <= 25; i++) 64 if (vis[i]) // 如 果 字 符 存 在 则 输 出 65 { 66 printf(" -%c ", i + 'a'); 67 if (st[i] == 2) cout << param[i] << ' '; 68 } 69 cout << endl; 70 } 71 return 0; 72 } Java 实现 1 import java.util.*; 2 3 public class Main { 4 public static void main(String [] args) { 5 Scanner cin = new Scanner(System.in); 6 String format = cin.nextLine (); // 读 入 格 式 字 符 串 7 int n = Integer.parseInt(cin.nextLine ()); 8 for (int i = 1; i <= n; i++) { 9 Map map = new HashMap (); 10 String [] s = 11 cin.nextLine ().split(" "); // 将 选 项 按 照 空 格 分 开 12 for (int j = 1; j < s.length; j++) { 13 if (s[j]. length () == 2 14 && s[j]. charAt (0) == '-') { // 如 果 选 项 合 法 15 int pos = format.indexOf(s[j]. charAt (1)); 16 //查找选项在格式字符串中的位置,判断是否带参数 17 if (pos == -1) { // 没 有 找 到 , 直 接 停 止 18 break; 19 } 20 21 if (map.containsKey(s[j]) == false) { 22 map.put(s[j], ""); 23 } 24 // 如 果 选 项 是 带 参 数 的 并 且 合 法 , 则 将 其 记 录 在 map 中 25 if (pos + 1 < format.length () 9 CCF CSP 认证考试历年真题解 26 && format.charAt(pos + 1) == ':' 27 && j + 1 < s.length) { 28 map.put(s[j], s[j + 1]); 29 j++; 30 } 31 } else { 32 break; 33 } 34 } 35 System.out.printf("Case " + i + ":"); 36 // 枚 举 所 有 选 项 , 通 过 map 寻 找 对 应 参 数 并 输 出 37 for (int j = 0; j < 26; j++) { 38 if (format.indexOf ((char) ('a' + j)) == -1) { 39 continue; 40 } 41 if (map.containsKey("-" + (char) ('a' + j)) 42 == false) { 43 continue; 44 } 45 System.out.printf(" -" + (char) ('a' + j)); 46 if (map.get("-" + (char) ('a' + j)) != "") { 47 System.out.printf( 48 " " + map.get("-" + (char) ('a' + j))); 49 } 50 } 51 System.out.println (); 52 } 53 } 54 } Python 实现 1 # 读 入 格 式 字 符 串 , 判 断 选 项 是 否 带 参 数 并 记 录 到 v 中 2 s = input ().strip () 3 v = {} 4 for i in range(len(s)): 5 if s[i] == ':': 6 v['-' + s[i - 1]] = 1 7 else: 8 v['-' + s[i]] = 0 9 n = int(input ()) 10 for i in range(n): 10