2017 年实验班选拔试题

求和号（10 分） 题目描述：在数学运算中经常要计算连续的和。例如，计算$1+2+\cdots +n$，或者等比数列$a+a^2+\cdots +a^n$。我们使用求和号在“$\sum$”来表示这类连续的和。 通常在“$\sum$”的下方标自变量名称和初始值，在“$\sum$”的上方标终止值，在“$\sum$”的右方写表达式，求和号也可以嵌套使用，例如： $$\sum _{i=1}^3\sum _{j=1}^2{a}_i{b}_j=a_1{b}_1+a_1{b}_2+a_2{b}_1+a_2{b}_2+a_3{b}_1+a_3{b}_2$$ 试编写程序计算$\sum _{i=1}^n\sum _{j=1}^m{a}_i{b}_j$。 输入格式：第 1 行有两个整数，$n$ 和 $m$。以下第 $2$ 行到第 $n＋1$ 行，每行包含一个整数，第 $i+1$ 行表示 $a_i$的值。紧接着从第 $n＋2$ 行到第 $n＋m＋1$ 行，每行包含一个整数，第 $i+n＋1$ 行表示 $b_j$的值。每次输入只包含一组测试数据。数据范 围：$1\le n,m\le 100000$，所有整数的绝对值$\le 10000$。 输出格式：对每组测试数据输出一行，仅含一个整数，即你计算得到的答案。 输入样例： 3 2 1 2 3 5 7 输出样例： 72

由于$1\le n,m\le 100000$，直接计算会超时，因此将公式转换为$\sum _{i=1}^n\sum _{j=1}^m{a}_i{b}_j=b_1\cdot \sum _{i=1}^n{a}_i+b_2\cdot \sum _{i=1}^n{a}_i+...+b_m\cdot \sum _{i=1}^n{a}_i=\sum _{i=1}^n{a}_i\cdot \sum _{i=1}^m{b}_i$计算。复杂度为$O(n)$。

#include<bits/stdc++.h> using namespace std; int n, m; long long suma, sumb; int main() { scanf("%d%d", &n, &m); for (int i = 1, a; i <= n; i++) scanf("%d", &a), suma += a; for (int i = 1, b; i <= m; i++) scanf("%d", &b), sumb += b; printf("%lld\n", suma * sumb); return 0; } 谁是中间的那个（15 分） 题目描述：一天，农夫乔伊像往常一项来到了他的农场，他突然对他的奶牛的产量产生了兴趣。他想知道产奶量处于中间的那头奶牛的产奶量是多少。“处于中间的”意思是说，其中有一半牛的产奶量比它多，另一半牛的产奶量比它少。 现在由你来完成这个问题的程序。 输入格式：仅包括一组测试数据，第一行一个正整数 $N(1\le N\le 10000)$,接下来 $N$ 行，每行一个正整数，不会超过 $10^6$，第 $i+1$ 行的数字代表第 $i$ 头牛的产奶量。 输出格式：输出处于中间的牛的产奶量。 输入样例： 5 1 2 3 4 5 输出样例： 3

“其中有一半牛的产奶量比它多，另一半牛的产奶量比它少”这句话不是很严谨，但是很明显是排序后输出中间的数，复杂度为$O(n\log n)$。

#include<bits/stdc++.h> using namespace std; const int N = 10010; int n, a[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%d", &a[i]); sort(a + 1, a + n + 1); printf("%d\n", a[(n + 1) / 2]); return 0; }

另外，借助快速排序的思想，只需要$O(n)$的时间就可以求出第$k$小的数。 每次选取基准值后，我们可以统计出小于等于基准值的数的数量 $cnt$，如果$k=cnt+1$，那么基准值就是第$k$小的数；如果 $k＜cnt+1$,我们就在左半段(小于或等于基准值的数中)寻找第$k$小的数；如果$k>cnt+1$，我们就在右半段(比基准值大的数中)寻找第$k-(cnt+1)$小的数。因此，寻找第k小的数时，我们只需要进入左右两半二者之一继续递归。 在平均情况下，复杂度为$n+\frac{n}{2}+\frac{n}{4}+\cdots +1=O(n)$。 为防止复杂度退化至$O(n^2)$，最好给每一个数附加一个随机的权值，并且在待查找区间中随机选择基准值。

#include<bits/stdc++.h> using namespace std; const int N = 10010; int n; pair<int, int> a[N]; int solve(int l, int r, int k) { if (l == r)return a[l].first; int x = l, y = r, p = l + rand() % (r - l + 1); while (x < y) { while (a[p] < a[y])y--; swap(a[y], a[p]), p = y; while (x < y && a[x] <= a[p])x++; swap(a[x], a[p]), p = x; } if (p - l + 1 == k)return a[l + k - 1].first; if (p - l + 1 > k)return solve(l, p - 1, k); return solve(p + 1, r, k - (p - l + 1)); } int main() { srand((unsigned) time(0)); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i].first); a[i].second = rand(); } printf("%d\n", solve(1, n, (n + 1) / 2)); return 0; } Doubles（15 分） 题目描述：给出 $2$ 到 $15$ 个不同的正整数，计算在这些数里面有多少数据对满足一个数是另一个数的的两倍。比如给出： $1$ $4$ $3$ $2$ $9$ $7$ $18$ $22$ 答案是 $3$，因为 $2$ 是 $1$ 的两倍，$4$ 是 $2$ 的两倍，$18$ 是 $9$ 的两倍。 输入格式：输入包括多组测试数据。每组测试数据包括一行，给出 $2$ 到 $15$个两两不同且大于 $0$ 小于 $1000000$ 的正整数。每一行的最后一个数是 $0$,表示这一行的结束。输入的最后一行只包括一个整数$-1$，这行表示输入数据的结束，不用进行处理。 输出格式：对于每组测试数据，输出一行，给出有多少个数对满足其中一个 数是另一个数的两倍。 输入样例： 1 4 3 2 9 7 18 22 0 2 4 8 10 0 7 5 11 13 1 3 0 -1 输出样例： 3 2 0

和16年的题有重复，这里给出$O(n)$的做法。

#include<bits/stdc++.h> using namespace std; const int N = 1000010; int a[N]; unordered_map<int, int> cnt; int main() { while (scanf("%d", &a[1]), a[1] != -1) { int n = 1; while (scanf("%d", &a[n + 1]), a[n + 1])n++; long long ans = 0; cnt.clear(); for (int i = 1; i <= n; i++) { ans += cnt[a[i] * 2]; if (a[i] % 2 == 0)ans += cnt[a[i] / 2]; cnt[a[i]]++; } printf("%lld\n", ans); } return 0; } Power Strings（30 分） 题目描述：给出两个字符串 $a$ 和 $b$，我们定义 $a\ast b$ 为它们的毗连。例如，如果 $a$=”abc”并且 $b$=”def”，那么 $a\ast b$=”abcdef”。如果我们把毗连视为乘法，那么非负整数的指数定义为：$a^0=$””（空串），$a^{(n+1)}=a\ast (a^n)$。 输入格式：输入包含多个测试用例。每个测试用例是一个可打印字符的组成的字符串 $s$。$s$ 的长度至少是 $1$，不超过 1 百万个字符。输入的最后一行是是一个句号，表示输入数据的结束，不用处理。 输出格式：对于每组测试数据，输出一行，对于字符串 $s$ 输出最大的 $n$，使得对于某个字符串 $a$，$s=a^n$。 输入样例： abcd aaaa . 输出样例 1 4

设字符串长度为$n$，从小到大枚举循环节的长度$i$，如果$n\mathrm{m}\mathrm{o}\mathrm{d}i=0$，则检查$i$是否合适，如果合适输出$n/i$。 由于数据规模是$10^6$，为了防止超时，采用字符串哈希算法减少字符串比较的时间。同时只枚举$[1,\sqrt{n}]$范围内的循环节长度，顺便找到$[\sqrt{n},n]$范围内要枚举的循环节长度，把枚举循环节的复杂度降低至$O(\sqrt{n})$。最终时间复杂度应当远小于$O(n\sqrt{n})$,实测完全可行。

#include<bits/stdc++.h> #define ull unsigned long long using namespace std; const int N = 1e6 + 10; struct Hash { const int base = 131; ull h[N], p[N]; inline ull get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } inline void init(char *a) { int n = strlen(a + 1); p[0] = 1; for (int i = 1; i <= n; i++) { h[i] = h[i - 1] * base + a[i] - 'a' + 1; p[i] = p[i - 1] * base; } } } H; char a[N]; int n; vector<int> tmp; inline bool check(int x) { ull cmp = H.get(1, x); for (int i = x + 1; i + x - 1 <= n; i += x) if (H.get(i, i + x - 1) != cmp) return false; return true; } int main() { while (scanf("%s", a + 1), a[1] != '.') { H.init(a); n = strlen(a + 1); int ans = 0; tmp.clear(); for (int i = 1; i <= sqrt(n); i++) if (n % i == 0) { tmp.push_back(n / i); if (check(i)) { ans = n / i; break; } } if (!ans) for (int i = tmp.size() - 1; i >= 0; i--) if (check(tmp[i])) { ans = n / tmp[i]; break; } printf("%d\n", ans); } return 0; }

根据前缀函数的性质可以$O(n)$复杂度求出。 对于字符串$s$和$0<p\le |s|$，若$s[i]=s[i+p]$对于$i\in [1,|s|-p]$成立，则称$p$是$s$的周期。 对字符串$s$和$0\le r\le |s|$，若$s$长度为$r$的前缀和长度为$r$的后缀相等，就称$s$长度为$r$的前缀是$s$的$border$。 由$s$有长度为$r$的$border$可以推导出$|s|-r$是$s$的周期。 根据前缀函数的定义，可以得到$s$所有的$border$长度,即$Next[n],Next[Next[n]],Next[Next[Next[n]]],\dots$ 最终答案为总长度$n$除以能被$n$整除的最小周期。 由于前缀函数可以$O(n)$复杂度求出，因此时间复杂度为$O(n)$。

#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; char a[N]; int n, Next[N]; void build_next() { for (int i = 2, j = 0; i <= n; i++) { while (j && a[i] != a[j + 1])j = Next[j]; if (a[i] == a[j + 1])j++; Next[i] = j; } } int main() { while (scanf("%s", a + 1), a[1] != '.') { n = strlen(a + 1); build_next(); printf("%d\n", n % (n - Next[n]) ? 1 : n / (n - Next[n])); } return 0; } 循环有序序列（30 分） 题目描述：定义一种循环有序序列，该序列可看做首尾相连的圈状序列，从某个位置开始向后数至该位置的前一位，数过的元素都是从小到大排列的。例如，对于 $1，2，3，4$这四个数，符合条件的循环有序序列有 $1,2,3,4;2,3,4,1;3,4,1,2;4,1,2,3$ 四个。 定义一种操作，可以在序列里任选一个位置的数，把它移动到序列的第一个位置，例如序列 $1,2,3,4$，对 $3$ 进行操作后，序列变为 $3,1,2,4$。 现在输入一个长度为 $n$ 的初始序列，问至少经过多少次操作，可以使原序列变成一个循环有序序列。 输入格式：输入数据包含若干测试用例。每个测试用例的格式为：第 $1$ 行：一个整数 $N$$(1\le N\le 30000)$；第 $2$ 行：$N$ 个整数 $a_i$，$(1\le a_i\le N)$，并且对于任意的 $i\ne j$,$a_i\ne a_j$。输入的最后一行为 0，表示输入结束，不需要做处理。 输出格式：对每个测试用例，输出一行，该行包括一个整数，表示至少需要的操作次数。 输入样例： 4 3 2 4 1 0 输出样例： 1

说明：对于序列 $3,2,4,1$，只需要做一次操作，得到 $2,3,4,1$ 即是循环有序序列。 显然是要找到当前序列的子序列中长度最大的循环有序序列，然后剩余元素移到开头一定能使整个序列变成成循环有序序列且操作数最少。 设$dp[i]$表示当前以$i$为结尾的子序列中可构成的循环有序序列中最大的长度，初始为$0$。遍历序列，对于当前遍历到的序列中的数$x$,更新$dp[x]=dp[(n+x-2)\mathrm{m}\mathrm{o}\mathrm{d}n+1]+1$。 最后答案为$n-\underset{i=1}{\overset{n}{\max }}dp[i]$。时间复杂度为$O(n)$。

#include<bits/stdc++.h> using namespace std; const int N = 3e4 + 10; int n, dp[N]; int main() { while (scanf("%d", &n), n) { memset(dp, 0, sizeof(int) * n); for (int i = 1, x; i <= n; i++) { scanf("%d", &x), x--; dp[x] = dp[(x - 1 + n) % n] + 1; } printf("%d\n", n - *max_element(dp, dp + n)); } return 0; }