Codeforces 1142B Lynyrd Skynyrd

---恢复内容开始---

题意：给你一个排列p和数组a，有t组询问，每次询问一个区间的子序列中是否有p的一个循环排列。

思路：以p = [3, 1, 2]举例，我们扫描数组b，假设当前数字是1,那么我们找前面离现在最近的3的位置，然后连一条边。为什么只连最近的呢？比如[3,3,1,2]这种情况，1只需要和第二个3连就行了，因为连第一个3的这种情况已经被连第二个3的这种情况包含了。那么对于每个点，我们可以找到通过连的边走n - 1次所到的点，所有包含这个区间的询问区间都有一个合法的循环排列。但是直接暴力找n - 1次到的点会被卡成O(n^2)的，我们可以用倍增优化这个过程。之后，对于每个点，我们只需记录在它前面的点中满足走n - 1次的点中最大的那一个就行了，因为这样相当于对于每个点，尽力压缩合法的区间。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 200010;

int f[maxn][20], pre[maxn], a[maxn], b[maxn], last[maxn], p[maxn], res[maxn];

int n, m, T, t;

int solve(int x) {

	int now = n - 1, ans = x;

	for (int i = t; i >= 0; i--) {

		if(p[i] <= now) {

			ans = f[ans][i];

			now -= p[i];

		}

	}

	return ans;

}

int main() {

	int l, r;

	scanf("%d%d%d", &n, &m, &T);

	t = (int)(log(n) / log(2)) + 1;

	p[0] = 1;

	for (int i = 1; i <= t;i++) {

		p[i] = p[i - 1] * 2;

	}

	for (int i = 1; i <= n; i++) {

		scanf("%d", &a[i]);

	}

	for (int i = 2; i <= n; i++) {

		pre[a[i]] = a[i - 1];

	}

	pre[a[1]] = a[n];

	for (int i = 1; i <= m; i++) {

		scanf("%d", &b[i]);

		f[i][0] = last[pre[b[i]]];

		for (int j = 1; j <= t; j++) {

			f[i][j] = f[f[i][j - 1]][j - 1];

		}

		last[b[i]] = i;

	}

	int pos;

	for (int i = 1; i <= m; i++) {

		pos = solve(i);

		res[i] = max(res[i - 1], pos);

	}

	while(T--) {

		scanf("%d%d", &l, &r);

		if(res[r] >= l) printf("1");

		else printf("0");

	}

}

---恢复内容结束---

巴特西

Codeforces 1142B Lynyrd Skynyrd

最新文章

热门文章