mydcwfy's Blog

CF Round#775

Posted on
Symbols count in article: 3.6k Reading time ≈ 8 mins.

状态不错，F 只想得到线段树，思路还没清晰，就结束了……

比赛记录：ABCDE Accepted，Scores：6328，Rank #7，Rating 1663 -> 1962。

改题进度：ABCDE Accepted。

比赛传送门

A.

题意不描述了。

签到题，从左端点一直向右走，从右端点一直向左走，遇上了就是 0，否则答案就是两点距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	int i = 1;
	while (i <= n && a[i]) i ++;
	if (i > n) {
		puts("0");
		return;
	}
	int j = n;
	while (j && a[j]) j --;
	printf("%d\n", j - i + 2);
}

B.

题意：有 $n$ 个人传球，已知每个人传出的次数，可以拿到球后不传，问至少要多少个球。

考虑贪心，要满足传出次数最多的人，就让剩下的人都传给他，如果还不能满足，剩余的传出次数，每一个都要一个球。否则一个球就可以完成。

注意特判全是 0 的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	bool flag = 0;
	for (int i = 1; i <= n; ++ i) flag |= !!a[i];
	if (!flag) {
		puts("0");
		return;
	}
	LL sum = 0;
	for (int i = 1; i <= n; ++ i) sum += a[i];
	if ((LL(*std::max_element(a + 1, a + n + 1)) << 1) <= sum)
	{
		puts("1");
		return;
	}
	printf("%lld\n", 2LL * (*std::max_element(a + 1, a + n + 1)) - sum);
}

C.

题意：给出 $n\times m$ 的矩形，每个点有一个颜色，求所有颜色相同的点两两之间的曼哈顿距离和。$n\times m \leq 10^5,c_{i, j}\leq 10^5$。

也许我的做法劣一些，但是也不慢，多一只 $\log$。

考虑将所有颜色相同的点按 $x$ 排序，统计答案的时候，由 $y$ 的情况分为两种：$y \leq y_{now}, y > y_{now}$。分别用树状数组维护即可，时间复杂度 $O(nm\log m)$。

似乎可以直接拆贡献计算做到 $O(nm)$？没管。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct BIT {  } f, g, cnt;
int main()
{
	LL res = 0;
	for (int c = 1; c < N; ++ c)
	{
		for (auto p : al[c]) {
			res += (LL)cnt.ask(p.y) * (p.x + p.y) + f.ask(p.y);
			res += (LL)(cnt.ask(m) - cnt.ask(p.y)) * (p.x - p.y) + (g.ask(m) - g.ask(p.y));
			f.add(p.y, -p.x - p.y), g.add(p.y, p.y - p.x), cnt.add(p.y, 1);
		}
		for (auto p : al[c]) {
			f.add(p.y, p.x + p.y), g.add(p.y, p.x - p.y), cnt.add(p.y, -1);
		}
	}
}

D.

题意：判断一个集合是否满足 $\forall x, y\in S\land x\geq y, s.t. \left\lfloor\dfrac xy \right\rfloor \in S$。$|S|\leq 10^6, \forall x \in S, x\leq 10^6$。

暴力枚举显然是 $O(n ^ 2)$ 的。

我们可以考虑枚举 $x$ 和 $\left\lfloor\dfrac yx\right\rfloor = k$，如果 $x$ 存在，$[kx, (k + 1)x)$ 中间也有数，那么 $k$ 必须存在，否则不合法。

看似是 $O(n ^ 2)$ 的，但是我们发现对于每个 $x$，需要枚举的 $k$ 仅为 $\dfrac{C}{x}$，其中 $C$ 为最大的数。

所以时间复杂度为 $O(C + \dfrac C2 + \dfrac C3 + …)$，为调和级数，$O(C\ln C)$。

至于怎么统计一个区间出现过没有数，直接前缀和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve()
{
    for (int i = 1; i <= c; ++ i) h[i] += h[i - 1];
    for (int i = 1; i <= c; ++ i) {
		for (int l = i, r, j = 0; l <= c; l = r + 1)
		{
			if (h[i] == h[i - 1]) break;
			r = std::min(c, l + i - 1), j ++;
			if (h[r] == h[l - 1]) continue;
			if (h[j] == h[j - 1]) {
				puts("No");
				return;
			}
		}
	}
	puts("Yes");
}

E.

题意：给定由数字组成的字符串 $s$ 和 $t$，求有多少种重排后的 $s$ 满足 $s$ 的字典序小于 $t$，答案对 998244353 取模。$|s|, |t|\leq 2\cdot 10^5, s_i, t_i\leq 2\cdot 10^5$。

比较思维的一个组合计数，但不是特别难。

考虑类似数位 DP 的方法，枚举出现差异为第 $i$ 位，那么前 $i - 1$ 项都是相同的。

假设我们暴力的话，我们枚举 $i$ 填入的数，显然填入的数 $x < b_i$，那么剩下的位置就可以随意组织了。因为有重复元素，不直接是阶乘，而是：

现在我们考虑快速将所有填入的 $x$ 的答案全部统计了。

假设我们不限制这一位，答案是：

限制之后，答案是：

所以我们要在原来的基础上乘以 $\dfrac{cnt_x}{n - i + 1}$。

所以我们直接维护 $cnt_x$ 的前缀和，用树状数组就可以在 $O(\log n)$ 的时间内维护。

至于如何维护不限制情况下的答案，我们也可以使用类似的办法。

填这一位之前：

假设 $b_i = x$，也就是我们要填入 $x$，那么答案变为了：

所以答案乘上了 $\dfrac{cnt_x}{n - i + 1}$，先维护每个数的逆元就可以 $O(1)$ 维护了。

可能无法在 $i$ 处填入 $b_i$，注意要快速退出。

注意如果 $n < m$ 且前 $n$ 个都可以填入，答案要加 1（因为前面一样，长度小的排前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct BIT {  } bt;

int main()
{
	int len = std::min(n, m);
	LL res = 0, now = fact[n];
	for (int i = 1; i <= n; ++ i) cnt[a[i]] ++;
	for (int i = 1; i < N; ++ i) now = now * infact[cnt[i]] % Mod;
	for (int i = 1; i < N; ++ i) bt.add(i, cnt[i]);
	bool flag = 1;
	for (int i = 1; i <= len; ++ i)
	{
		res = (res + bt.ask(b[i] - 1) * now % Mod * inv[n - i + 1]) % Mod;
		if (!cnt[b[i]]) {
			flag = 0;
			break;
		}
		bt.add(b[i], -1), now = now * inv[n - i + 1] % Mod * (cnt[b[i]] --) % Mod;
	}
	printf("%lld\n", (res + ((n < m) && flag)) % Mod);
}