P7149 [USACO20DEC] Rectangular Pasture S
题目描述
Farmer John 最大的牧草地可以被看作是一个由方格组成的巨大的二维方阵（想象一个巨大的棋盘）。现在，有NNN头奶牛正占据某些方格（1≤N≤25001≤N≤25001≤N≤2500）。
Farmer John 想要建造一个可以包围一块矩形区域的栅栏；这个矩形必须四边与xxx轴和yyy轴平行，最少包含一个方格。请帮助他求出他可以包围在这样的区域内的不同的奶牛子集的数量。注意空集应当被计算为答案之一。
输入格式
输入的第一行包含一个整数NNN。以下NNN行每行包含两个空格分隔的整数，表示一头奶牛所在方格的坐标(x,y)(x,y)(x,y)。所有xxx坐标各不相同，所有yyy坐标各不相同。所有xxx与yyy的值均在0…1090…10^90…109范围内。
输出格式
输出 FJ 可以包围的奶牛的子集数量。可以证明这个数量可以用 64 位有符号整数型存储（例如 C/C++ 中的long long）。
输入输出样例 #1
输入 #1
4 0 2 1 0 2 3 3 5输出 #1
13说明/提示
共有242^424个子集。FJ 不能建造一个栅栏仅包围奶牛111、222、444，或仅包围奶牛222、444，或仅包围奶牛111、444，所以答案为24−3=16−3=132^4-3=16-3=1324−3=16−3=13。
- 测试点 2-3 满足N≤20N≤20N≤20。
- 测试点 4-6 满足N≤100N≤100N≤100。
- 测试点 7-12 满足N≤500N≤500N≤500。
- 测试点 13-20 没有额外限制。
供题：Benjamin Qi
C++实现
#include<iostream>#include<algorithm>usingnamespacestd;typedeflonglongll;#defineMAXN2505ll N;pair<ll,ll>x[MAXN];ll ans=1;ll l[MAXN],r[MAXN];intmain(){cin>>N;for(inti=0;i<N;i++)cin>>x[i].first>>x[i].second;sort(x,x+N);for(ll i=0;i<N;i++){ans++;ll lt=0,rt=0;for(ll j=i-1;j>=0;j--){if(x[i].second>x[j].second){ans+=(rt+1)*(l[j]+1);r[j]++;lt++;}else{ans+=(lt+1)*(r[j]+1);l[j]++;rt++;}}}cout<<ans<<endl;return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
