BZOJ 3208: 花神的秒题计划Ⅰ

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
", 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