网站开发制作公司排行,洛阳做网站哪家便宜,学校网站建设目的是什么,网站留言板怎么做phpHopping Rabbit
题意#xff1a;
给你n个矩阵#xff0c;每个矩阵(给出左上标和右下标)#xff0c;现在让你给出一个点的位置#xff0c;这个点每次只能上下左右四个方向移动#xff0c;且移动距离为d#xff0c;是否存在一个这样的点#xff0c;其所有落点都不在矩阵…Hopping Rabbit
题意
给你n个矩阵每个矩阵(给出左上标和右下标)现在让你给出一个点的位置这个点每次只能上下左右四个方向移动且移动距离为d是否存在一个这样的点其所有落点都不在矩阵内。
题解
能到达的位置都是周期重复的比如当前点在(x,y),那么可以到达(xd,y),(x2d,y)所以我们将所有(k1d,k2d)到(k1dd,k2dd)范围内的所有图形移动至(1,1)到(d,d)范围内相当于整体大地图上彼此可以到达的点当作一个点这样就得到一个d * d的小地图 同样矩阵也会被带到这个小地图矩阵所覆盖小地图的部分说明在这个位置跳终究会跳到矩阵中所以我要找是否存在一个点没有被矩阵覆盖。 那问题就变成n个矩阵移动至(1,1)到(d,d)范围内求并这是扫描先的典型操作。我们用扫描线求每一行的最小值如果存在0说明有个点没有被覆盖记录坐标否在就是全部被覆盖 情况如图 代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime clock(); //计时开始freopen(in.txt,r,stdin);#endif
}
void Time_test(){#ifdef ONLINE_JUDGE#elseendTime clock(); //计时结束printf(\n运行时间为:%lfs\n,(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif
}
const int N200010;#define lson (id1)
#define rson ((id1)|1)
#define mid ((lr)1)struct Node
{int val,add,mul;
}tr[N2];void push_up(int id,int l,int r)
{tr[id].valmin(tr[lson].val,tr[rson].val);
}void solve(int id,int mul,int add){tr[id].addtr[id].add*muladd;tr[id].multr[id].mul*mul;tr[id].valtr[id].val*muladd;
}
void push_down(int id){solve(id1,tr[id].mul,tr[id].add);solve(id1|1,tr[id].mul,tr[id].add);tr[id].mul1;tr[id].add0;
}void build(int id,int l,int r)
{tr[id].mul1;tr[id].add0;if (lr){tr[id].val0;return;}build(lson,l,mid);build(rson,mid1,r);push_up(id,l,r);
}void update(int id,int l,int r,int L,int R,int mul,int add)
{if (Ll Rr){solve(id,mul,add);return;}push_down(id);if (midR) update(lson,l,mid,L,R,mul,add);else if (midL) update(rson,mid1,r,L,R,mul,add);else{update(lson,l,mid,L,mid,mul,add);update(rson,mid1,r,mid1,R,mul,add);}push_up(id,l,r);
}int query(int id,int l,int r,int L,int R)
{if (Ll Rr) return tr[id].val;push_down(id);if (midR) return query(lson,l,mid,L,R);if (midL) return query(rson,mid1,r,L,R);return min(query(lson,l,mid,L,mid),query(rson,mid1,r,mid1,R));
}int n,d;
vectorpairint,int add[N],del[N];void upd(int x1,int y1,int x2,int y2)
{int xl0,xr0,yl0,yr0;if (x2-x1d){xl1;xrd;}else{xl(x1%dd)%d1;xr((x2-1)%dd)%d1;}if (y2-y1d){yl1;yrd;}else{yl(y1%dd)%d1;yr((y2-1)%dd)%d1;}if (xlxr){if (ylyr){add[yl].push_back({xl,xr});del[yr1].push_back({xl,xr});}else//列拆分成两部分 {add[1].push_back({xl,xr});del[yr1].push_back({xl,xr});add[yl].push_back({xl,xr});del[d1].push_back({xl,xr});}}else//行拆分成两部分 {if (ylyr){add[yl].push_back({1,xr});add[yl].push_back({xl,d});del[yr1].push_back({1,xr});del[yr1].push_back({xl,d});}else{add[1].push_back({1,xr});add[1].push_back({xl,d});del[yr1].push_back({1,xr});del[yr1].push_back({xl,d});add[yl].push_back({1,xr});add[yl].push_back({xl,d});del[d1].push_back({1,xr});del[d1].push_back({xl,d});}}
}int main()
{scanf(%d%d,n,d);int x10,y10,x20,y20;for (int i1;in;i){scanf(%d%d%d%d,x1,y1,x2,y2);upd(x1,y1,x2,y2);}build(1,1,d);int ansx0,ansy0;for (int y1;yd;y){for (PII it:add[y]){update(1,1,d,it.first,it.second,1,1);}for (PII it :del[y]){update(1,1,d,it.first,it.second,1,-1);}if (query(1,1,d,1,d)0)//如果存在空隙找到空隙坐标 {for (int x1;xd;x){if (query(1,1,d,x,x)0){ansxx;ansyy;break;}}break;}}if (!ansx) printf(NO\n);else printf(YES\n%d %d\n,ansx-1d,ansy-1d);return 0;
}
