XYD周测T1样例不过离散化正确求助！！！

杨思越 · 2025 年6 月 7 日 08:54

1. 牛牛的围栏

题目ID：21636必做题100分

时间限制: 1000ms

空间限制: 262144kB

题目描述

农夫约翰有一片巨大的二维网格状牧场（想象一个超大的棋盘）。目前有N头奶牛（1≤N≤2500）分布在不同的网格单元中。约翰想要建造一个围栏，围住一个矩形区域内的奶牛子集。这个矩形必须与x轴和y轴平行，最小可以只包含一个单元格。请帮他计算可以围住的不同奶牛子集数量（包括空子集）。

输入格式

第一行：整数N（奶牛数量）

接下来N行：每行两个整数，表示奶牛的(x,y)坐标

所有x坐标互不相同，所有y坐标也互不相同

坐标值范围：0到10^9

输出格式

可围住的奶牛子集总数（保证可以用64位有符号整数存储）（long long in C/C++）

样例

Input 1

4 0 2 1 0 2 3 3 5

Output 1

13

样例解释

总共有2^4=16个子集。无法围住的子集有：

仅包含奶牛1、2、4

仅包含奶牛2、4

仅包含奶牛1、4
因此答案为16-3=13

数据范围

测试点2-3：N≤20

测试点4-6：N≤100

测试点7-12：N≤500

测试点13-20：无额外限制

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(int x,int y){
	return x<y;
}
int n;
struct box{
	int x,y;
}cow[505];
int x[505],y[505];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		cow[i].x=x[i];
		cow[i].y=y[i];
	}
	sort(x+1,x+1+n,cmp);
	sort(y+1,y+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(cow[i].x==x[j]){
				cow[i].x=j;
				break;
			}
		}
		for(int j=1;j<=n;j++){
			if(cow[i].y==y[j]){
				cow[i].y=j;
				break;
			}
		}
	}
	/*for(int i=1;i<=n;i++){
		cout<<cow[i].x<<" "<<cow[i].y<<endl;
	}*/
	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			//选定cow[i],cow[j]为上下区间
			ans=ans+min(cow[i].x,cow[j].x)*abs(cow[i].y-cow[j].y);
			ans=ans+(n-1-max(cow[i].x,cow[j].x))*abs(cow[i].y-cow[j].y);
		}
	}
	cout<<ans;
	return 0;
}
/*
 
    \__/
 \ /   \ /
—|o_o | —
 /\ _ /\ 
   / \
00000000-0010-0824-0000-000000000000


*/

360病毒 · 2025 年6 月 7 日 08:57

你没有用前缀和吗？

杨思越 · 2025 年6 月 7 日 08:57

呃,不太理解

360病毒 · 2025 年6 月 7 日 09:01

思路不理解吗？

杨思越 · 2025 年6 月 7 日 09:02

是的

360病毒 · 2025 年6 月 7 日 09:03

具体哪里不理解？

杨思越 · 2025 年6 月 7 日 10:45

现在代码是这样:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(int x,int y){
	return x<y;
}
int n;
struct box{
	int x,y;
}cow[505];
int x[505],y[505];
int qq[505][505];
int get_(int x1,int y_,int x2,int y2){
	return qq[x2+1][y2+1]-qq[x2+1][y_]-qq[x1][y2+1]+qq[x1][y_];
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		cow[i].x=x[i];
		cow[i].y=y[i];
	}
	sort(x+1,x+1+n,cmp);
	sort(y+1,y+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(cow[i].x==x[j]){
				cow[i].x=j;
				break;
			}
		}
		for(int j=1;j<=n;j++){
			if(cow[i].y==y[j]){
				cow[i].y=j;
				break;
			}
		}
	}
	/*for(int i=1;i<=n;i++){
		cout<<cow[i].x<<" "<<cow[i].y<<endl;
	}*/
	for(int i=1;i<=n;i++){
		qq[cow[i].x][cow[i].y]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			qq[i][j]+=qq[i-1][j]+qq[i][j-1]-qq[i-1][j-1];
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			//选定cow[i],cow[j]为上下区间
			int x1=min(cow[i].x,cow[j].x);
			int x2=max(cow[i].y,cow[j].y);
			ans+=get_(0,i,x1,j)*get_(x2,i,n-1,j);
		}
	}
	cout<<ans;
	return 0;
}
/*
 
    \__/
 \ /   \ /
—|o_o | —
 /\ _ /\ 
   / \
00000000-0010-0824-0000-000000000000


*/

样例不过

360病毒 · 2025 年6 月 7 日 10:50

第一，ans初始值要为n，因为单独一头奶牛也是一种方案；
第二，get返回值要加1；
第三，统计答案时，j从i+1开始枚举

杨思越 · 2025 年6 月 7 日 10:52

样例过,RE5

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(int x,int y){
	return x<y;
}
int n;
struct box{
	int x,y;
}cow[505];
int x[505],y[505];
int qq[505][505];
int get_(int x1,int y_,int x2,int y2){
	return qq[x2+1][y2+1]-qq[x2+1][y_]-qq[x1][y2+1]+qq[x1][y_]+1;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		cow[i].x=x[i];
		cow[i].y=y[i];
	}
	sort(x+1,x+1+n,cmp);
	sort(y+1,y+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(cow[i].x==x[j]){
				cow[i].x=j;
				break;
			}
		}
		for(int j=1;j<=n;j++){
			if(cow[i].y==y[j]){
				cow[i].y=j;
				break;
			}
		}
	}
	/*for(int i=1;i<=n;i++){
		cout<<cow[i].x<<" "<<cow[i].y<<endl;
	}*/
	for(int i=1;i<=n;i++){
		qq[cow[i].x][cow[i].y]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			qq[i][j]+=qq[i-1][j]+qq[i][j-1]-qq[i-1][j-1];
		}
	}
	ll ans=n;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			//选定cow[i],cow[j]为上下区间
			int x1=min(cow[i].x,cow[j].x);
			int x2=max(cow[i].y,cow[j].y);
			ans+=get_(0,i,x1,j)*get_(x2,i,n-1,j);
		}
	}
	cout<<ans;
	return 0;
}
/*
 
    \__/
 \ /   \ /
—|o_o | —
 /\ _ /\ 
   / \
00000000-0010-0824-0000-000000000000


*/

360病毒 · 2025 年6 月 7 日 10:52

数组开到2505，另外，你在写啥？

杨思越 · 2025 年6 月 7 日 10:53

WA5

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(int x,int y){
	return x<y;
}
int n;
struct box{
	int x,y;
}cow[2503];
int x[2503],y[2503];
int qq[2503][2503];
int get_(int x1,int y_,int x2,int y2){
	return qq[x2+1][y2+1]-qq[x2+1][y_]-qq[x1][y2+1]+qq[x1][y_]+1;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		cow[i].x=x[i];
		cow[i].y=y[i];
	}
	sort(x+1,x+1+n,cmp);
	sort(y+1,y+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(cow[i].x==x[j]){
				cow[i].x=j;
				break;
			}
		}
		for(int j=1;j<=n;j++){
			if(cow[i].y==y[j]){
				cow[i].y=j;
				break;
			}
		}
	}
	/*for(int i=1;i<=n;i++){
		cout<<cow[i].x<<" "<<cow[i].y<<endl;
	}*/
	for(int i=1;i<=n;i++){
		qq[cow[i].x][cow[i].y]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			qq[i][j]+=qq[i-1][j]+qq[i][j-1]-qq[i-1][j-1];
		}
	}
	ll ans=n;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			//选定cow[i],cow[j]为上下区间
			int x1=min(cow[i].x,cow[j].x);
			int x2=max(cow[i].y,cow[j].y);
			ans+=get_(0,i,x1,j)*get_(x2,i,n-1,j);
		}
	}
	cout<<ans;
	return 0;
}
/*
 
    \__/
 \ /   \ /
—|o_o | —
 /\ _ /\ 
   / \
00000000-0010-0824-0000-000000000000


*/

yangshe · 2025 年6 月 7 日 11:13

求二维前缀和的x1 x2这种别搞混，你的离散化以及输入的时候有的是从1开始，有的是从0开始，你的二维前缀和是从1开始的

yangshe · 2025 年6 月 7 日 11:13

这里改成x

yangshe · 2025 年6 月 7 日 11:14

在这个前面，按照y排序一下

yangshe · 2025 年6 月 7 日 11:14

+1去掉

yangshe · 2025 年6 月 7 日 11:15

输出的时候ans+1

杨思越 · 2025 年6 月 7 日 11:21

二维数组咋排序

yangshe · 2025 年6 月 7 日 11:23

给cow排序，按照列从小到大排序

杨思越 · 2025 年6 月 7 日 11:31

全WA

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct box{
	int x,y;
}cow[2503];
bool cmp(int x,int y){
	return x<y;
}
bool cmp1(box x,box y){
	return x.y<y.y;
}
int n;
int x[2503],y[2503];
int qq[2503][2503];
int get_(int x1,int y_,int x2,int y2){
	return qq[x2+1][y2+1]-qq[x2+1][y_]-qq[x1][y2+1]+qq[x1][y_];
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		cow[i].x=x[i];
		cow[i].y=y[i];
	}
	sort(x+1,x+1+n,cmp);
	sort(y+1,y+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(cow[i].x==x[j]){
				cow[i].x=j;
				break;
			}
		}
		for(int j=1;j<=n;j++){
			if(cow[i].y==y[j]){
				cow[i].y=j;
				break;
			}
		}
	}
	/*for(int i=1;i<=n;i++){
		cout<<cow[i].x<<" "<<cow[i].y<<endl;
	}*/
	for(int i=1;i<=n;i++){
		qq[cow[i].x][cow[i].y]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			qq[i][j]+=qq[i-1][j]+qq[i][j-1]-qq[i-1][j-1];
		}
	}
	sort(cow,cow+n,cmp1);
	ll ans=n;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			//选定cow[i],cow[j]为上下区间
			int x1=min(cow[i].x,cow[j].x);
			int x2=max(cow[i].x,cow[j].x);
			ans+=get_(0,i,x1,j)*get_(x2,i,n-1,j);
		}
	}
	cout<<ans+1;
	return 0;
}
/*
 
    \__/
 \ /   \ /
—|o_o | —
 /\ _ /\ 
   / \
00000000-0010-0824-0000-000000000000


*/

yangshe · 2025 年6 月 7 日 11:31

你的cow是从1开始的，那应该是 sort(cow+1,cow+n+1,cmp1);`