Codeforces 1175F（哈希后暴力）

要点

官解使用的哈希，给每个数一个二维键值，这样每个排列就有唯一的键值，再预求一下所给数列的前缀键值，暴力寻找有多少个答案即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <random>

#include <ctime>

using namespace std;

typedef long long ll;

typedef pair<ll, ll> pll;

const int maxn = 3e5 + 5;

int n, a[maxn], ans;

pll hsh[maxn], jc[maxn], sum[maxn];

mt19937 rnd(time(NULL));

pll operator ^ (pll a, pll b) {

	return {a.first ^ b.first, a.second ^ b.second};

}

int calc(int pos) {

	int res = 0, len = 0;

	for (int r = pos + 1; r <= n && a[r] != 1; r++) {

		len = max(len, a[r]);

		if (r - len >= pos)	break;//肯定是重复的

		if (r - len >= 0 && (sum[r] ^ sum[r - len]) == jc[len])

			res++;

	}

	return res;

}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {

		scanf("%d", &a[i]);

	}

	for (int i = 1; i <= n; i++) {//为每个数i弄一个键值

		hsh[i].first = rnd();

		hsh[i].second = rnd();

		jc[i] = hsh[i];

		jc[i] = jc[i] ^ jc[i - 1];//排列1~i的键值

	}

	for (int it = 0; it < 2; it++) {//第一轮算最大值在右边

		for (int i = 1; i <= n; i++) {

			sum[i] = hsh[a[i]];

			sum[i] = sum[i] ^ sum[i - 1];//数列的前缀

		}

		for (int i = 1; i <= n; i++)

			if (a[i] == 1)

				ans += calc(i) + (it == 0);

		reverse(a + 1, a + 1 + n);//下一轮算最大值在左边的

	}

	return !printf("%d\n", ans);

}

巴特西

Codeforces 1175F（哈希后暴力）

要点

最新文章

热门文章