当前位置:网站首页>C. Rotation Matching
C. Rotation Matching
2022-08-10 20:44:00 【秦小咩】
C. Rotation Matching
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
After the mysterious disappearance of Ashish, his two favourite disciples Ishika and Hriday, were each left with one half of a secret message. These messages can each be represented by a permutation of size nn. Let's call them aa and bb.
Note that a permutation of nn elements is a sequence of numbers a1,a2,…,ana1,a2,…,an, in which every number from 11 to nn appears exactly once.
The message can be decoded by an arrangement of sequence aa and bb, such that the number of matching pairs of elements between them is maximum. A pair of elements aiai and bjbj is said to match if:
- i=ji=j, that is, they are at the same index.
- ai=bjai=bj
His two disciples are allowed to perform the following operation any number of times:
- choose a number kk and cyclically shift one of the permutations to the left or right kk times.
A single cyclic shift to the left on any permutation cc is an operation that sets c1:=c2,c2:=c3,…,cn:=c1c1:=c2,c2:=c3,…,cn:=c1 simultaneously. Likewise, a single cyclic shift to the right on any permutation cc is an operation that sets c1:=cn,c2:=c1,…,cn:=cn−1c1:=cn,c2:=c1,…,cn:=cn−1 simultaneously.
Help Ishika and Hriday find the maximum number of pairs of elements that match after performing the operation any (possibly zero) number of times.
Input
The first line of the input contains a single integer nn (1≤n≤2⋅105)(1≤n≤2⋅105) — the size of the arrays.
The second line contains nn integers a1a1, a2a2, ..., anan (1≤ai≤n)(1≤ai≤n) — the elements of the first permutation.
The third line contains nn integers b1b1, b2b2, ..., bnbn (1≤bi≤n)(1≤bi≤n) — the elements of the second permutation.
Output
Print the maximum number of matching pairs of elements after performing the above operations some (possibly zero) times.
Examples
input
Copy
5 1 2 3 4 5 2 3 4 5 1
output
Copy
5
input
Copy
5 5 4 3 2 1 1 2 3 4 5
output
Copy
1
input
Copy
4 1 3 2 4 4 2 3 1
output
Copy
2
Note
For the first case: bb can be shifted to the right by k=1k=1. The resulting permutations will be {1,2,3,4,5}{1,2,3,4,5} and {1,2,3,4,5}{1,2,3,4,5}.
For the second case: The operation is not required. For all possible rotations of aa and bb, the number of matching pairs won't exceed 11.
For the third case: bb can be shifted to the left by k=1k=1. The resulting permutations will be {1,3,2,4}{1,3,2,4} and {2,3,1,4}{2,3,1,4}. Positions 22 and 44 have matching pairs of elements. For all possible rotations of aa and bb, the number of matching pairs won't exceed 22.
=========================================================================
只对b进行平移是可以的,只对b进行右移也是可以的,那么就统计出来每个数字偏移的距离即可
取其最大值
#include<iostream>
#include<cstdio>
#include<cstring>
# include<iomanip>
#include<algorithm>
#define mo 998244353;
using namespace std;
typedef long long int ll;
int pre[200000+10];
int now[200000+10];
int cnt[200000+10];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
pre[x]=i;
}
for(int i=1;i<=n;i++)
{
cin>>now[i];
if(i-pre[now[i]]>=0)
{
cnt[i-pre[now[i]]]++;
}
else
{
cnt[i-pre[now[i]]+n]++;
}
}
int ans=0;
for(int i=0;i<=n;i++)
{
ans=max(ans,cnt[i]);
}
cout<<ans;
return 0;
}
边栏推荐
- The most complete GIS related software in history (CAD, FME, ArcGIS, ArcGISPro)
- 双 TL431 级联振荡器
- 金鱼哥RHCA回忆录:CL210OpenStack操作的故障排除--章节实验
- Single-click to cancel the function
- UE4 - 河流流体插件Fluid Flux
- paddle 35 paddledetection保存训练过程中的log信息
- [Golang]用反射让你的代码变优美
- Kubernetes 笔记 / 入门 / 生产环境 / 用部署工具安装 Kubernetes / 用 kubeadm 启动集群 / 用 kubeadm 创建集群
- 【图像分类】2017-MobileNetV1 CVPR
- Knowledge map Knowledge Graph
猜你喜欢
mysql性能监控与执行计划
XML小讲
【图像分类】2019-MoblieNetV3 ICCV
npm WARN config global `--global`, `--local` are deprecated. Use `--location=global` instead.
数据标注太昂贵?这个方法可以用有限的数据训练模型实现基于文本的ReID!
详叙c中的分支与循环
论文解读(g-U-Nets)《Graph U-Nets》
leetcode:45. 跳跃游戏II
Transferrin-modified vincristine-tetrandrine liposomes | transferrin-modified co-loaded paclitaxel and genistein liposomes (reagents)
C语言系列——猜名次、猜凶手、打印杨辉三角
随机推荐
A fullGC problem troubleshooting caused by groovy
JS中的filter、map、reduce
关于 NFT 版权保护的争议
[Golang]用反射让你的代码变优美
壁仞推出全球最大算力芯片,号称以7nm超越英伟达4nm最新GPU
Transferrin-modified osthole long-circulating liposomes/PEG-PLGA nanoparticles loaded with notoginsenoside R1 ([email prot
Tf ferritin particles contain cisplatin / oxaliplatin / doxorubicin / methotrexate MTX / paclitaxel PTX and other drugs
【golang map】 深入了解map内部存储协议
Transferrin-modified vincristine-tetrandrine liposomes | transferrin-modified co-loaded paclitaxel and genistein liposomes (reagents)
Apache DolphinScheduler 3.0.0 正式版发布!
第四届红帽杯网络安全大赛
单选点击可取消功能
[mysql] 深入分析MySQL版本控制MVCC规则
The 2021 ICPC Asia Shanghai Regional Programming Contest D、E
睡前故事|用Bitmap与AST做一个配置化时长系统
Apple Font Lookup
ES6中的for...in/of的使用
每日一R「03」Borrow 语义与引用
MySQL数据库的主从复制部署详解
2021年中国工业互联网安全大赛(福建省选拔赛) 暨首届福建省工业互联网创新大赛