题意：

给出一个矩阵，求这个矩阵中权值和第k小的长在xmin到n之间，宽在ymin到m之间的子矩阵。n，m≤1000，k≤250000。

题解：

首先求出长为xmin，宽为ymin的子矩阵放入优先队列，每次取出时如果该矩阵之前没有出现过（用set判重），则将其扩展并放入优先队列，输出第k个不重复的（这里指位置不重复的，权值可以相等）。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define inc(i,j,k) for(int i=j;i<=k;i++) 7 #define maxn 1010 8 using namespace std; 9 10 inline int read(){11     char ch=getchar(); int f=1,x=0;12     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();14     return f*x;15 }16 int sum[maxn][maxn],n,m,xmin,ymin,k,tot;17 struct nd{18     int x,y,l,c,v;19     bool operator < (const nd &a)const{20         if(v!=a.v)return v>a.v; if(x!=a.x)return x
          
           q; set
           
            st;25 int main(){26 n=read(); m=read(); xmin=read(); ymin=read(); k=read();27 inc(i,1,n)inc(j,1,m){ int x=read(); sum[i][j]=sum[i-1][j]-sum[i-1][j-1]+sum[i][j-1]+x;}28 inc(i,1,n-xmin+1)inc(j,1,m-ymin+1){29 q.push((nd){i,j,xmin,ymin,sum[i+xmin-1][j+ymin-1]-sum[i+xmin-1][j-1]-sum[i-1][j+ymin-1]+sum[i-1][j-1]});30 }31 while(!q.empty()){32 nd x=q.top(); q.pop(); if(st.find(x)!=st.end())continue;33 tot++; if(tot==k){printf("%d",x.v+1); break;} st.insert(x);34 if(x.x+x.l<=n)35 q.push((nd){x.x,x.y,x.l+1,x.c,sum[x.x+x.l][x.y+x.c-1]-sum[x.x+x.l][x.y-1]-sum[x.x-1][x.y+x.c-1]+sum[x.x-1][x.y-1]});36 if(x.y+x.c<=m)37 q.push((nd){x.x,x.y,x.l,x.c+1,sum[x.x+x.l-1][x.y+x.c]-sum[x.x+x.l-1][x.y-1]-sum[x.x-1][x.y+x.c]+sum[x.x-1][x.y-1]});38 if(x.x+x.l<=n&&x.y+x.c<=m)39 q.push((nd){x.x,x.y,x.l+1,x.c+1,sum[x.x+x.l][x.y+x.c]-sum[x.x+x.l][x.y-1]-sum[x.x-1][x.y+x.c]+sum[x.x-1][x.y-1]});40 }41 return 0;42 }
           
          
         
        
       
      
     

 

20161110