3208: 花神的秒題計劃Ⅰ

Time Limit:?16 Sec??Memory Limit:?128 MB
Submit:?695??Solved:?474
[Submit][Status][Discuss]

Description

背景【backboard】： Memphis等一群蒟蒻出題中，花神湊過來秒題…… 描述【discribe】： 花花山峰巒起伏，峰頂常年被雪，Memphis打算幫花花山風景區的人員開發一個滑雪項目。 我們可以把風景區看作一個n*n的地圖，每個點有它的初始高度，滑雪只能從高處往低處滑【嚴格大于】。但是由于地勢經常變動【比如雪崩、滑坡】，高度經常變化；同時，政府政策規定對于每個區域都要間歇地進行保護，防止環境破壞。現在，滑雪項目的要求是給出每個n*n個點的初始高度，并給出m個命令，C a b c表示坐標為a,b的點的高度改為c；S a b c d表示左上角為a,b右下角為c,d的矩形地區開始進行保護，即不能繼續滑雪；B a b c d表示左上角為a b,右下角為c d的矩形地區取消保護，即可以開始滑雪；Q表示詢問現在該風景區可以滑雪的最長路徑為多少。對于每個Q要作一次回答。 花神一看，這不是超簡單！立刻秒出了標算~

?

Input

第一行n，第二行開始n*n的地圖，意義如上；接下來一個m，然后是m個命令，如上

?

Output

對于每一個Q輸出單獨一行的回答

Sample Input

5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
5
C 1 1 3
Q
S 1 3 5 5
S 3 1 5 5
Q

Sample Output

24
3

樣例解釋：
第一個Q路線為：25->24->23->22….->3->2
第二個Q的路線為：10->9->2

HINT

?

100%的數據：1<=n<=700;1<=m<=1000000;其中Q、S、B操作總和<=100;

題中所有數據不超過2*10^9

?

Source

原創 Memphis

[Submit][Status][Discuss]

?

看到數據范圍都不相信自己眼睛，額，花神系列什么時候出了這么一道水題？

完完全全的暴力，每次暴力修改高度，暴力標記保護，詢問就BFS一遍算答案。

?

1 #include <cstdio> 2 #include <cstring> 3 4 const int siz = 705; 5 6 int n, m; 7 int h[siz][siz]; 8 int v[siz][siz]; 9 int c[siz][siz]; 10 int f[siz][siz]; 11 12 const int mv[4][2] = 13 { 14 {0, +1}, 15 {0, -1}, 16 {-1, 0}, 17 {+1, 0} 18 }; 19 20 inline int path(void) 21 { 22 static int que[siz * siz][2], hd, tl; 23 24 memset(f, 0, sizeof(f)); 25 memset(c, 0, sizeof(c)); 26 27 hd = 0, tl = 0; 28 29 int ans = 0; 30 31 for (int i = 1; i <= n; ++i) 32 for (int j = 1; j <= n; ++j) 33 if (!v[i][j]) 34 { 35 for (int k = 0; k < 4; ++k) 36 { 37 int x = i + mv[k][0]; 38 int y = j + mv[k][1]; 39 40 if (x < 1 || x > n)continue; 41 if (y < 1 || y > n)continue; 42 43 if (!v[x][y] && h[x][y] > h[i][j]) 44 ++c[i][j]; 45 } 46 47 if (!c[i][j]) 48 { 49 que[tl][0] = i; 50 que[tl][1] = j; 51 f[i][j] = 1; 52 ++tl; 53 } 54 } 55 56 while (hd != tl) 57 { 58 int x = que[hd][0]; 59 int y = que[hd][1]; 60 ++hd; 61 62 if (ans < f[x][y]) 63 ans = f[x][y]; 64 65 for (int k = 0; k < 4; ++k) 66 { 67 int i = x + mv[k][0]; 68 int j = y + mv[k][1]; 69 70 if (i < 1 || i > n)continue; 71 if (j < 1 || j > n)continue; 72 73 if (!v[i][j] && h[x][y] > h[i][j]) 74 { 75 if (f[i][j] < f[x][y] + 1) 76 f[i][j] = f[x][y] + 1; 77 78 if (--c[i][j] == 0) 79 { 80 que[tl][0] = i; 81 que[tl][1] = j; 82 ++tl; 83 } 84 } 85 } 86 } 87 88 return ans; 89 } 90 91 signed main(void) 92 { 93 scanf("%d", &n); 94 95 for (int i = 1; i <= n; ++i) 96 for (int j = 1; j <= n; ++j) 97 scanf("%d", &h[i][j]); 98 99 scanf("%d", &m); 100 101 while (m--) 102 { 103 static int a, b, c, d; 104 105 static char s[5]; 106 107 scanf("%s", s); 108 109 switch(s[0]) 110 { 111 case 'Q': 112 printf("%d\n", path()); 113 break; 114 case 'C': 115 scanf("%d%d%d", &a, &b, &c); 116 h[a][b] = c; 117 break; 118 case 'S': 119 scanf("%d%d%d%d", &a, &b, &c, &d); 120 for (int i = a; i <= c; ++i) 121 for (int j = b; j <= d; ++j) 122 v[i][j] = true; 123 break; 124 case 'B': 125 scanf("%d%d%d%d", &a, &b, &c, &d); 126 for (int i = a; i <= c; ++i) 127 for (int j = b; j <= d; ++j) 128 v[i][j] = false; 129 break; 130 } 131 } 132 }

?

@Author: YouSiki

?

轉載于:https://www.cnblogs.com/yousiki/p/6297460.html

總結

以上是生活随笔為你收集整理的BZOJ 3208: 花神的秒题计划Ⅰ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。