阿里巴巴秋招笔试两道编程题（2021-09-01）

以下字节笔试编程题代码及思路由@nuoyanli提供，有兴趣的可以去这位ACM专业打铁选手那里找到更多刷题技巧。

ps:题面收集于民间

第一题：差分数组 题目描述

生牛得到了一个长度为 n n n 的只包含正整数的数组 a = { a 1 , a 2 , … , a n } a=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\} a={a1​,a2​,…,an​}. 他将对敞组执行下正 的操作直到数组只剩下一个数字:

• 假设当前数组长度为 l l l, 则对于所有的 1 ≤ i ≤ l − 1 1 \leq i \leq l-1 1≤i≤l−1, 按 i i i 从尔到大的顺序令 a i = a_{i}= ai​= a i + 1 − a i a_{i+1}-a_{i} ai+1​−ai​ 井删除 a i a_i ai​.

请你写一个程序帮助牛牛计算最后剩下的数字是几, 由于答案可能很大, 你只需输出答案对 1 0 9 + 7 10^{9}+7 109+7 取摸的结果即可。

输入描述:

第一行输入一个正整数 n n n 。 1 ≤ n ≤ 5 × 1 0 3 , 1 ≤ a i ≤ 1 0 9 1 \leq n \leq 5 \times 10^{3}, 1 \leq a_{i} \leq 10^{9} 1≤n≤5×103,1≤ai​≤109

输出描述:

输出一个数表示最终的答案。

样例

输入 4 1 2 3 4 输出 0 解释：第一次操作后数组变成了{1,1,1}，第二次操作后变成{0,0}，第三次操作后变成{0}，此时只剩下一个元素，所以输出答案0。 输入 3 5 3 2 输出 1 解释：第一次操作后数组变成{-2,-1}，第二次操作后数组变成 {1}，此时只剩下一个元素，所以输出答案1。

思路

由于数据 1 ≤ n ≤ 5 × 1 0 3 1 \leq n \leq 5 \times 10^{3} 1≤n≤5×103比较小，两重 f o r for for循环暴力复杂度为 O ( ( n ∗ ( n + 1 ) / 2 ) O((n*(n+1)/2) O((n∗(n+1)/2)大概是 1 0 7 10^7 107常数比较小可过，每次把数组长度 − 1 -1 −1，然后更新数组中的每个数，记得取模，最后数组只剩一个输出就行了。

参考代码

#include 
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int n;
ll a[5005];

int main()
{
    cin >> n;
    for (int i = 1; i > a[i];
    }
    int len = n;
    while (len > 1)
    {
        for (int i = 1; i > m;
        for (int i = 1; i > x >> y;
            add(y, x);
            d[x]++;
        }
        d[n] = 0;
        string ch;
        cin >> ch;
        int fg = 0;
        if (ch == "Alice")
        {
            fg = 1;
        }
        for (int i = 1; i