2019 年实验班选拔试题

1.最大公约数（10分） 题目描述：已知两个正整数$a$和$b$，求这两个数的最大公约数$GCD(a,b)$。 输入格式：测试数据包括多组数据。测试数据的第一行是一个整数$n(n<50)$，表示有$n$组输入数据。其后有$n$行数据，每行数据包括由空格分隔的两个正整数$a$和$b$。 输出格式：对于每组测试数据，输出一行，给出对应输入数据的$GCD(a,b)$。

输入样例： 1 24 16 输出样例： 8

欧几里得算法，单次计算复杂度为$O(log(a+b))$。 C++ 内置 __gcd() 函数。

#include<bits/stdc++.h> using namespace std; int T, x, y; //int gcd(int a, int b) { // return b ? gcd(b, a % b) : a; //} int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &x, &y); printf("%d\n", __gcd(x, y)); } return 0; }

2.连续素数的和（10分) 题目描述：一些正整数能够表示为一个或多个连续素数的和。给出一个正整数，有多少个这样的表示?例如，整数$53$有两个表示，分别是：$5+7+11+13+17$和$53$；整数$41$有三个表示，分别是：$2+3+5+7+11+13$，$11+13+17$和$41$；整数$3$只有一个表示$3$；整数$20$没有这样的表示。注意，这里要求必须是连续的素数相加，因此对于整数$20$，$7+13$和$3+5+5+7$，都不是有效的表示。请写出一个程序，对于给出的正整数，给出连续素数的和的表示数。 输入格式：测试数据包括多组数据。每一行是一个正整数$n$，$2\le n\le 10000$。输入数据的最后一行为$0$，表示输入结束。 输出格式：对于每组测试数据（除了输入数据最后一行的$0$)，输出一行。输出的每一行，对应输入的正整数，给出连续素数和的表示数量。输出中没有其它的字符。

输入样例： 2 3 17 41 20 666 12 53 0 输出样例： 1 1 2 3 0 0

首先利用线性筛法筛出前$10000$个数中的素数，然后求前缀和，存在数组$p$中。对于每个数$x$，寻找有几对$i$，$j$，使得$p[i]+x=p[j]$，统计的数量即为答案。

#include<bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int v[N], p[N], tot; unordered_map<int, bool> e; inline void primes(int n) { for (int i = 2; i <= n; i++) { if (v[i] == 0)v[i] = i, p[++tot] = i; for (int j = 1; j <= tot; j++) { if (p[j] > v[i] || p[j] > n / i)break; v[i * p[j]] = p[j]; } } for (int i = 1; i <= tot; i++)p[i] += p[i - 1], e[p[i]] = true; } inline int solve(int x) { int cnt = 0; for (int i = 0; p[i] + x <= p[tot]; i++) if (e[p[i] + x])cnt++; return cnt; } int main() { primes(10000); int n; while (scanf("%d", &n), n) printf("%d\n", solve(n)); return 0; }

3.487-3279(20分） 题目描述：企业在广告推广中，喜欢使用容易记住的电话号码。让电话号码容易记的一种方法是，将电话号码写成容易记住的单词或短语。例如，如果你要给滑铁卢大学打电话时，可以拨打TUT-GLOP。有时，只将电话号码中的部分数字拼写成单词。例如，可以拨打310-GINO向Gino定一份披萨。让电话号码容易记的另一种方法是，以一种好记的方式对号码的数字分组。例如拨打必胜客的“三个十”号码3-10-10-10，也可以定披萨。 电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有个一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下： A、B和C映射到2； D、E和F映射到3； G、H和I映射到4； J、K和L映射到5； M、N和0映射到6； P、R和S映射到7； T、U和V映射到8； W、X和Y映射到9。 Q和Z没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。 如果两个号码有相同的标准格式，那么它们就是等同的（相同的拨号)。请编写一个程序，检查电话号码簿中的电话号码中是否有相同的电话号码。 输入格式：测试数据包括多组数据。测试数据的第一行是一个正整数$n(n\le 100000)$，表示电话号码簿中号码的数量。其后有n行数据，每行数据是一个电话号码，每个电话号码由数字、大写字母（除了Q和Z)以及连接符组成。每个电话号码中只会刚好有$7$个数字或字母。 输出格式：对于电话号码簿中每个出现重复的号码产生一行输出，输出号码的标准格式紧限一个空格，然后是该号码重复的次数。如果存在多个重复的号码，则按照号码的字典序升序输出。如果输入数据中没有重复的号码，输出一行：No duplicates.

输入样例： 12 4873279 ITS-EASY 888-4567 3-10-10-10 888-GLOP TUT-GLOP 967-11-11 310-GINO F101010 888-1200 -4-8-7-3-2-7-9- 487-3279 输出样例： 310-1010 2 487-3279 4 888-4567 3

利用map统计个数即可，map内部已经把键按字典序升序排序，个数大于1的直接输出键和值即可。

#include<bits/stdc++.h> using namespace std; map<char, char> mp; map<string, int> cnt; int n; int main() { mp['A'] = mp['B'] = mp['C'] = '2'; mp['D'] = mp['E'] = mp['F'] = '3'; mp['G'] = mp['H'] = mp['I'] = '4'; mp['J'] = mp['K'] = mp['L'] = '5'; mp['M'] = mp['N'] = mp['O'] = '6'; mp['P'] = mp['R'] = mp['S'] = '7'; mp['T'] = mp['U'] = mp['V'] = '8'; mp['W'] = mp['X'] = mp['Y'] = '9'; scanf("%d", &n); while (n--) { string s1, s2; cin >> s1; for (auto it:s1) { if (it == '-')continue; else if (it >= '0' && it <= '9')s2.push_back(it); else s2.push_back(mp[it]); } cnt[s2]++; } bool flag = false; for (auto it:cnt) if (it.second > 1) { flag = true; for (int i = 0; i <= 2; i++)putchar(it.first[i]); putchar('-'); for (int i = 3; i <= 6; i++)putchar(it.first[i]); putchar(' '); printf("%d\n", it.second); } if (!flag)puts("No duplicates."); return 0; }

4.Where Amazing Happens(20分) Problem Description As the premier men’s professional basketball league in the world, the National Basketball Association (NBA) has witnessed many superstars, legendary teams and precious friendships. Here is a list of every season’s champion from the league’s inception in 1946 to 2019. Season Champion 2018-19 Toronto Raptors 2017-18 Golden State Warriors 2016-17 Golden State Warriors 2015-16 Cleveland Cavaliers 2014-15 Golden State Warriors 2013-14 San Antonio Spurs 2012-13 Miami Heat 2011-12 Miami Heat 2010-11 Dallas Mavericks 2009-10 L.A. Lakers 2008-09 L.A. Lakers 2007-08 Boston Celtics 2006-07 San Antonio Spurs 2005-06 Miami Heat 2004-05 San Antonio Spurs 2003-04 Detroit Pistons 2002-03 San Antonio Spurs 2001-02 L.A. Lakers 2000-01 L.A. Lakers 1999-00 L.A. Lakers 1998-99 San Antonio Spurs 1997-98 Chicago Bulls 1996-97 Chicago Bulls 1995-96 Chicago Bulls 1994-95 Houston Rockets 1993-94 Houston Rockets 1992-93 Chicago Bulls 1991-92 Chicago Bulls 1990-91 Chicago Bulls 1989-90 Detroit Pistons 1988-89 Detroit Pistons 1987-88 L.A. Lakers 1986-87 L.A. Lakers 1985-86 Boston Celtics 1984-85 L.A. Lakers 1983-84 Boston Celtics 1982-83 Philadelphia 76ers 1981-82 L.A. Lakers 1980-81 Boston Celtics 1979-80 L.A. Lakers 1978-79 Seattle Sonics 1977-78 Washington Bullets 1976-77 Portland Trail Blazers 1975-76 Boston Celtics 1974-75 Golden State Warriors 1973-74 Boston Celtics 1972-73 New York Knicks 1971-72 L.A. Lakers 1970-71 Milwaukee Bucks 1969-70 New York Knicks 1968-69 Boston Celtics 1967-68 Boston Celtics 1966-67 Philadelphia 76ers 1965-66 Boston Celtics 1964-65 Boston Celtics 1963-64 Boston Celtics 1962-63 Boston Celtics 1961-62 Boston Celtics 1960-61 Boston Celtics 1959-60 Boston Celtics 1958-59 Boston Celtics 1957-58 St. Louis Hawks 1956-57 Boston Celtics 1955-56 Philadelphia Warriors 1954-55 Syracuse Nats 1953-54 Minneapolis Lakers 1952-53 Minneapolis Lakers 1951-52 Minneapolis Lakers 1950-51 Rochester Royals 1949-50 Minneapolis Lakers 1948-49 Minneapolis Lakers 1947-48 Baltimore Bullets 1946-47 Philadelphia Warriors

(quoted from http://www.nba.com/history/nba-season-recaps/)

Given the team name, it won’t be difficult for you to count how many times this team(with exactly the same name) has made amazing happen. Input The first line gives the number of test cases. Each case contains one string S representing the team to be queried.$(T<=30)$.S consists of English letters, digits, punctuations and spaces. And $1<=length(S)<=30$. Output For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from $1$) and y is the times this team has won the championship according to the list above.

Sample Input 2 Cleveland Cavaliers Oklahoma City Thunder Sample Output Case #1: 1 Case #2: 0

打表。

#include<bits/stdc++.h> using namespace std; int T; multiset<string> s = { "Toronto Raptors", "Golden State Warriors", "Golden State Warriors", "Cleveland Cavaliers", "Golden State Warriors", "San Antonio Spurs", "Miami Heat", "Miami Heat", "Dallas Mavericks", "L.A. Lakers", "L.A. Lakers", "Boston Celtics", "San Antonio Spurs", "Miami Heat", "San Antonio Spurs", "Detroit Pistons", "San Antonio Spurs", "L.A. Lakers", "L.A. Lakers", "L.A. Lakers", "San Antonio Spurs", "Chicago Bulls", "Chicago Bulls", "Chicago Bulls", "Houston Rockets", "Houston Rockets", "Chicago Bulls", "Chicago Bulls", "Chicago Bulls", "Detroit Pistons", "Detroit Pistons", "L.A. Lakers", "L.A. Lakers", "Boston Celtics", "L.A. Lakers", "Boston Celtics", "Philadelphia 76ers", "L.A. Lakers", "Boston Celtics", "L.A. Lakers", "Seattle Sonics", "Washington Bullets", "Portland Trail Blazers", "Boston Celtics", "Golden State Warriors", "Boston Celtics", "New York Knicks", "L.A. Lakers", "Milwaukee Bucks", "New York Knicks", "Boston Celtics", "Boston Celtics", "Philadelphia 76ers", "Boston Celtics", "Boston Celtics", "Boston Celtics", "Boston Celtics", "Boston Celtics", "Boston Celtics", "Boston Celtics", "Boston Celtics", "St. Louis Hawks", "Boston Celtics", "Philadelphia Warriors", "Syracuse Nats", "Minneapolis Lakers", "Minneapolis Lakers", "Minneapolis Lakers", "Rochester Royals", "Minneapolis Lakers", "Minneapolis Lakers", "Baltimore Bullets", "Philadelphia Warriors" }; int main() { scanf("%d", &T); getchar(); for (int i = 1; i <= T; i++) { string a; getline(cin, a); printf("Case #%d: %d\n", i, s.count(a)); } return 0; }

5.数字排序（40分） 题目描述：已知两个整数序列$A=(a_1,a_2，a_3,.\dots ,a_n)$和$B=(b_1,b_2,b_3\dots ,b_m)$,将$a_i(1<i\le n)$乘以$b_j(1\le j\le m)$，产生一个有着$m\ast n$个整数的新序列。请编写一个程序，将新序列按照升序排序，并找到排序后的第$k$个数字。 输入格式：测试数据包括多组数据。 每组测试数据的第一行是三个整数$n(1\le n\le 10000)$，$m(1\le m\le 10000)$和$k(1\le k\le m\ast n)$。 第二行包含有$n$个整数，表示序列$A$。 第三行包含有$m$个整数，表示序列$B$。 序列$A$和$B$中的所有整数都位于区间$[0，10000]$。 每组测试数据之后有一个空行。 输出格式：对于每组测试数据，输出一行，给出对应测试数据的结果。

输入样例： 1 3 3 1 3 2 1 3 3 7 1 2 3 1 2 3 输出样例： 3 6

先将数组$a$，$b$按从小到大排序，然后二分第$k$个数的值，check函数操作类似于双指针，从大到小枚举$a$，当枚举到$i$时找到最大的$j$使得$b[j+1]\cdot a[i]<=x$则枚举到$i-1$时找到的$j^{\prime }$一定满足$j^{\prime }\ge j$，因此继续从原来的$j$枚举。 总体复杂度为$O(n\log n^2)$。

#include<bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int a[N], b[N], n, m, k; inline bool check(int x) { int cnt = 0, j = 0; for (int i = n; i >= 1; i--) { while (j < m && b[j + 1] * a[i] <= x)j++; cnt += j; } return cnt >= k; } int main() { while (scanf("%d%d%d", &n, &m, &k) != EOF) { for (int i = 1; i <= n; i++)scanf("%d", &a[i]); for (int i = 1; i <= m; i++)scanf("%d", &b[i]); sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + m); int l = 0, r = a[n] * b[m], ans; while (l <= r) { int mid = (l + r + 1) >> 1; if (check(mid))r = mid - 1, ans = mid; else l = mid + 1; } printf("%d\n", ans); } return 0; }