Cycle Correspondence (USACO Silver 2023 December)

Cycle Correspondence (USACO Silver 2024 January)

能重合的点的数量，就是两部分，一是在环里的点，二是环外的点。环外的点简单，就是看哪些点在两个列表里都没有出现过。环里的点可能最大重合数，可以通过枚举环的起点，然后计算环里的点的最大重合数。

这个可以通过统计每个相同数字出现的位置差来做，然后看最高频率的位置差的频就是答案。
每个数字的位置差，因为旋转对称，一定可以在0 ~ N-1之间取得。
要考虑相同方向，和不同方向两种情况，后者就是把其中一个列表反转一下，然后再次就可以。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, k;
int a[500005], b[500005], seen[500005];
int pos[500005];    // 1-based
int ans;
 
int solve() {
    vector<int> v;
    v.resize(k+1, 0);
    for (int i = 1; i <= k; i++) {
        if (pos[b[i]] == 0) continue;
        int d = i - pos[b[i]];
        if (d < 0) d += k;
        v[d]++;
    }
    return *max_element(v.begin(), v.end());
}
 
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= k; i++) {
        scanf("%d", &a[i]);
        seen[a[i]] = 1;
    }
    for (int i = 1; i <= k; i++) {
        scanf("%d", &b[i]);
        seen[b[i]] = 1;
    }
    for (int i = 1; i <= n; i++)            // barns outside the cycle
        if (!seen[i]) ans++;
 
    for (int i = 1; i <= k; i++) 
        pos[a[i]] = i;
    
    int ans0 = solve();
    reverse(b+1, b+k+1);
    int ans1 = solve();
 
    printf("%d\n", ans + max(ans0, ans1));
 
    return 0;
}