昨天上午是头条2018暑期实习在线笔试，时限2小时，5道题，OI赛制，有部分分。难度比较大。
对于这种时间紧，题目多而且难度大的笔试，建议如果题目没思路，就先写暴力算法。
题目1
对于严格递增的正整数数列 $A = a_1, a_2, … a_n$，如果一个正整数 $T$ 满足：
- 对于数列 $A$ 中的任意元素 $x$，如果 $x + T$ 不大于 $a_n$，则 $x + T$ 也是 $A$ 中的元素；
- 对于数列 $A$ 中的任意元素 $x$，如果 $x - T$ 不小于 $a_1$，则 $x - T$ 也是 $A$ 中的元素；
那么称 $T$ 为数列 $A$ 的周期，如果同时满足：所有小于 $T$ 的正整数，都不是 $A$ 的周期，则称 $T$ 为 $A$ 的最小周期。
输入描述：
每组测试样本的输入格式为：
第一行是一个正整数 $N$；
从第二行开始，每行有若干个正整数，依次存放 $n, a_1, a_2, … a_n$，一共有 $N$ 行，也就是 $N$ 个数列。
输出描述：
输出有 $N$ 行，每行打印出对应数列的最小周期。
样例：
输入：
3
3 1 2 3
3 2 4 6
3 3 4 6
输出：
1
2
3
说明：
数据范围：
$N: 0 \lt N \lt 10$
$a_n: a_n \lt 10^9$
$n: $
$0 \lt n \lt 10^3 (50\%)$
$0 \lt n \lt 10^4 (30\%)$
$0 \lt n \lt 10^6 (20\%)$
算法
(KMP) $O(n)$
题目对数列定义了一种新的周期 $T$，难以求直接解。我们先将问题转化为求数列的循环节长度 $t$。
首先将数列：$a_0, a_1, … a_{n-1}$ 转换成 $b_1, b_2, …b_{n-1}, 其中 b_i = a_i - a_{i-1}$。
则 $t$ 是 {$b_i$} 的循环节，当且仅当 $T = a_t - a_0$ 是数列 {$a_i$} 的周期；
由于数列 {$a_i$} 严格单调递增，所以$t$ 是 {$b_i$} 的最短循环节，当且仅当 $T = a_t - a_0$ 是数列 {$a_i$} 的最小周期。
求数列的最短循环节是一个经典问题，可以用KMP算法来做。
首先求出数列{$b_i$}的 $next$ 数组，$next_i$ 是满足在 {$b_i$} 中 $[1, next_i]$ 和 $[i - next_i + 1, i]$ 这两段连续子序列相等的最大值。
则 $t = (n - 1) - next_{n-1}$。
简单解释一下为什么 $t$ 是最短循环节：
根据 $next$ 数组的定义，在数列 {$b_i$} 中，连续子序列 $[(n-1) - next_{n-1} + 1, n-1]$ 和连续子序列 $[1, next_{n-1}]$ 相等，所以我们会依次得到：
- 连续子序列 $[(n-1)-t+1, n-1]$ 等于连续子序列 $[(n-1)-2t+1, (n-1)-t]$；
- 连续子序列 $[(n-1)-2t+1, (n-1)-t]$ 等于连续子序列 $[(n-1)-3t+1, (n-1)-2t]$；
- 依次类推，可得 $t$ 是数列 {$b_i$} 的循环节。且由于 $next_i$ 是满足要求的最大值，所以 $t$ 是最短循环节。
感觉太抽象的同学可以自行画张线段图。 ^^
求出 $t$ 后， $T = a_t - a_0$。
时间复杂度分析：数列变换和KMP算法的时间复杂度均是 $O(n)$，所以总时间复杂度 $O(n)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int n;
int a[N], b[N];
int nxt[N];
void get_next()
{
for (int i = 2, j = 0; i < n; i++)
{
while (j && b[i] != b[j + 1]) j = nxt[j];
if (b[i] == b[j + 1]) j++;
nxt[i] = j;
}
}
int main()
{
int cases;
cin >> cases;
while (cases--)
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 1; i < n; i++) b[i] = a[i] - a[i - 1];
get_next();
int t = n - 1 - nxt[n - 1];
cout << a[t] - a[0] << endl;
}
return 0;
}
题目2
现在有 $n_1+n_2$ 种面值的硬币，其中前 $n_1$ 种为普通币，可以取任意枚，后 $n_2$ 种为纪念币，每种最多只能取1枚，每种硬币有一个面值，问能用多少种方法拼出 $m$ 的面值？
输入描述：
第一行三个整数 $n_1, n_2, m$，分别表示普通币种类数，纪念币种类数和目标面值；
第二行 $n_1$ 个整数，第 $i$ 种普通币的面值 $a[i]$。保证 $a[i]$ 为严格升序；
第三行 $n_2$ 个整数，第 $i$ 中纪念币的面试 $b[i]$。保证 $b[i]$ 为严格升序；
对于 $30\%$ 的测试，保证 $1 \le n_1 + n_2 \le 10$, $1 \le m \le 100$, $1 \le a[i] \le 100$, $1 \le b[i] \le 100$
对于 $100\%$ 的测试，保证 $1 \le n_1 + n_2 \le 100$, $1 \le m \le 100000$, $1 \le a[i] \le 100000$, $1 \le b[i] \le 100000$
输出描述：
输出第一行，包含一个数字 $x$，表示方法总数对 $1000000007(1e9+7)$ 取模的结果。
注意：不要忘记取模！
样例：
输入：
3 1 5
1 2 3
1
输出：
9
说明：
(x) 代表面值为x的普通币，[x]代表面值为x的纪念币，样例所有方法数如下：
(1)(1)(1)(1)(1)
(1)(1)(1)(2)
(1)(1)(3)
(1)(2)(2)
(2)(3)
(1)(1)(1)(1)[1]
(1)(1)[1](2)
(1)[1](3)
[1](2)(2)
算法
(背包问题) $O(mn)$
典型的背包问题，普通币是完全背包问题，纪念币是0/1背包问题。
两种背包问题做法类似，都是先枚举物品，再枚举容量，不同点在于完全背包问题要从小到大枚举容量，0/1背包问题要从大到小枚举容量。
时间复杂度分析：两重循环，复杂度 $O(mn) = 100 * 100000 = 10^7$，1秒内出解毫无压力。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, M = 100010, MOD = 1000000007;
int n1, n2, m;
int a[N], b[N], f[M];
int main()
{
cin >> n1 >> n2 >> m;
for (int i = 0; i < n1; i++) cin >> a[i];
for (int i = 0; i < n2; i++) cin >> b[i];
f[0] = 1;
for (int i = 0; i < n1; i++)
for (int j = a[i]; j <= m; j++)
{
f[j] += f[j - a[i]];
if (f[j] >= MOD) f[j] -= MOD;
}
for (int i = 0; i < n2; i++)
for (int j = m; j >= b[i]; j--)
{
f[j] += f[j - b[i]];
if (f[j] >= MOD) f[j] -= MOD;
}
cout << f[m] << endl;
return 0;
}
题目3
小a在玩一个很简单的游戏，游戏的内容是控制一个小人在一块矩形的空地内走，一旦小人走出矩阵范围，游戏就失败。游戏机上有上下左右四个键，每按一下小人就朝相应的方向走一步。这个游戏过于简单，小a说：“这种游戏我闭着眼睛玩都输不了”。于是他便闭上眼睛，进行一连串的操作。但若他中途输了的话就会停止。
那么问题来了：给定小a的操作，进行Q次询问，你能算出每次询问小人能走多少步吗？
输入描述：
第一行为长度为 $L$ 的字符串 $S$，每个字符依次代表小a的一次操作。’u’代表向上，’d’代表向下，’l’代表向左，’r’代表向右。字符串 $S$ 不会包含其他字符。
第二行是整数 $Q$，代表 $Q$ 次询问。
接下来 $Q$ 行，每行有四个整数：$N,M,X,Y$，保证 $1 \le X \le N$，$1 \le Y \le M$，矩阵的大小为 $N*M$，小人初始位置为 $(X, Y)$。
对于 $30\%$ 的测试，$0 \lt X, Y, L, Q \le 1000$；
对于 $100\%$ 的测试，$0 \lt X, Y, L \le 100000(1e5)$，$o \lt Q \le 30000(3e4)$；
输出描述：
每次询问要求你打印一个整数 $s$（单独一行），代表小人所走的步数。
样例：
输入：
uuurrdddddl
3
5 6 3 3
5 6 4 2
6 6 4 2
输出：
3
10
11
算法1
(二分查找) $O(L + QlogL)$
我们开4个数组 $l[L], r[L], u[L], d[L]$，分别记录操作到每一步时，在四个方向上走到过的最大距离。
则四个数组都是单调递增的。
对于每个询问，我们先求出小人在四个方向上分别最多能走多远：$L_{Max}, R_{Max}, U_{Max}, D_{Max}$，则小人能走到第 $i$ 步，当且仅当过程中没有出界，等价于：
$$
l[i] \le L_{Max} \&\& r[i] \le R_{Max} \&\& u[i] \le U_{Max} \&\& d[i] \le D_{Max}
$$
由于四个数组都是单调递增的，因此我们可以二分出最大步数。
时间复杂度分析：初始化要遍历整个操作序列，复杂度 $O(L)$；对于每个询问，二分查找的复杂度是 $O(logL)$，验证二分值是否合法的复杂度是 $O(1)$，因此总时间复杂度是 $O(L + QlogL)$.
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int N = 100010;
string ops;
int n, m, x, y;
int l[N], r[N], u[N], d[N];
bool check(int mid)
{
return l[mid] <= y - 1 && r[mid] <= m - y
&& d[mid] <= n - x && u[mid] <= x - 1;
}
int main()
{
cin >> ops;
for (int i = 0; i < ops.size(); i++)
{
char op = ops[i];
if (op == 'u') x--;
else if (op == 'd') x++;
else if (op == 'l') y--;
else y++;
l[i + 1] = max(l[i], -y);
r[i + 1] = max(r[i], y);
u[i + 1] = max(u[i], -x);
d[i + 1] = max(d[i], x);
}
int Q;
cin >> Q;
while (Q--)
{
cin >> n >> m >> x >> y;
if (!check(1))
{
cout << 0 << endl;
continue;
}
int L = 0, R = ops.size() - 1;
while (L < R)
{
int mid = L + R + 1 >> 1;
if (check(mid + 1)) L = mid;
else R = mid - 1;
}
cout << min((int)ops.size(), L + 2) << endl;
}
return 0;
}
算法2
(线性扫描) $O(L+Q)$
我们可以对算法1进行优化，在 $l[L], r[L], u[L], d[L]$ 的基础上做进一步初始化，记录在每个方向上到达相应距离所需的最小长度。
对于每个询问，我们分别计算出在每个方向上走出界需要的最小长度，然后取个最小值即可。
复杂度分析：初始化复杂度 $O(L)$，询问复杂度 $O(Q)$，所以总时间复杂度是 $O(L + Q)$。
C++ 代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int N = 100010;
string ops;
int n, m, x, y;
int l[N], r[N], u[N], d[N];
int ln[N], rn[N], un[N], dn[N];
bool check(int mid)
{
return l[mid] <= y - 1 && r[mid] <= m - y
&& d[mid] <= n - x && u[mid] <= x - 1;
}
void init(int a[], int b[])
{
for (int i = 1, j = 1; i <= ops.size(); i++)
{
while (j <= ops.size() && a[j] < i) j++;
b[i] = j;
}
}
int main()
{
cin >> ops;
for (int i = 0; i < ops.size(); i++)
{
char op = ops[i];
if (op == 'u') x--;
else if (op == 'd') x++;
else if (op == 'l') y--;
else y++;
l[i + 1] = max(l[i], -y);
r[i + 1] = max(r[i], y);
u[i + 1] = max(u[i], -x);
d[i + 1] = max(d[i], x);
}
init(l, ln), init(r, rn), init(u, un), init(d, dn);
int Q;
cin >> Q;
while (Q--)
{
cin >> n >> m >> x >> y;
int t = ops.size();
int sl = y > t ? t : ln[y];
int sr = m - y + 1 > t ? t : rn[m - y + 1];
int su = x > t ? t : un[x];
int sd = n - x + 1 > t ? t : dn[n - x + 1];
cout << min(sl, min(sr, min(su, sd))) << endl;
}
return 0;
}
题目4
升序数组中第一个数是1，后续为若干连续的素数，对于数组里面的元素 $m$ 和 $n, (m \lt n)$ 都对应了一个有理数 $m / n$，现在给定这个数组和一个 $K$，要求返回第 $K$ 小的有理数。
输入描述：
每组测试样本的输入格式为：
第一行是一个正整数 $N$；
从第二行开始，每行若干个正整数，依次存放 $K, a_1, a_2, … a_n$，一共有 $N$ 行，也就是 $N$ 组参数。
$K$ 是输入参数，表示需要寻找的顺序第 $K$ 小的有理数，$a_1$ 到 $a_n$ 是以1开始的后续 $n - 1$ 个素数。
、
输出描述：
输出有 $N$ 行，每行两个数字 $m$ 和$n$，空格隔开，分别表示第 $K$ 小有理数的分字和分母。
样例：
输入：
1
3 1 2 3 5
输出：
2 5
备注：
$m, n$ 必须为 $a_1$ 到 $a_n$ 中的满足条件的个数。
数据范围为：
$10 \le N \le 20000$
$10 \le K \le 20000$
$1 \le m \lt n \le 20000$
算法
(数据结构，堆) $O(KlogN)$
此题让求第 $K$ 小数，可以利用堆排序的思想，每次弹出堆中最小数，弹 $K$ 次即可。但如果直接用堆排序做，堆中元素有 $O(N^2)$ 个，建堆的时间复杂度和空间复杂度均是 $N^2 = 400000000 = 4*10^8$，会超时超内存。所以我们需要优化。
仔细思考我们会发现，求当前最小数时，我们不需要将每个分母的所有分子都放进堆里，只需放入该分母未使用过的最小分子即可。如果一个分母的分子被使用了，则将该分子分母从堆中弹出，再将该分母的下一个分子插入堆中。
时间复杂度分析：堆中元素一直维持在 $N$ 个，总共需要 $K$ 次弹出和插入操作，所以总时间复杂度是 $O(KlogN) = 20000 * log20000 = 260000$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <queue>
#define x first
#define y second
#define mp make_pair
using namespace std;
const int N = 20010, M = 1000000;
int a[N];
priority_queue<pair<double, pair<int, int>>> heap;
char buff[M];
int main()
{
int T, n, k;
cin >> T;
while (T--)
{
cin.getline(buff, M);
cin.getline(buff, M);
stringstream seq(buff);
n = 0;
seq >> k;
while (seq >> a[n]) n++;
for (int i = 0; i < n; i++)
heap.push(mp(-1.0 / a[i], mp(0, i)));
int up, down;
while (k--)
{
auto t = heap.top();
heap.pop();
heap.push(mp(a[t.y.x + 1] * -1.0 / a[t.y.y],
mp(t.y.x + 1, t.y.y)));
up = a[t.second.first];
down = a[t.second.second];
}
cout << up << ' ' << down << endl;
}
return 0;
}
题目5
有一台用电容组成的计算器，其中每个电容组件都有一个最大容量值（正整数）。
对于单个电容，有如下操作指令：
- 指令1：放电操作-把该电容当前电量值清零；
- 指令2：充电操作-把该电容当前电量补充到最大容量值；
- 指令3：转移操作-从电容 $A$ 中尽可能多的将电量转移到电容 $B$ ，转移不会有电量损失，如果能够充满 $B$ 的最大容量，那剩余的电量仍然会留在 $A$ 中。
现在已知有两个电容，其最大容量分别为 $a$ 和 $b$，其初始状态都是电量值为 $0$，希望通过一些列的操作可以使其中某个电容（无所谓哪一个）中的电量值等于 $c$ （$c$也是正整数），这一些列操作所用的最少指令条数记为 $M$，如果无论如何操作，都不可能完成，则定义此时 $M=0$。
显然对于每一组确定的 $a,b,c$，一定会有一个 $M$ 与之对应。
输入描述：
每组测试样本的输入格式为：
第一行是一个正整数 $N$；
从第二行开始，每行都是 $3$ 个正整数依次组成一组 $a,b,c$，一共有 $N$ 组；
输出描述：
输出为 $N$ 行，每行打印每一组对应的 $M$
样例
输入：
2
3 4 2
2 3 4
输出：
4
0
说明
对于 $(3, 4, 2)$，最少只需要4个指令即可完成：
（设最大容量为 $3$ 的是 $A$ 号电容，另一个是 $B$ 号电容）
操作：（充电 $A$）=> （转移 $A$ -> $B$） => （充电 $A$）=> （转移 $A$ -> $B$）。
对于 $(2, 3, 4)$，显然不可能完成，输出0。
备注：
数据范围：
$N: 0 \lt N \lt 100$
$a, b, c$：
$0 \lt a, b, c \lt 10^5 (50\%)$
$0 \lt a, b, c \lt 10^7 (30\%)$
$0 \lt a, b, c \lt 10^9 (20\%)$
算法
(扩展欧几里得算法,裴蜀定理) $O(NlogV)$
首先如果 $c \gt a$ 并且 $c \gt b$ 时，操作显然无法完成。所以我们只考虑 $c \le Max(a, b)$ 的情况。
我们将两个电容看做一个整体，与外界只有两种操作：充电和放电。充电会使整个系统的总电量增加，放电会使整个系统的总电量减少。
我们先判断整个系统的总电量是否可以等于 $c$，即是否存在整数 $x, y$，使得 $ax + by = c$。如果 $x, y$ 是负整数，则表示放电，如果是正整数，则表示充电。
根据裴蜀定理，等式可以满足当且仅当 $gcd(a, b) | c$。
我们现在来考虑当 $gcd(a, b) | c$ 时，如何计算最少操作次数：
根据裴蜀定理，存在整数 $x, y$，使得 $ax + by = c$，且由于 $c \le Max(a, b)$，所以 $x, y$ 一定一正一负，或者一正一零。
我们现在来考虑怎么统计 $ax + by = c$ 的操作次数。不妨假设 $x \gt 0$，则整个操作流程如下：
- 给A充电;
- A转移到B;
- 如果B满电，则放空电量;
- 如果A非空，则重复2-4;
- 从1开始重复整个过程，直到A或B中的电量是 $c$为止。
如果 $c \gt a$，则最终会是B里先有 $c$ 的电量（因为A存不下），此时有 $x$次充电，$-y$次放电，$x-y$次转移，共 $2x - 2y$ 次操作；
如果 $c \le a$，假设B中先有 $c$ 的电量，则 $a, b \ge c$，所以 $b=c$，仅需一次操作；假设A中先有 $c$ 的电量，则有 $x$ 次充电，$x-y-1$ 次转移，$-y-1$次放电，共 $2x - 2y - 2$ 次操作；
因此我们只需最小化 $|x| + |y|$。可以先用扩展欧几里得算法求出任意一组 $(x, y)$，则
$$
\\left\\{
\\begin{aligned}
x + kb/gcd(a,b) \\\\
y - ka/gcd(a,b)
\\end{aligned}
\\right.
, k = …, -2, -1, 0, 1, 2, …
$$
就是该等式的全部整数解，我们找出和 $0$ 最接近的两组 $(x, y)$（一组 $x \gt 0$, 另一组 $y \gt 0$ ），然后取操作次数较小的一组即可。
时间复杂度分析：扩展欧几里得算法的复杂度是 $O(logV)$，一共 $N$ 组测试数据，所以总时间复杂度是 $O(NlogV)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
LL q = gcd(b, a % b, y, x);
y -= a / b * x;
return q;
}
int main()
{
int T;
cin >> T;
while (T--)
{
LL a, b, c, x, y;
cin >> a >> b >> c;
int d = gcd(a, b, x, y);
if (c > a && c > b || c % d)
{
cout << 0 << endl;
continue;
}
if (c == a || c == b)
{
cout << 1 << endl;
continue;
}
if (y > 0) swap(x, y), swap(a, b);
LL a2 = a / d, b2 = b / d;
x *= c / d, y *= c / d;
LL k = x / b2;
x -= k * b2, y += k * a2;
LL res;
if (c > a) res = 2 * (x - y);
else res = 2 * (x - y - 1);
x -= b2, y += a2;
if (c > b) res = min(res, 2 * (y - x));
else res = min(res, 2 * (y - x - 1));
cout << res << endl;
}
return 0;
}
请问题目5里的
转移次数具体是怎么计算得到的 ？tql，笔试也太难了，背包问题混合，数论！