Beads

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2482 字
枚举块长用正反哈希去重统计不同串
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1461
// 题意：给长度 n 的颜色序列，对每个块长 k 切成若干长为 k 的块（余料丢弃），正反视为同一种，求不同块数最多的 k 及个数。
// 思路：正反两个方向预处理滚动哈希，枚举 k，把每块的正向哈希与反向哈希取较小者作代表值，排序去重计数。
// 复杂度：O(n·log n·H(n)) 时间 / O(n) 空间
// 易错点：反向块必须用反串的哈希区间，不能只靠单值异或；代表值取 min(正,反) 才能把互逆的两块并成一类。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B1=911382323ull;
const ull B2=972663749ull;
struct Hv{
    ull a,b;
    bool operator<(const Hv&o)const{
        if(a!=o.a) return a<o.a;
        return b<o.b;
    }
    bool operator==(const Hv&o)const{
        return a==o.a&&b==o.b;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin>>n)) return 0;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        if(!(cin>>a[i])) return 0;
    }
    vector<ull> h1(n+1,0),h2(n+1,0),g1(n+1,0),g2(n+1,0),p1(n+1,1),p2(n+1,1);
    for(int i=0;i<n;i++){
        ull v=(ull)a[i]+1;
        h1[i+1]=h1[i]*B1+v;
        h2[i+1]=h2[i]*B2+v;
        p1[i+1]=p1[i]*B1;
        p2[i+1]=p2[i]*B2;
        ull w=(ull)a[n-1-i]+1;
        g1[i+1]=g1[i]*B1+w;
        g2[i+1]=g2[i]*B2+w;
    }
    auto f1=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return h1[r+1]-h1[l]*p1[r-l+1];
    };
    auto f2=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return h2[r+1]-h2[l]*p2[r-l+1];
    };
    auto r1=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return g1[r+1]-g1[l]*p1[r-l+1];
    };
    auto r2=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return g2[r+1]-g2[l]*p2[r-l+1];
    };
    int best=0;
    vector<int> ks;
    vector<Hv> cur;
    for(int k=1;k<=n;k++){
        int blocks=n/k;
        if(blocks<best) continue;
        cur.clear();
        cur.reserve(blocks);
        for(int i=0;i<blocks;i++){
            int l=i*k;
            int r=l+k-1;
            Hv fwd{f1(l,r),f2(l,r)};
            Hv rev{r1(n-1-r,n-1-l),r2(n-1-r,n-1-l)};
            if(rev<fwd) cur.push_back(rev);
            else cur.push_back(fwd);
        }
        sort(cur.begin(),cur.end());
        int d=0;
        for(int i=0;i<blocks;i++){
            if(i==0||!(cur[i]==cur[i-1])) d++;
        }
        if(d>best){
            best=d;
            ks.clear();
            ks.push_back(k);
        }else if(d==best){
            ks.push_back(k);
        }
    }
    cout<<best<<' '<<ks.size()<<'\n';
    for(int i=0;i<(int)ks.size();i++){
        if(i) cout<<' ';
        cout<<ks[i];
    }
    cout<<'\n';
    return 0;
}
Beads

正文

一本通·提高篇的其它内容
