【codeforces|Codeforces Round #648 (Div. 2) C. Rotation Matching(思维)】题目传送
题意:
给你俩个大小为n的排列，现在你可以任意的选择一个排列，使其全部元素同时向右或者向左平移k(k任选)个单位，问最多能有多少个:当i == j(俩个排列中的位置下标一样时)，ai == bj(相同位置的元素值相同)。
思路:
既然是平移，那么向右或者向左平移的结果是一样的，那么我们何不枚举一下，枚举当前向右平移一个单位，俩个单位，直到n个单位时，那种情况最多。但是这样一来时间复杂度就高了，所以我们要转化一下，其实我们只要记录第一个排列中，的1的位置和第二个排列中1的位置的距离之差(向右平移的距离)，然后依次记录下去，我们看看在相同距离下，谁的次数最多就可以了。
//看代码易懂些哦
AC代码
#include
inline long long read(){char c = getchar();
long long x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';
c = getchar();
}
return x*s;
}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 2e5 + 10;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const unsigned long long mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
typedef pair piil;
int a[N],b[N],vis[N];
void Put(int n,int ans)
{
for(int i = 1,c;
i <= n;
i++)
{
cin >> c;
ans ? a[c] = i : b[c] = i;
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,Max = 0;
cin >> n;
Put(n,1);
Put(n,0);
//输入俩个排列
for(int i = 1;
i <= n;
i++)
{
int x = 0;
a[i] > b[i] ? x = n-(a[i]-b[i]) : x = b[i]-a[i];
//向右平移的距离
vis[x]++;
//记录该距离下，有多少个数相等
Max = max(vis[x],Max);
//取最多的次数
}
cout << Max << endl;
}
推荐阅读
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element