【AT2394】井井井 / ###


题目地址:AT2394 [ARC071B] 井井井 / ### – 洛谷 | 计算机科学教育新生态

$\rm{Description}$

在平面直角坐标系中,给定 $n$ 条平行于 $y$ 轴的线和 $m$ 条平行于 $x$ 轴的线,求由这些线组成的矩形的面积和。

$\rm{Solution}$

$\rm{subtask}$ $\rm{1}$

考虑暴力做法,枚举矩形的左上角和右下角,也就是求:

$$
\sum_{1\leq i\leq j\leq n}\sum_{1\leq k\leq l\leq m}(x_j-x_i)\cdot(y_l-y_k)
$$

时间复杂度是 $\mathcal{O}(n^2m^2)$ .

$\rm{subtask}$ $\rm{2}$

对于任意一个矩形,想要确定它,只需要固定一条平行于 $x$ 轴的线段和一条平行于 $y$ 轴的线段。

所以最终的答案可以写成:

$$
\sum_{i\leq i\leq j\leq n}(x_j-x_i)\sum_{1\leq k\leq l\leq m}(y_l-y_k)
$$

记 $A=\sum\limits_{1\leq i\leq j\leq n}(x_j-x_i)$,$B=\sum\limits_{1\leq k\leq l\leq m}(y_l-y_k)$,那么我们可以分开计算 $A$ 和 $B$。也就是分别计算:所有平行于 $x$ 轴的线段长度和,以及所有平行于 $y$ 轴的线段长度和

这样可以得到 $\mathcal{O}(n^2)$ 级别的算法。

$\rm{subtask}$ $\rm{3}$

思路:

对于满分做法,我们期望 $\mathcal{O}(n)$ 的算法,现在想要进一步简化上面的式子。

考虑如何快速求出所有平行于 $x$ 轴的线段长度和。容易想到,我们只需要统计每条小线段被算了几次。显然对于线段 $(x_{i-1}, x_{i})$,被计算了 $(i – 1) \times(n-i-1)$ 次,于是我们就有了线性的做法。

对于平行于 $y$ 轴的线段,计算方法完全相同。

如果到此为止您看懂了,那可以直接看代码了,如果没看懂,请看下面这部分。

具体地:

定义一个线段是基本线段,当且仅当线段的两个端点之间不存在另一个端点,那么我们可以将每条线段拆成基本线段的和的形式,之后分别计算每条基本线段的贡献。

比如:

【AT2394】井井井 / ###插图

对于这张图,线段长度和为 $|AB|+|AC|+|AD|+|BC|+|BD|+|CD|$.

那么我们将上图中每个线段表示成基本线段的和的形式,比如 $|AC|=|AB|+|BC|$,整理之后即:

$$
3|AB|+4|BC|+3|CD|
$$

现在考虑如何计算每条基本线段的贡献。

根据小学数学知识,线段 $(x_i, x_{i – 1})$ 被算的次数是 $(i-1)\times (n – i – 1)$ ,这样我们就能 $\mathcal{O}(n)$ 地算出平行于 $x$ 轴的线段长度和。

对于平行于 $y$ 轴的,用同样的方法计算。

$\rm{Code}$

#include <bits/stdc++.h>
#define int long long
#define MAXN 100008
using namespace std;
int n, m, x[MAXN], y[MAXN];
int A, B; //A为所有平行于 x 轴的线段长度和,B为平行于 y 轴的线段长度和
const int mod = 1e9 + 7;
signed main() {
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld", &x[i]);
	for(int i = 1; i <= m; i++) scanf("%lld", &y[i]);
	sort(x + 1, x + n + 1); //横纵坐标升序排序
	sort(y + 1, y + m + 1);
	for(int i = 2; i <= n; i++) { //计算与x轴平行的所有线段的长度和
		A = (A + (x[i] - x[i - 1]) * (i - 1) * (n - i + 1)) % mod;
	}
	for(int i = 2; i <= m; i++) {
		B = (B + (y[i] - y[i - 1]) * (i - 1) * (m - i + 1)) % mod;
	}
	printf("%lld\n", A * B % mod);
	return 0;
}
内容原创,转载请著名本文URL:https://www.tonyyin.top/2020/12/at2394/
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇