20200722T2 【NOIP2015模拟10.29A组】网格图游戏 Description Input Output Sample Input Sample Output Data Constraint solution code
Input
Output
Sample Input
3 4
2 1 E 1 2 N
2 1 N 1 1 N
3 1 N 2 1 N
2 2 N 1 1 N
Sample Output
YES
YES
NO
NO
Data Constraint
solution
因为处理转换点的问题找了一晚上bug
先埋坑
气死了。。。。
——————————————————————————————
对于一个平面图，任何一条边两侧都是两个平面区域，在纸上画图发现，如果是两个区域，断开这条边我们还可以从外面绕过去得到路径，如果已经合并成一个区域了，就找不到路径。
所以可以用并查集维护。
对于本题来说，画出网格图，中间的是白块，容易发现如果两个点在删掉这条边以前就联通，肯定有白色区域包围一个点，它出不去，就无法链接到另一个点，于是就把删边转化为加边询问连通性，用并查集很好维护。
对于四边的点，我们可以在最外层套一层白块，然后预处理最外面的白块都连通即可。
时间复杂度：
code
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<queue> 7 #include<vector> 8 #include<stack> 9 #include<set> 10 #include<deque> 11 #include<map> 12 using namespace std; 13 14 template <typename T> void read(T &x) { 15 x = 0; int f = 1; char c; 16 for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') f = -f; 17 for (; c >= '0' && c <= '9'; c = getchar()) x = 10 * x + c - '0' ; 18 x *= f; 19 } 20 template <typename T> void write(T x){ 21 if (x < 0) putchar('-'), x = -x; 22 if (x > 9) write(x / 10); 23 putchar(x % 10 + '0'); 24 } 25 template <typename T> void writeln(T x) { write(x); putchar(' '); } 26 template <typename T> void writesn(T x) { write(x); putchar(' '); } 27 28 #define ll long long 29 #define inf 1234567890 30 #define next net 31 #define P 1000000007 32 #define N 500020 33 #define mid ((l+r)>>1) 34 #define lson (o<<1) 35 #define rson (o<<1|1) 36 #define R register 37 38 int n, k, last = 1, maxn; 39 int aa, bb, dd, ee; 40 char cc, ff; 41 int f[800000]; 42 int getf(int x) 43 { 44 return f[x] == x ? x : f[x] = getf(f[x]); 45 } 46 void bing(int x,int y) 47 { 48 f[getf(y)] = f[getf(x)]; 49 } 50 void solve(int x,int y) 51 { 52 if(getf(x) == getf(y)) 53 { 54 printf("NO "); 55 last = 0; 56 return; 57 } 58 bing(x, y); 59 printf("YES "); 60 last = 1; 61 return; 62 } 63 signed main() 64 { 65 read(n); read(k); 66 maxn = (n + 1) * (n + 1); 67 for(R int i = 1; i <= maxn; i++) f[i] = i; 68 for(R int i = 1; i <= n; i++) bing(i, i + 1); 69 for(R int i = 0; i <= n - 1; i++) bing(i * (n + 1) + 1, (i + 1) * (n + 1) + 1); 70 for(R int i = 0; i <= n - 1; i++) bing(i * (n + 1) + n + 1, (i + 1) * (n + 1) + n + 1); 71 for(R int i = 1; i <= n; i++) bing(n * (n + 1) + i, n * (n + 1) + i + 1); 72 while(k--) 73 { 74 read(aa); read(bb); cc = getchar(); while(cc != 'E' && cc != 'N') cc = getchar(); 75 read(dd); read(ee); ff = getchar(); while(ff != 'E' && ff != 'N') ff = getchar(); 76 aa = (aa - 1) * n + bb; 77 dd = (dd - 1) * n + ee; 78 if(last) 79 { 80 //writeln(aa); 81 if(cc == 'E') 82 { 83 //writeln(aa / n); 84 aa = ((aa % n == 0) ? (aa / n) : (aa / n + 1)) * (n + 1) + (aa % n) + (aa % n == 0) * n; 85 bb = aa + 1;//writesn(aa); writeln(bb); 86 solve(aa, bb); 87 } 88 else 89 { 90 aa = (aa / n) * (n + 1) + (aa % n + 1); 91 bb = aa + n + 1;//writesn(aa); writeln(bb); 92 solve(aa, bb); 93 } 94 } 95 else 96 { 97 //writeln(dd); 98 if(ff == 'E') 99 { 100 dd = ((dd % n == 0) ? (dd / n) : (dd / n + 1)) * (n + 1) + (dd % n) + (dd % n == 0) * n; 101 ee = dd + 1;//writesn(dd); writeln(ee); 102 solve(dd, ee); 103 } 104 else 105 { 106 dd = (dd / n) * (n + 1) + (dd % n + 1); 107 ee = dd + n + 1;//writesn(dd); writeln(ee); 108 solve(dd, ee); 109 } 110 } 111 } 112 return 0; 113 }