题解：P13788 「CZOI-R6」Permutation and Subsequence

看了一下别人的代码，貌似没有和我一样的？

题目意思比较明了，这里不在复述。

思路

首先我们观察题目，发现

a

和

b

数组都是一个排列，这意味着每个数在

b

中都有唯一的位置。

不难想到我们可以用一个

c

数组，来存储每个

a_i

在

b

数组中的位置。

那么，问题就转化成了：统计

c

数组中所有递增的非空连续子段的数量。

这是因为要使得

a

的连续子段是

b

的子序列，当且仅当对应的

c

的子段是递增的。

最后，要注意的是爆int。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[1000010],b[1000010],c[1000010],d[1000010],ans,cnt = 1;
signed main(){
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	for (int i = 1;i <= n;i++) cin >> b[i],c[b[i]] = i;
	for (int i = 1;i <= n;i++) d[i] = c[a[i]];
	for (int i = 1;i <= n;i++){
		if (i > 1 && d[i] <= d[i - 1]) cnt = i;
		ans += i - cnt + 1;
	}
	cout << ans << endl;
}

题解：P13788 「CZOI-R6」Permutation and Subsequence

文章操作

思路

代码

相关推荐

评论

题解：P13788 「CZOI-R6」Permutation and Subsequence