题解：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:

CPP

#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;
}

题解：AT_nyc2015_4 ジャンプ

文章操作

观察性质

考虑优化

AC code:

相关推荐

评论

题解：AT_nyc2015_4 ジャンプ