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;

}