526互联

Educational Codeforces Round 94 (Rated for Div. 2) D. Zigzags 题解

发布时间 2023-11-15 21:36:07作者: DanRan02

题意

给你一个数组 \(a1,a2…an\) 请计算有多少个四元组 \((i,j,k,l)\) 符合以下条件:

  1. \(1 <= i < j < k < l <= n\)
  2. \(a_i=a_k \ \&\&\ a_j=a_l\)

\(4<=n<=3000,1<=a_i<=n\)

\(input\)

2
5
2 2 2 2 2
6
1 3 3 1 2 3

\(output\)

5
2

思路

问题可以转化为：当 \(i<j<k<l\) 时，有多少组 \((a_i,a_j)=(a_k,a_l)\) 关系？
具体实现：枚举 \(j\) ，从后往前枚举，并且每次算出后方有多少对 \((a_k,a_l)\) ，统计起来，再在数组开头到 \(j\) 的地方枚举 \(i\) ，看目前存在的可能成立的数对有多少。
具体表现为：\((a_i,a_j)\) 可以表示为 \(a_i * n + a_j\) （\(a_i\) 和 \(a_j\) 是在 \(n\) 进制下的两位数位）。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define flase false
#define ture true
#define ft first
#define sd second
#define int long long
#define startt cout<<"----------start----------\n";
#define endd cout<<"-----------end-----------\n";
#define No cout<<"No\n"
#define Yes cout<<"Yes\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 200010;
const int M = N * 2;
const int mod = 1e9 + 7;
const double Pi = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679;

template <typename T>
T read() {
	T sum = 0, fl = 1;
	int ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>
void print(T x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

vector<int> a;
int n, m, k;

//Let's BEGIN!!!==============================================================

void solve() {

	cin >> n;

	a = vector<int> (n);

	for (auto &x : a) {
		cin >> x;
	}

	vector<int> cnt(n * (n + 1) + 1, 0);
	int tot = 0;

	for (int j = n - 1; j >= 0; --j) {

		int k = j + 1;

		for (int l = k + 1; l < n; ++ l) {
			cnt[a[k] * n + a[l]] += 1;
		}

		for (int i = 0; i < j; ++ i) {
			tot += cnt[a[i] * n + a[j]];
		}
	}

	cout << tot << '\n';

}

signed main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}