题解分析

关键观察

1. 从全零数组开始的最优策略
   如果数组 $a$ 一开始就是全零，并且以后也会被重置成全零，那么考虑后续的若干天。

   • 操作 1（前缀加一）会使数组保持非递增（因为对前缀加一，后面的元素不会超过前面的）。
   • 而条件 $a_j = j$ 要求数组是严格递增的（$1,2,\dots,n$）。
   • 因此，在一次“统计并重置”操作中，最多只能有 $1$ 个位置满足 $a_j = j$（因为非递增序列中不可能有两个不同位置同时等于它们的位置编号）。
   • 另外，重置后数组变为全零，所以不可能连续两天都做统计操作（第二天统计时全零，得分为 $0$）。
     综上，从全零开始，最优策略是交替执行操作 1 和操作 2：
   • 第 $1$ 天做操作 1（使 $a_1 = 1$，其余仍为 $0$）
   • 第 $2$ 天做操作 2（此时只有 $a_1 = 1$，得 $1$ 分，然后重置为全零）
   • 第 $3$ 天再做操作 1，第 $4$ 天再统计……
     这样在 $x$ 天中最多可以获得 $\lfloor x/2 \rfloor$ 分。
     并且这个上界是可以达到的。

2. 第一次重置的时间
   由于数组初始值不一定全零，我们需要决定第一次执行统计操作发生在哪一天（记为第 $i$ 天）。

   • 第 $i$ 天之前的所有天只能执行操作 1（否则会提前重置）。
   • 第 $i$ 天执行统计操作，得分为当前数组中满足 $a_j = j$ 的个数，记为 $c_i$。
   • 重置后数组变为全零，剩下的 $d-i$ 天从全零开始，最优得分为 $\lfloor (d-i)/2 \rfloor$。
     因此，如果固定第一次重置在第 $i$ 天，总得分为：
   $$\text{score}(i) = c_i + \left\lfloor \frac{d-i}{2} \right\rfloor $$

   我们需要对所有可能的 $i$ 计算此值，并取最大值。

3. 枚举的范围
   $d$ 可以高达 $10^9$，不能枚举所有 $d$ 天。但是可以证明，只需要考虑 $i \le 2n$ 即可。
   原因：如果第一次重置在第 $i > 2n$ 天，那么经过 $i-1$ 次前缀加操作后，每个 $a_j$ 至少增加了 $i-1$（因为每次 $b_i \ge 1$，至少给 $a_1$ 加 $1$，但其他位置可能加得少）。但更严格的分析是：当 $i-1 \ge n+1$ 时，所有 $a_j \ge i-1 > n \ge j$，此时 $c_i = 0$。
   于是 $\text{score}(i) = \lfloor (d-i)/2 \rfloor$。
   而如果我们在第一天就重置（$i=1$），得分为 $c_1 + \lfloor (d-1)/2 \rfloor$，其中 $c_1$ 是初始数组中原有的满足 $a_j = j$ 的个数。显然 $c_1 \ge 0$，且 $\lfloor (d-1)/2 \rfloor \ge \lfloor (d-i)/2 \rfloor$（因为 $i \ge 1$）。所以 $i=1$ 不会比任何 $i > 2n$ 差。
   因此只需枚举 $i = 1, 2, \dots, \min(d, 2n)$。

4. 模拟前 $i-1$ 次操作 1
   对于每个枚举的 $i$，我们需要知道经过前 $i-1$ 天（每天做操作 1）后数组的状态。
   由于 $n \le 2000$ 且 $i \le 2n \le 4000$，我们可以直接模拟：

   • 维护一个当前数组 cur，初始为给定的 $a$。
   • 对于第 $t = 1$ 到 $i-1$ 天，执行前缀加操作，其中 $b_t = v_{(t-1)\bmod k}$。
   • 第 $i$ 天的得分为 $\sum_{j=1}^n [cur[j] == j]$。
     每次模拟的复杂度为 $O(i \cdot n)$，所有 $i$ 的总复杂度为 $O(n^2)$ 级别，因为 $n$ 总和不超过 $2000$，完全可行。

5. 最终算法

   • 读入 $n, k, d$，数组 $a$，序列 $v$。
   • 令 limit = min(d, 2 * n)。
   • 初始化 cur = a（使用 0‑索引，但条件变为 cur[j] == j+1）。
   • 初始化答案 ans = 0。
   • 对于 $i = 1$ 到 limit：
     • 计算当前 cur 中满足 cur[j] == j+1 的个数 cnt。
     • 更新 ans = max(ans, cnt + (d - i) // 2)。
     • 如果 $i < d$（且为了下一次迭代），执行第 $i$ 天的操作 1：
       • 取出 b = v[(i-1) % k]。
       • 对 cur[0] 到 cur[b-1] 各加 $1$。
   • 输出 ans。

   注意：如果 $d$ 天中一次重置都不做，得分为 $0$，但我们的枚举中 $i=1$ 已经包含了第一次重置在第 $1$ 天的情况，$i$ 枚举到 limit 也可能包含永远不重置吗？不包含。但 $i=d$ 时，剩余天数为 $0$，得分为 $c_d$，这已经考虑了最后一天重置。而一次都不重置的情况得分为 $0$，显然不会大于某个正得分，因此不影响答案。

复杂度

• 每个测试用例中，枚举 $O(\min(d, 2n))$ 次，每次模拟操作 1 的复杂度为 $O(n)$（因为前缀加是线性的），所以总复杂度为 $O(n \cdot \min(d, n))$。
• 由于所有测试用例的 $n$ 之和不超过 $2000$，总体复杂度约为 $O(2000 \times 4000) = 8 \times 10^6$，非常快。

示例验证

以第一个测试用例为例：

• $n=3, k=4, d=4$，$a=[1,2,3]$，$v=[1,3,2,3]$。
• limit = min(4, 6)=4。
• $i=1$：cur=[1,2,3]，满足 $a_j=j$ 的位置有 $3$ 个（全满足），得分 $3 + \lfloor (4-1)/2 \rfloor = 3+1=4$。然后应用第 $1$ 天操作：$b_1=1$，cur 变为 $[2,2,3]$。
• $i=2$：cur=[2,2,3]，满足条件的位置：$a_2=2$ 成立，共 $1$ 个，得分 $1 + \lfloor (4-2)/2 \rfloor = 1+1=2$。应用第 $2$ 天操作：$b_2=3$，cur 变为 $[3,3,4]$。
• $i=3$：cur=[3,3,4]，无满足条件，得分 $0 + \lfloor (4-3)/2 \rfloor = 0$。应用第 $3$ 天操作：$b_3=2$，cur 变为 $[4,4,4]$。
• $i=4$：cur=[4,4,4]，无满足条件，得分 $0 + \lfloor (4-4)/2 \rfloor = 0$。 最大值为 $4$，输出正确。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, k, d;
        cin >> n >> k >> d;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        vector<int> v(k);
        for (int i = 0; i < k; ++i) cin >> v[i];

        int limit = min(d, 2 * n);
        vector<int> cur = a;
        int ans = 0;

        for (int i = 1; i <= limit; ++i) {
            // 统计当前数组中满足 a_j == j 的个数 (1-indexed)
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if (cur[j] == j + 1) ++cnt;
            }
            ans = max(ans, cnt + (d - i) / 2);
            // 应用第 i 天的操作1，为下一次迭代准备
            if (i < d) { // 如果 i == d 则没有后续，但为了代码简洁仍可执行，不影响
                int b = v[(i - 1) % k];
                for (int j = 0; j < b; ++j) {
                    cur[j]++;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}