|
题目链接：https://atcoder.jp/contests/arc133/tasks/arc133_b
题意：给定两个1到n的排列P、Q。从P、Q中找到一个最长的子序列，满足以下条件：
1、P中的子序列和Q中的子序列长度相同，设为k。
2、a、b分别是P、Q的子序列，
a
=
(
a
1
,
a
2
,
.
.
.
,
a
k
)
,
b
=
(
b
1
,
b
2
,
.
.
.
,
b
k
)
a=(a_1,a_2,...,a_k), b=(b_1,b_2,...,b_k)
a=(a1?,a2?,...,ak?),b=(b1?,b2?,...,bk?)，对于
1
<
=
i
<
=
k
,
1<=i<=k,
1<=i<=k,都有
b
i
b_i
bi?是
a
i
a_i
ai?的倍数。
思路：由于
b
i
b_i
bi?是
a
i
a_i
ai?的倍数，
∑
1
<
=
i
<
=
N
N
/
i
\sum_{1<=i<=N}N/i
∑1<=i<=N?N/i，所以可以枚举出所有符合要求的
(
i
,
j
)
(i,j)
(i,j)，复杂度为
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)
然后按照
(
i
,
?
j
)
(i, -j)
(i,?j)排序，这样可以避免选择重复的
i
i
i，求一遍LIS即可。
例如
1 2 3 4 5
5 4 3 2 1
其所有符合要求的
(
i
,
j
)
(i,j)
(i,j)有
(
1
,
1
)
,
(
1
,
2
)
,
(
1
,
3
)
,
(
1
,
4
)
,
(
1
,
5
)
,
(
2
,
2
)
,
(
2
,
4
)
,
(
3
,
3
)
,
(
4
,
2
)
,
(
5
,
1
)
(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,4),(3,3),(4,2),(5,1)
(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,4),(3,3),(4,2),(5,1)共10个，需要从中找到最长的序列，满足
i
1
<
i
2
<
.
.
.
<
i
k
,
j
1
<
j
2
<
.
.
.
<
j
k
i_1<i_2<...<i_k,j_1<j_2<...<j_k
i1?<i2?<...<ik?,j1?<j2?<...<jk?
将其排序后为
(
1
,
5
)
,
(
1
,
4
)
,
(
1
,
3
)
,
(
1
,
2
)
,
(
1
,
1
)
,
(
2
,
4
)
,
(
2
,
2
)
,
(
3
,
3
)
,
(
4
,
2
)
,
(
5
,
1
)
(1,5),(1,4),(1,3),(1,2),(1,1),(2,4),(2,2),(3,3),(4,2),(5,1)
(1,5),(1,4),(1,3),(1,2),(1,1),(2,4),(2,2),(3,3),(4,2),(5,1)，通过二分来求LIS。
代码如下
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
const int mod = 998244353;
int a[maxn];
int b[maxn];
int pos[maxn];
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i) scanf("%d", a + i);
for(int i = 0; i < n; ++i) {
scanf("%d", b + i);
pos[b[i]] = i;
}
vector<int> dp(n, n+1);
for(int i = 0; i < n; ++i){
vector<int> t;
for(int j = a[i]; j <= n; j += a[i]){
t.push_back(pos[j]);
}
sort(t.rbegin(), t.rend());
for(int j = 0; j < t.size(); ++j){
*lower_bound(dp.begin(), dp.end(), t[j]) = t[j];
}
}
for(int i = n-1; i >= 0; --i){
if(dp[i] != n + 1) {
printf("%d\n", i+1);
return 0;
}
}
}
|