2023-08-13 16:36 厦门大学 计算机类
关注
0813科大讯飞笔试 第三题 个人思路
思路：
其实就是统计两个排列之间相同的子数组个数，用总的子数组个数减去重复的即可。
我们把第一个排列当作是基准数列，意思是第一个序列是我们规定的从小到大的排序。
根据第一个排列处理第二个排列，得到新的第二个排列，如果第二个排列的某个区间是1，2，3..这样递增的，那么这个区间的子数组就是重复的，减去即可。
时间复杂度：O(n)
代码：
```
#include
using namespace std;
#define int long long
const int N = 2e5+9;
int a[N],b[N];
int pos[N],c[N];
signed main() {
int n;
cin>>n;
for(int i=1; i<=n; ++i) cin>>a[i],pos[a[i]]=i;
for(int i=1; i<=n; ++i) cin>>b[i],b[i]=pos[b[i]];
int ans=n*(n+1); //如果
for(int i=1; i<=n; ++i){
int j=i+1;
while(j<=n){
if(b[j-1]!=b[j]-1) break;
c[j++]=1;
}
//i~j-1就是递增的 ,递增的就会重复
int nn = j-i;
ans-=nn*(nn+1)/2;
i=j-1;
//cout<
cout<
}
/*
3
1 2 3
2 3 1
3
1 2 3
1 3 2
3
2 3 1
1 2 3
*/
```
其实就是统计两个排列之间相同的子数组个数，用总的子数组个数减去重复的即可。
我们把第一个排列当作是基准数列，意思是第一个序列是我们规定的从小到大的排序。
根据第一个排列处理第二个排列，得到新的第二个排列，如果第二个排列的某个区间是1，2，3..这样递增的，那么这个区间的子数组就是重复的，减去即可。
时间复杂度：O(n)
代码：
```
#include
using namespace std;
#define int long long
const int N = 2e5+9;
int a[N],b[N];
int pos[N],c[N];
signed main() {
int n;
cin>>n;
for(int i=1; i<=n; ++i) cin>>a[i],pos[a[i]]=i;
for(int i=1; i<=n; ++i) cin>>b[i],b[i]=pos[b[i]];
int ans=n*(n+1); //如果
for(int i=1; i<=n; ++i){
int j=i+1;
while(j<=n){
if(b[j-1]!=b[j]-1) break;
c[j++]=1;
}
//i~j-1就是递增的 ,递增的就会重复
int nn = j-i;
ans-=nn*(nn+1)/2;
i=j-1;
//cout<
cout<
}
/*
3
1 2 3
2 3 1
3
1 2 3
1 3 2
3
2 3 1
1 2 3
*/
```
全部评论
牛客63557255号
门头沟学院 计算机类
你咋还能拍照咧
分享
牛客977694570号
门头沟学院 电子信息类
100%吗？卡超时?
分享
联易融
校招火热招聘中
官网直投
xxxxxl昕
中国科学院大学 计算机类
用的排列组合再加全排列，100%
分享
相关推荐
投递华为等公司10个岗位 > 点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发