20231017模拟赛题解

AisDaeun 8 2023-10-29

今日笑点:山东省实验中学某同学在比赛结束时开始了比赛!

T1 你比较牛

考虑使用归并排序,求出逆序对的个数。

#include <bits/stdc++.h>
#define int long long
#define _for(i, a, b) for (int i = (a); i <= (b); ++i)
#define __for(i, a, b) for (int i = (a); i >= (b); --i)
int read() {
	int x = 0; bool fl(0); char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) fl = ch == '-';
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	return fl ? -x : x;
}
const int N = 5e5 + 10;
int a[N], b[N], c[N], cnt;
template <typename F>
void merge_sort(int a[], int l, int mid, int r, F const &f) {
	if (l >= r) return;
	merge_sort(a, l, (l + mid) >> 1, mid, f);
	merge_sort(a, mid + 1, (mid + 1 + r) >> 1, r, f);
	int i = l, j = mid + 1;
	_for(k, l, r) 
		if (j > r || (i <= mid && f(a[i], a[j]))) c[k] = a[i++];
		else c[k] = a[j++], cnt += mid - i + 1;
	_for(k, l, r) a[k] = c[k];
}
signed main() {
	std::ios::sync_with_stdio(false);
	int n = read(), l = read(), r = read();
	_for(i, 1, n) {
		int x = read();
		a[i] = a[i - 1] + x - l;
		b[i] = b[i - 1] + x - r;
	}
	merge_sort(b, 0, n >> 1, n, [] (int x, int y) {return x < y;});
	int ans = cnt; cnt = 0;
	merge_sort(a, 0, n >> 1, n, [] (int x, int y) {return x <= y;});
	int base = (n * (n + 1)) >> 1; ans -= cnt;
	int p = std::__gcd(ans, base);
	ans /= p, base /= p;
	if (ans == 0) std::cout << 0 << '\n';
	else if (base == 1) std::cout << ans << '\n';
	else std::cout << ans << '/' << base << '\n';
	return 0;
}

T2 编花篮

后面忘了

T3 平均数

后面忘了

T4 冲向食堂

后面忘了