网站icp备案认证怎么做,宁波网络seo推广,东莞凌峰建设公司,秦皇岛昌黎县建设局网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
还以为这个题有什么高深的算法#xff0c;结果就是个暴力。 由于n∗mn*mn∗m达到了1e101e101e10的级别#xff0c;所以直接暴力肯定是不行的#xff0c;考虑有很多空格#xff0c;我们…传送门
文章目录题意思路题意 思路
还以为这个题有什么高深的算法结果就是个暴力。 由于n∗mn*mn∗m达到了1e101e101e10的级别所以直接暴力肯定是不行的考虑有很多空格我们可以维护四个变量表示边界让后在当前轴上二分最近的障碍点让后判断即可。 实现的时候可以加两个边界比较方便。 要注意如果枚举的四个方向如果有一个方向不能走的话不能直接退出有如下样例 333\ \ 33 3 0110\ \ 1\ \ 10 1 1 0110\ \ 1\ \ 10 1 1 0110\ \ 1\ \ 10 1 1 111代表障碍一开始是向右走显然不能走如果直接退出就错了我们还可以向下走。 只有这一种情况所以特判一下是不是起点即可。
还有注意二分前先给数组排个序。。。 没排序卡了我半天。
// Problem: D. Alice and the Doll
// Contest: Codeforces - Codeforces Round #593 (Div. 2)
// URL: https://codeforces.com/contest/1236/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m,k;
vectorintx[N],y[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d%d,n,m,k);for(int i1;in;i) x[i].pb(0);for(int i1;im;i) y[i].pb(0);for(int i1;ik;i) {int xx,b; scanf(%d%d,xx,b);x[xx].pb(b); y[b].pb(xx);}for(int i1;in;i) sort(x[i].begin(),x[i].end()),x[i].pb(m1);for(int i1;im;i) sort(y[i].begin(),y[i].end()),y[i].pb(n1);int sx,ex,sy,ey;sxsy0; exn1; eym1;LL sum0;int dx,dy; dxdy1;int op0;while(1) {if(op%40) {int poslower_bound(x[dx].begin(),x[dx].end(),dy)-x[dx].begin();int addmin(x[dx][pos],ey);if(add-1dy) {if(op0) {sum; op;continue;} else break;} sumadd-dy;dyadd-1; eydy; sxdx;} else if(op%41) {int poslower_bound(y[dy].begin(),y[dy].end(),dx)-y[dy].begin();int addmin(y[dy][pos],ex);if(add-1dx) break;sumadd-dx;dxadd-1; exdx; eydy;} else if(op%42) {int posupper_bound(x[dx].begin(),x[dx].end(),dy)-x[dx].begin();pos--;int addmax(x[dx][pos],sy);if(add1dy) break;sumdy-add;dyadd1; sydy; exdx;} else if(op%43) {int posupper_bound(y[dy].begin(),y[dy].end(),dx)-y[dy].begin();pos--;int addmax(y[dy][pos],sx);if(add1dx) break;sumdx-add;dxadd1; sxdx; sydy;}op; }sum-op-1;if(sum1ll*n*m-k) puts(Yes);else puts(No);return 0;
}
/**/
