当前位置：首页 -> 基础 -> c++编程基础

计算机程序设计竞赛艺术(单调栈扩展）(二)

2015-01-27 18:12:49 · 作者: · 浏览: 99
标签: 计算机 程序设计 竞赛 艺术 单调 扩展
es contains two integers A and B, which means Z wonders if there's an empty sub-grid fo size A*B(1<=A<=N;1<=B<=M).
Note that query is just asking question. Z will not draw anything during his query stage. So the test paper remains the same for every query in a test case.

Output

For each query, just output a line containing "Y" if the corresponding empty A*B sub-grid can be found, or "N" otherwise.

Sample Input

1
3 3
1 1 1
0 0 0
1 0 0
5
1 1
1 3
3 1
2 2
2 3

Sample Output

Y
Y
N
Y
N

Author

HYNU 题目说了一大堆，其实主要就是后面的有用，给定一个n*m的矩阵和k个询问，问是否存在一个全为0的子矩阵。是输出Y，否则输出N。 思路是预处理出所有满足条件的子矩阵，然后查询的时候就可以在O（1）时间得出，预处理跟最大矩形那题类似，也是枚举每一行，每行上方就是一个最大矩形问题，然后不用更新最大值，只是用一个标记数组把把这个矩形标记为1即可，表示这个矩形存在，这样处理完后只是得出了大矩形的位置，但是还需要更新小的矩形，这样在枚举完后我单独用了两重循环遍历，把隐藏的求出来，就可以查询了。 
#include
  
   
#include
   
     #include
    
      using namespace std; const int N = 1000 + 10; int flag[N][N],map[N][N],f[N],ff[N]; void solve(int ff[],int m) { stack
     







      s; int i,l,k,temp; ff[m+1]=-1; for(i=1;i<=m+1;i++) { if(s.empty()||ff[i]>ff[s.top()]) { s.push(i); } else if(ff[i]
      
       =1;i--) //遍历出小的矩形，并且是从后往前，一步步求出。 { for(j=m;j>=1;j--) flag[i][j]=flag[i][j]||flag[i+1][j]||flag[i][j+1]; } scanf("%d",&k); while(k--) { scanf("%d%d",&a,&b); if(flag[a][b]) printf("Y\n"); else printf("N\n"); } } return 0; }