题解：AT_nyc2015_4 ジャンプ

· · 题解

观察性质

通过观察，发现做两次翻转操作之后等于一次平移。

翻转操作：x'=−x+b

平移操作：x'=x+b

两次操作：x'=2a_i-(2a_j-x) 进行了一次 x'=x+2(a_i-a_j) 的平移。所以翻转的翻转是一次平移。

如果答案是偶数步，将两步看成一步，这样可以做到预处理一个平移数组。如果答案是奇数步，对于每个询问枚举第一步。

预处理变成了一个完全背包或 BFS 的问题。

但我们发现这样复杂度还是多了一个 n。

考虑优化

其实两步看一步没有必要。

偶数步操作就是一个平移，预处理出这个平移操作，看成一个简单的 BFS 问题。异或是一个交替取正/负数的完全背包问题。

奇数步跟上一个算法一样可以枚举第一步。

复杂度 O(n|x_i|+q)

AC code:

#include <bits/stdc++.h>
#define File(x, y) freopen(x".in", "r", stdin), freopen(y".out", "w", stdout)
#define REP(i, a, b) for (int i = a; i <= b; i ++)
#define PER(i, a, b) for (int i = a; i >= b; i --)
using namespace std;
const int N = 510, M = 3e4 + 10;
int a[N], d[M << 1], h[M << 1];
int len, tot = 0;
int n, q;
void upd(int &a, int b) { 
    if (b == -1) return;
    a = (a == -1 || a > b) ? b : a;
}

void init() {
    queue<pair<int, int>> q;
    memset(d, -1, sizeof d), memset(h, -1, sizeof h);
    d[M] = 0;
    q.push({M, 0});
    while (!q.empty()) {
        auto now = q.front(); q.pop();
        int x = now.first, y = now.second;
        if (!y) {
            REP(i, 1, n) if (x + a[i] < 2 * M && h[x + a[i]] == -1) {
                h[x + a[i]] = d[x] + 1;
                q.push({x + a[i], 1});
            }
        }
        else {
            REP(i, 1, n) if (x - a[i] >= 0 && d[x - a[i]] == -1) {
                d[x - a[i]] = h[x] + 1;
                q.push({x - a[i], 0});
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    REP(i, 1, n) cin >> a[i];
    init();
    cin >> q;
    while (q --) {
        int s, t; cin >> s >> t; if ((s + t) & 1) {
            cout << -1 << '\n';
            continue;
        }
        int ans = d[(t - s) / 2 + M];
        REP(i, 1, n) {
            int x = a[i] * 2 - s;
            if (~ d[(t - x) / 2 + M]) upd(ans, d[(t - x) / 2 + M] + 1);
        }
        cout << ans << '\n';    
    }
    return 0;
}