P7149 [USACO20DEC] Rectangular Pasture S

思路

由于确定一个矩形后这个矩形里面有哪些奶牛是确定的,而且如果确定矩形的上下左右的边的位置,这个矩形就是确定的,所以这道题就改为计算有多少个不同矩形,使得每个矩形里面至少有一个一个奶牛,而且每个奶牛是在矩形的边上的(用来防止多个矩形内的奶牛一样)。

那么,我们可以先枚举两个奶牛确定两个奶牛作为上下两条边。然后可以计算出靠左边的奶牛的左边有多少奶牛在我们确定的两条边之间(算上用来确定上下边的奶牛),右侧同样计算,然后用左边的乘以右边。

统计的话,我们可以先按横坐标排好序(这篇文章里面的横纵坐标是按照计算机的表格的横纵坐标来说的,也就是行列,第一行第二列的横坐标是 $1$,纵坐标是 $2$,横坐标越大越靠下,虽然按数学平面直角坐标系的横纵坐标也一样),然后枚举确定一个下边,然后再从这个点往前寻找一个上边,由于我们之前排好序了,所以往前搜索的纵坐标肯定小于我们确定的这个下边,而且由于我们是逐渐往前枚举的,所以我们河阳也能确定给横坐标在两条边之间的点有哪些了。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int p[100005];
/*

li,ri 代表i 左边有多少个点,右边有多少个点
lj,rj 同理
由于i是从左往右的,所以这样统计是没问题的
*/
int n, ans;
struct node {
    int x, y;
} a[1000005];
bool cmp(node x, node y) {
    if (x.x != y.x) return x.x < y.x;
    else return x.y < y.y;
}
int lj[1000005], rj[1000005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    p[0] = 1;
    for (int i = 1; i <= 60; i ++) p[i] = p[i - 1] * 2;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i].x >> a[i].y;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i ++) {
        ans ++;
        int li = 0, ri = 0;
        for (int j = i - 1; j >= 1; j --) {

            if (a[i].y > a[j].y) {
                ans += (lj[j] + 1) * (ri + 1);
                li ++;
                rj[j] ++;
            }
            else {
                ans += (li + 1) * (rj[j] + 1);
                ri ++;
                lj[j] ++;
            }

        }
    }
//  ans = p[n] - ans;
    cout << ans + 1;
    return 0;
}
本文链接:https://ztrztr.top/archives/1032
版权声明:本文 《P7149 [USACO20DEC] Rectangular Pasture S》 为 ztrztr 原创。著作权归作者所有。
转载说明:联系作者或者评论区留言获得转载授权,并注明转载地址。
暂无评论

发送评论 编辑评论


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