CF1569 - Educational Codeforces Round 113 (Rated for Div. 2)

link：Educational Codeforces Round 113 (Rated for Div. 2)

C - Jury Meeting

题意

（把原题魔改了一下，感觉好理解点~）

给出 $n$ 个玩家，每个玩家手上有 $a_i$ 个糖果，你可以改变玩家的初始排列顺序，确定排列顺序后，每一轮会从第一个玩家到第n个手上还有糖果的玩家手上拿走一个糖果，求有多少种排列方案，使得不会连续两次从同一个玩家手上拿走糖果。

数据范围：$2\leqslant n\leqslant 2\times 10^5$。

思路

先分情况讨论下，可以发现这与最大糖果数目和次大糖果数目有关。

设最大糖果数目为 $mx_1$ 持有人数为 $b_1$ 个，次大糖果数目为 $mx_2$ 持有人数为 $b_2$ 个，则

• 当 $b_1 \geqslant 2$ 时，答案就是 $n!$，因为随意排列，都能保证最后一定会剩余至少两个人仍有糖果，那么就不会连续从一个人手上拿走两次糖果。

• 当 $mx_1 - mx_2 \geqslant 2, b_1 = 1$ 时，答案是 $0$，无解，因为最后一定会真剩下一个人手上拿着至少两个糖果，那么就会从他手上连续取走两次糖果。

• 当 $mx_1 - mx_2 = 1, b_1 = 1$ 时，答案是 $n!\cdot \frac{b_2}{b_2+1}$，因为我们可以先将糖果数为 $mx_2$ 的人进行全排列 $b_2!$，然后将那一个糖果数为 $mx_1$ 的人插入到这 $b_2$ 个人的左边也就是有 $b_2$ 个位置可以放，最后再将剩余的 $n-1-b_2$ 个人随意插入到这 $1+b_2$ 之间就行了，方案数为 $A_{n}^{n-1-b_2}$。
  所以全部乘起来再化简一下，就是 $b_2!\cdot b_2\cdot A_{n}^{n-1-b_2} = n!\cdot \frac{b_2}{b_2+1}$。

时间复杂度 $O(n)$。

点击显/隐代码

//比赛时没有化简就有点复杂了.
#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 2e5 + 10;
int ksm(int a, int b) {int ret = 1; while (b) {if (b & 1) ret = ret * a % P; a = a * a % P; b >>= 1;} return ret;}
int jie[N], nijie[N];
void pre(int n) {
	jie[0] = 1;
	for (int i = 1; i <= n; i++) jie[i] = jie[i-1] * i % P;
	nijie[n] = ksm(jie[n], P-2);
	for (int i = n-1; i >= 0; i--) nijie[i] = nijie[i+1] * (i+1) % P;
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	pre(2e5);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vi a(n);
		int mx1 = 0, mx2 = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			if (a[i] > mx1) {
				mx2 = mx1;
				mx1 = a[i];
			} else if (a[i] > mx2) {
				mx2 = a[i];
			}
		}
		if (mx1 == mx2) {
			cout << jie[n] << '\n';
		} else if (mx1 - mx2 >= 2) {
			cout << 0 << '\n';
		} else {
			int cnt = 0;
			for (int i = 0; i < n; i++) if (a[i] == mx2) cnt++;
			cout << jie[cnt] * cnt % P * jie[n] % P * nijie[cnt+1] % P << '\n';
		}
	}
	return 0;
}

D - Inconvenient Pairs

题意

给出 $n, m, k$，分别给出 $n$ 条竖直线，$m$ 条横直线，和 $k$ 个在线上的点。（当然包括线的交点）

求有多少对点的线上距离（指必须通过已有直线的最短距离）小于曼哈顿距离（指 $|x_1-x_2|+|y_1-y_2|$）。

注：$(x, y)$ 和 $(y, x)$ 算一个点对，保证给出的直线和竖线坐标都在 $[0, 10^6]$ 之间，且保证各有两个坐标为 $0,10^6$ 的直线和竖线（也就是整个图形是被一个大的正方形包围起来了）。

数据范围：$2\leqslant n, m\leqslant 2\times 10^5,2\leqslant k\leqslant 3\times 10^5$。

思路

比赛时，已经想出来解决方法了，但苦于实现过于复杂，下面代码参考题解方法用较为简短的实现方法。

不难发现，满足题意的点对一定是在两条不同的竖直线或者横直线上的，下面只考虑在不同的竖直线上的情况，横直线可以类比讨论。

如果两个不同竖直线上的点，它们之间又没有横直线，则它们的线上距离一定小于曼哈顿距离，可以画图理解。

有了上述判断，接下来就是实现，为了不重复计算，我们考虑先将所有点按照横坐标排序，我们先利用双指针的思路，将所有相同横坐标的点包围在双指针内。

那么这些有着相同横坐标的点之间肯定不满足题意，因为他们在同一条竖线上面。

在枚举点的过程中，每次枚举完的点（不在交点上面），都要存储的离它最近的上侧横线上（用于记录该横线到下侧一条横线中间已经枚举过的点的个数）。

那么只需要判断它们和之前的点的关系，对于每一个点按照纵坐标为键值 lower_bound 求出大于等于它的一条横线，如果该横线坐标和当前点纵坐标相等，说明该点在横竖线的交点上，则它一定不能满足题意，跳过。否则将之前存储在该横线上的点的个数加到答案上即可，因为存储在该直线上的点一定和该点之间没有横直线了。将双指针内的所有点求出对答案的贡献后，存储到理它最近的上侧的横线上。

最后将横纵交换，再次求解即可。

时间复杂度 $O(n + m + k(\log n + \log m + \log k))$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m, k, ans = 0;
		cin >> n >> m >> k;
		vi X(n), Y(m);
		vp pt(k);
		for (int i = 0; i < n; i++) cin >> X[i];
		for (int i = 0; i < m; i++) cin >> Y[i];
		for (int i = 0; i < k; i++) cin >> pt[i].first >> pt[i].second;
		for (int _i = 0; _i < 2; _i++) {
			sort(pt.begin(), pt.end());
			vi cntY(m);
			for (int u = 0, v; u < k; u = v) {
				vi up;
				v = u;
				while (v < k && pt[u].first == pt[v].first) v++;
				for (int i = u; i < v; i++) {
					int p = lower_bound(Y.begin(), Y.end(), pt[i].second) - Y.begin();
					if (Y[p] == pt[i].second) continue;
					ans += cntY[p];
					up.pb(p);
				}
				for (auto i : up) cntY[i]++;
			}
			swap(n, m);
			for (auto &i : pt) swap(i.first, i.second);
			swap(X, Y);
		}
		cout << ans << '\n';
	}
	return 0;
}