題目鏈接：http://codeforces.com/contest/1293/problem/C
題目：給定一個 2*n的地圖，初始地圖沒有巖漿，都可以走，
給定q個詢問，每個詢問給定一個點（x，y）,每個詢問有以下作用：
（1）如果該點可走，則變為不可走
（2）如果該點不可走，則變為可走
問，每個詢問作用后，還能否從（1，1）走到（2，n），
思路：我們可以這么想：
如果第二層有個無法走的點，那么只要該點上方三個點任意一個點不可走，則該地圖無法走到終點，
"如果第二層有個無法走的點，那么只要該點上方三個點任意一個點不可走"這句話可以想成該點會對上面
三個點貢獻1點，那么第一層任意點的貢獻值為[0,3]，只要第一層有個點不可走，且第二層給它的貢獻值不為0，
即該地圖無法走通，如果第二層不能走的點變為可走了，那么對上面三個點的貢獻度為-1，即減去之前的1點貢獻，
下面用到了二維轉一維來操作，
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 using namespace std; 6 7 const int N = (int)3e5+100; 8 int app[N << 1];//該點障礙（巖漿）本來是否存在 9 int tot[N];//第一層的貢獻度 10 int sum[10];//貢獻度為1，2，3的點數 11 12 int main(){ 13 14 int n,q; 15 scanf("%d%d",&n,&q); 16 int x,y; 17 while(q--){ 18 scanf("%d%d",&x,&y); 19 if(x > 1){ //第二層 20 if(!app[ n+y ]){//第二層該點本來不存在 21 app[ n+y ] = 1;//標記存在 22 for(int now = max(1,(x-1)*y-1); now <= min((x-1)*y+1,n); ++now){ 23 if(app[now]){//第一層存在 24 //改變該點的貢獻度，隨之也要改變貢獻度為1，2，3的點數的數量 25 --sum[tot[now]]; 26 ++tot[now]; 27 ++sum[tot[now]]; 28 } 29 else ++tot[now]; 30 } 31 }else{ 32 app[ n+y ] = 0; 33 for(int now = max(1,(x-1)*y-1); now <= min((x-1)*y+1,n); ++now){ 34 if(app[now]){//第一層存在 35 --sum[tot[now]]; 36 --tot[now]; 37 ++sum[tot[now]]; 38 } 39 else --tot[now]; 40 } 41 } 42 }else{//第一層的點，要判斷第一層的點是否存在，如果第一層的該點不存在， 43 //第二層的貢獻度對該點也沒有影響 44 if(app[x*y]){ 45 app[x*y] = 0; 46 --sum[tot[x*y]]; 47 } 48 else{ 49 app[x*y] = 1; 50 ++sum[tot[x*y]]; 51 } 52 } 53 if(sum[1]+sum[2]+sum[3]) printf("%d__________________________No\n",sum[1]+sum[2]+sum[3]); 54 else printf("__________________________Yes\n"); 55 } 56 57 return 0; 58 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102311.html
標籤：其他
上一篇：selenium
下一篇：無法解決：androidx.lifecycle：lifecycle-extensions-ktx：2.0.0-alpha1