洛谷链接
FZQOJ

First

这一题的题面看似很长，

但是实际上归纳下来可以总结为：

(1)：告诉你有i张地毯

(2)：第2行~第i+1行告诉你地毯的位置（前两个是最左边端点的坐标，后两个是x,y轴长度）

(3):输入要查找的哪一行最后被第几张地毯覆盖

Second

​ 我一开始的想法是用二维数组来写

代码：

#include<bits/stdc++.h>
using namespace std;

long long k[10000][10000]={0},ans[10000][10000]={0};//k数组是表示某个点是否被覆盖（0表没有，1表有），ans数组表示某个点最后被第几个数覆盖
int main(){
	int a,b=0,c,d,i,j,n,x1,y1,x2,y2,l;
	scanf("%d",&a);
	for(l=1;l<=a;l++){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		for(i=y1;i<=y1+y2;i++){			//y轴长度
			for(j=x1;j<=y1+y2;j++){		//x轴长度
				k[j][i]=1;				//将他们变为已覆盖
				ans[j][i]=l;			//记录下他们是被第几个地毯覆盖的
			}
		}
	}
	scanf("%d %d",&x1,&y1);
	if(k[x1][y1]==1){					//如果已覆盖
		printf("%d",ans[x1][y1]);		//输出被第几个地毯覆盖
	}
	else{
		printf("-1");
	}
	return 0;
}

但是

这样就会有一个问题，文中的数组要求很大，必须是k[100000] [100000]

这样就连long long都存不下

所以

这一题只得了50分，必须换一种方法

Third

于是我换了一个想法：不需要遍历每一个地毯的位置，其实只需要判断一个地毯x轴最大是否大于需要判断位置的x轴，y轴同理

​ 如果满足大于的话，那么就会被覆盖，反之不会

所以我将源代码重新改了一下，得到如下代码：

#include<bits/stdc++.h>
using namespace std;

struct dx{
	long long x1;
	long long y1;
	long long x2;
	long long y2;//定义结构体数组，用四个数组分别存也行
};

dx k[100010];
int main(){
	long long a,b=0,i,j,n,x1,y1,x2,y2,ans=0;
	scanf("%lld",&a);
	for(i=1;i<=a;i++){
		scanf("%lld %lld %lld %lld",&k[i].x1,&k[i].y1,&k[i].x2,&k[i].y2);	//先记录下来，后面判断
	}
	scanf("%lld %lld",&x1,&y1);
	for(i=1;i<=a;i++){
		if((k[i].x1+k[i].x2>=x1)&&(k[i].y1+k[i].y2>=y1)){		//判断是否大于x与y轴，如果是就保存被那个数覆盖
			ans=i;
		}
	}
	if(ans==0){
		printf("-1");
	}
	else{
		printf("%lld",ans);
	}
	return 0;
}

我原本以为到这里就结束了，但是还没AC

我重新检查后，发现漏了一个部分：如果地毯左下一开始就是在需要判断的点上方，那么地毯是不能覆盖的，但是我们判断中确实是x与y轴都大于需要判断的点

SO

加上一句话就可以成功AC

附上最后解题代码

#include<bits/stdc++.h>
using namespace std;

struct dx{
	long long x1;
	long long y1;
	long long x2;
	long long y2;
};

dx k[100010];
int main(){
	long long a,b=0,i,j,n,x1,y1,x2,y2,ans=0;
	scanf("%lld",&a);
	for(i=1;i<=a;i++){
		scanf("%lld %lld %lld %lld",&k[i].x1,&k[i].y1,&k[i].x2,&k[i].y2);
	}
	scanf("%lld %lld",&x1,&y1);
	for(i=1;i<=a;i++){				//前面与上一个代码无区别，但是在下一步的判断中，加上（如果地毯左下端点一开始就是在需要判断的点上方，那么不符合）	
        							//需要加上左下端点在需判断的点下方，那么就符合
		if((k[i].x1+k[i].x2>=x1)&&(k[i].y1+k[i].y2>=y1)&&(k[i].x1<=x1&&k[i].y1<=y1)){
			ans=i;										
		}
	}
	if(ans==0){
		printf("-1");
	}
	else{
		printf("%lld",ans);
	}
	return 0;
}

Update 2023/8/27

做到这里其实有优化的地步，就是将数组倒序循环，第一个满足的就是正序的最后一个，也就是答案：


不同时期，马蜂不同，将就着看

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct dx{
	ll x1, y1, x2, y2;
};

dx k[1010100];
ll n, x, y;

int main(){
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++){
        scanf("%lld %lld %lld %lld", &k[i].x1, &k[i].y1, &k[i].x2, &k[i].y2);
    }
    scanf("%lld %lld", &x, &y);
    for(int i = n; i; i--){
        if ((k[i].x1 + k[i].x2 >= x) && (k[i].y1 + k[i].y2 >= y) && (k[i].x1 <= x && k[i].y1 <= y)){
            printf("%lld", i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}

完结散花！