弱鸡记录一道模拟题-创新互联
前言：
这不能算是题解，只是日记+笔记而已
如果您想看正经规范的题解，请移步
题解
最近女赛寄了，并不是因为队员的原因，因为疫情??
我们组没能凑齐最终上场的队员，最后相当于是两个菜鸡上的，我+另外一个已经保研的学姐,这种组合让我成功输掉了比赛，不然总归是能拿个银??
唉，算了不想了
从最基础的开始做吧
真的在比赛的时候就有个怪圈，平时又是练习图论，又是练习数学，最后上场跟榜走的时候竟然只能从模拟这种题（就比较水的开始写起）偏偏还不太擅长做这种题，（平时都不练啊,就很奇怪
所以今天来练练
果然就寄了hh
P1003 [NOIP2011 提高组] 铺地毯
这道题之前做过，之前过的时候数据量没有这么大然后那次比较那啥，用的线段树过的，之后也没看题解，自己当时应该是做麻烦了，毕竟只是一道简单题hh
如果是线段树的话，说一下思路，线段树也是需要使用二维的线段树的，也就是使用二维数组，不能用两个一维数组组在一起，不然的话比如说更新同一段x的不同y值就会出问题
我想的二维线段树解法是，在x方向先找到要更新的段
然后从入口进去
入口就是：
if(l>=L&&r<=R)函数是：
update(int L,int R,int l,int r,int cnt,int v)
{ update(L,R,l,(l+r)/2,cnt*2,v);
update(L,R,(l+r)/2+1,r,cnt*2+1,v);
}//伪代码然后从上面提到的那个入口进去让他去更新y值
可以这么写
if(l>=L&&r<=R)
update(tree[cnt],y1,y2,1,n,1,v);这样的话就相当于更新tree[x_l~tree_r]段的y值，之后查询再返回相应的值
但是有个问题
这个题的数据量是五次方，之前怕超时，现在不超时了，超内存了，得，于是我们换一个方法
当然是看了题解之后
直接存储矩形的左上和右下两个顶点不就行了吗，奶奶的
然后挨个举行判断
giao
我只想到不能暴力枚举了
寄
结果越想越麻烦
hh
贴个代码吧
#includeusing namespace std;
struct point
{int x; int y;
};
struct rectangle
{point p1;
point p2;
};
vectoredge;
int main(void)
{int n;
scanf_s("%d", &n);
for (int i = 0; i< n; i++)
{int a, b,lenx, leny;
scanf_s("%d%d%d%d", &a, &b, &lenx, &leny);
edge.push_back({{a,b},{a + lenx,b + leny} });
}
int x, y;
scanf_s("%d%d", &x, &y);
int ans = -1;
for (int i = 0; i< n; i++)
{if (x >= edge[i].p1.x&&x<= edge[i].p2.x&&y>=edge[i].p1.y&&y<=edge[i].p2.y)
{ ans = i + 1;
}
}
printf("%d", ans);
} 后记：这是VS2017的代码
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享文章：弱鸡记录一道模拟题-创新互联
本文网址：http://6mz.cn/article/dhecso.html