LOJ#2427. 「POI2010」珍珠项链 Beads

题目地址

题目链接

题解

不会算复杂度真是致命，暴力枚举k每次计算是n/2+n/3+n/4+...+1的，用调和级数算是\(O(nlogn)\)的...

如果写哈希表的话能够\(O(nlogn)\)，或者直接拿个set存就\(O(nlognlogn)\)。

进制要选好，233不能过，2333过的点会多一点，然后选13131才过了

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
typedef unsigned long long ull;
const int N = 200010;
const ull base = 13131;
using namespace std;

int Ans, n, a[N], ans[N], cnt = 0;
ull h1[N], h2[N], p[N];
set<ull> st;

ull cal1(int l, int r) { return h1[r] - h1[l - 1] * p[r - l + 1]; }

ull cal2(int l, int r) { return h2[l] - h2[r + 1] * p[r - l + 1]; }

int ins(int x) {
    st.clear();
    for(int l = 1; l + x - 1 <= n; l += x) {
        int r = l + x - 1;
        ull ha = min(cal1(l, r), cal2(l, r));
        st.insert(ha);
    }
    return (int)st.size();
}

int main() {
    scanf("%d", &n); p[0] = 1;
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) h1[i] = h1[i - 1] * base + a[i], p[i] = p[i - 1] * base;
    for(int i = n; i; i--) h2[i] = h2[i + 1] * base + a[i];
    for(int i = 1; i <= n; ++i) {
        int num = ins(i);
        if(num > Ans) { Ans = num; cnt = 0; }
        if(num == Ans) ans[++cnt] = i;
    }
    printf("%d %d\n", Ans, cnt);
    for(int i = 1; i <= cnt; ++i) printf("%d ", ans[i]);
    return 0;
}