昨天上午是头条2018暑期实习在线笔试，时限2小时，5道题，OI赛制，有部分分。难度比较大。
对于这种时间紧，题目多而且难度大的笔试，建议如果题目没思路，就先写暴力算法。

题目1

对于严格递增的正整数数列 $A = a_1, a_2, … a_n$，如果一个正整数 $T$ 满足：

1. 对于数列 $A$ 中的任意元素 $x$，如果 $x + T$ 不大于 $a_n$，则 $x + T$ 也是 $A$ 中的元素；
2. 对于数列 $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}]$ 相等，所以我们会依次得到：

1. 连续子序列 $[(n-1)-t+1, n-1]$ 等于连续子序列 $[(n-1)-2t+1, (n-1)-t]$；
2. 连续子序列 $[(n-1)-2t+1, (n-1)-t]$ 等于连续子序列 $[(n-1)-3t+1, (n-1)-2t]$；
3. 依次类推，可得 $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$，则整个操作流程如下：

1. 给A充电;
2. A转移到B;
3. 如果B满电，则放空电量;
4. 如果A非空，则重复2-4;
5. 从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;
}