Cow Program

题目描述

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$, and performs the following operations on a sequence $a_1, a_2, \ldots, a_n$ of positive integers:

1. Initially, $x=1$ and $y=0$. If, after any step, $x \le 0$ or $x \gt n$, the program immediately terminates.
2. The program increases both $x$ and $y$ by a value equal to $a_x$ simultaneously.
3. The program now increases $y$ by $a_x$ while decreasing $x$ by $a_x$.
4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!

You are given the sequence $a_2, a_3, \ldots, a_n$. Suppose for each $i \ (1 \le i \le n-1)$ we run the program on the sequence $i, a_2, a_3, \ldots, a_n$. For each such run output the final value of $y$ if the program terminates or $-1$ if it does not terminate.

题意概述

有一个包含$n$个数的数列，第$i$项为$a_i$。现有两个数$x=1, \ y=0$。执行以下操作

while (!(x <= 0  x > n)) {
  y += a[x], x += a[x];
  if (!(x <= 0  x > n)) y += a[x], x -= a[x];
}

给定$a_2, a_3, \ldots, a_n$，对于所有$i \in [1, n-1]$，求对数列$i, a_2, a_3, \ldots, a_n$执行操作后$y$的值。若无限循环则输出$-1$。

数据范围：$2 \le n \le 2 \times 10^5, \ 1 \le a_i \le 10^9$。

算法分析

直接模拟肯定会超时。易知从一个位置开始执行操作的顺序是固定的，因此可以用记忆化搜索，记录下每一个位置向左或向右执行操作后的$y$值。如果搜索到一个已搜索过但还没有得到答案的位置，则返回$-1$。

代码

#include <iostream>
using namespace std;
long long n, a[300001], ans[300001][2], to[300001][2], vis[300001][2];
long long dfs(long long t, long long m) {
  if (ans[t][m]) return ans[t][m];
  if (vis[t][m]) return ans[t][m] = -1; vis[t][m] = true;
  if (to[t][m] < 1 || to[t][m] > n) return ans[t][m] = a[t];
  long long ret = dfs(to[t][m], !m);
  if (ret == -1) ans[t][m] = -1; else ans[t][m] = a[t] + ret;
  return ans[t][m];
}
int main()
{
  cin >> n, vis[1][1] = true;
  for (int i = 2; i <= n; ++i) cin >> a[i];
  for (int i = 2; i <= n; ++i) to[i][0] = i - a[i], to[i][1] = i + a[i];
  for (int i = 2; i <= n; ++i) if (!ans[i][0]) dfs(i, 0);
  for (int i = 1; i < n; ++i)
    if (ans[i + 1][0] == -1) cout << -1 << endl;
    else cout << i + ans[i + 1][0] << endl;
  return 0;
}