Skip to content

内网 2085马农

Description

在观看完战马检阅之后，来自大草原的两兄弟决心成为超级“马农”，专门饲养战马。

兄弟两回到草原，将可以养马的区域，分为N*N的单位面积的正方形，并实地进行考察，归纳出了每个单位面积可以养马所获得的收益。接下来就要开始规划他们各自的马场了。

首先，两人的马场都必须是矩形区域。同时，为了方便两人互相照应，也为了防止马匹互相走散，规定两个马场的矩形区域相邻，且只有一个交点。最后，互不认输的两人希望两个马场的收益相当，这样才不会影响他们兄弟的感情。

现在，兄弟两找到你这位设计师，希望你给他们设计马场，问共有多少种设计方案。

Input

第一行一个整数N，表示整个草原的大小为N*N。

接下来N行，每行N个整数A(i,j)，表示第i行第j列的单位草地的收成。（注意：收益可能是负数，养马也不是包赚的，马匹也可能出现生病死亡等意外。）

1<=N<=50
-1000<A(i,j)<1000

Output

输出符合两人要求的草原分配方案数。

Sample Input

3 1 2 3 4 5 6 7 8 9

Sample Output

2

Hint

Source

2014宁波初中 T2


宁波镇海中学的罗方炜给我们组的一场比赛。

此题主要靠技巧。枚举中心点，然后用数组hash。注意数组清空复杂度很大，每次清空必定超时。应该用一个栈来记录更改的地方，直接赋0.

#include&lt;map&gt;
#include&lt;set&gt;
#include&lt;cmath&gt;
#include&lt;stack&gt;
#include&lt;queue&gt;
#include&lt;string&gt;
#include&lt;cstdio&gt;
#include&lt;vector&gt;
#include&lt;cctype&gt;
#include&lt;cassert&gt;
#include&lt;utility&gt;
#include&lt;numeric&gt;
#include&lt;cstring&gt;
#include&lt;iostream&gt;
#include&lt;algorithm&gt;
using namespace std;
#define pr pair
#define PR pair&lt;int,int&gt;
#define MP make_pair
#define SI(x) set&lt;x&gt;::iterator
#define VI(x) vector&lt;x&gt;::iterator
#define MI(x,y) map&lt;x,y&gt;::iterator
#define SRI(x) set&lt;x&gt;::reverse_iterator
#define VRI(x) vector&lt;x&gt;::reverse_iterator
#define MRI(x,y) map&lt;x,y&gt;::reverse_iterator
#define F first
#define S second
#define Sz(x) (int)x.size()
#define clrQ(x) while(!x.empty)x.pop();
#define clr(x,y) memset(x,y,sizeof(x));
#if defined (_WIN32) || defined (__WIN32) || defined (WIN32) || defined (__WIN32__)
#define LL __int64
#define LLS "%" "I" "6" "4" "d"
#define LLU "%" "I" "6" "4" "u"
#define LL_MAX _I64_MAX
#else
#define LL long long
#define LLS "%" "l" "l" "d"
#define LLU "%" "l" "l" "u"
#define LL_MAX _I64_MAX
#endif
const int inf = ~0u &gt;&gt; 1;
const LL lnf = ~0ull &gt;&gt; 1;
/*start*/
#define N 55
#define M 2500000
int f[N][N],a[N][N];
int h[M&lt;&lt;1|1];
int st[N*N],top;
int n,m;
int main(int argc, char **argv) {
    while(~scanf("%d",&amp;n)){
        for (int i = 1; i &lt;= n; ++i) {
            for (int j = 1; j &lt;= n; ++j) {
                scanf("%d",&amp;a[i][j]);
                f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
            }
        }
        int res=top=0;
        for (int x = 1; x &lt;= n; ++x) {
            for (int y = 1; y &lt;= n; ++y) {
                for (int i = 1; i &lt;= x; ++i) {
                    for (int j = 1; j &lt;= y; ++j) {
                        st[top++]=f[x][y]-f[x][j-1]-f[i-1][y]+f[i-1][j-1]+M;
                        h[st[top-1]]++;
                    }
                }
                for (int i = x+1; i &lt;= n; ++i) {
                    for (int j = y+1; j &lt;= n; ++j) {
                        res+=h[f[i][j]-f[i][y]-f[x][j]+f[x][y]+M];
                    }
                }

                while(top){
                    h[st[--top]]=0;
                }
                for (int i = x; i &lt;= n; ++i) {
                    for (int j = 1; j &lt;= y; ++j) {
                        st[top++]=f[i][y]-f[x-1][y]-f[i][j-1]+f[x-1][j-1]+M;
                        h[st[top-1]]++;
                    }
                }
                for (int i = 1; i &lt; x; ++i) {
                    for (int j = y+1; j &lt;= n; ++j) {
                        res+=h[f[x-1][j]-f[x-1][y]-f[i-1][j]+f[i-1][y]+M];
                    }
                }
                while(top){
                    h[st[--top]]=0;
                }
            }
        }
        printf("%d\n",res);
    }
}

Comments