题目描述

难度分:$1500$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 3 \times 10^5$。

每组数据输入$n(1 \leq n \leq 3 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^{12})$。

数组下标从$1$开始。用$|a|$表示数组当前长度。

你可以执行多次如下操作：

• 选择一个$[2,|a|]$中的下标$i$，满足$a[i]=|a|+1-i$。然后在$a$的末尾添加$i-1$个$0$。

输出$|a|$的最大值。

输入样例

4
5
2 4 6 2 5
5
5 4 4 5 1
4
6 8 2 3
1
1

输出样例

10
11
10
1

算法

BFS

挺有意思的一个题，乍一看一头雾水，但只要转化出来本质就非常简单。如果选择的是满足$a[i]=|a|+1-i$的$i$，就可以使得数组长度增加$i-1$，也就是说如果$a[i]+i-1=|a|$，数组长度就可以增加$i-1$，变为$|a|+i-1=a[i]+2(i-1)$。

这样就很容易了，这就相当于有个图，节点$a[i]+i-1$向节点$a[i]+2(i-1)$存在一条有向边，从$n$节点出发能够到达的最大编号节点是多少。先遍历原始$a$数组建立图的邻接表，然后从$n$开始进行BFS，维护途中经过节点的最大编号即可。

复杂度分析

时间复杂度

本质上是个图的遍历，最差情况下会遍历$O(n)$级别的节点，因此时间复杂度为$O(n)$。

空间复杂度

BFS遍历的过程中需要使用队列和防止重复遍历节点的集合$vis$，它们的空间都是$O(n)$的，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 300010;
int T, n;
LL a[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        unordered_map<LL, vector<LL>, custom_hash> graph;
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            if(i > 1) {
                graph[a[i] + i - 1].push_back(a[i] + (i - 1)*2);
            }
        }
        LL len = n;
        unordered_set<LL> vis;
        vis.insert(len);
        queue<LL> q;
        q.push(len);
        while(!q.empty()) {
            LL cur = q.front();
            q.pop();
            len = max(len, cur);
            for(LL nxt: graph[cur]) {
                if(vis.find(nxt) == vis.end()) {
                    vis.insert(nxt);
                    q.push(nxt);
                }
            }
        }
        printf("%lld\n", len);
    }
    return 0;
}