SRM542DIV2

一道DIV2里面500pt的题目想了3天还是没有想出来，这是什么水平。。。。太菜了，弱爆了，该怎么办呢？怎么样才能成为高手呢？ 250pt： 题意：题意很简单，就是说兔子之间的合作问题，每对兔子间有个权，最后求平均。 思路：水题，求出兔子的总对数和权总和，

一道DIV2里面500pt的题目想了3天还是没有想出来，这是什么水平。。。。太菜了，弱爆了，该怎么办呢？怎么样才能成为高手呢？

250pt：

题意：题意很简单，就是说兔子之间的合作问题，每对兔子间有个权值，最后求平均值。

思路：水题，求出兔子的总对数和权值总和，再除就可以了，没什么技术含量。代码就不贴了。

500pt：

题意：

给一个X*Y的矩阵，规定矩阵里面的两点（x1,y1）和（x2,y2）之间的距离为|x1-x2|+|y1-y2|,给出你一个三角形的最小周长和最大周长，求这个周长范围内的三角形有多少个。要求：三角形的三个点的坐标必须是整点坐标，且三个点的横坐标不能有相同，纵坐标不能有相同。

思路：因为是绝对值，容易知道，其实三角形的周长就是一个矩形的周长。然后从矩形考虑，三角形的三个点必定可以在一个矩形上，有两种情况。一种是有一个顶点在矩形顶点上，另外两个顶点在矩形边上，顶点有四种情况，故可形成4个三角形；另一种情况是两个顶点矩形在对角线上，另外一个顶点在矩形内部，这样可以形成2个三角形。一个x*y的矩形可以形成6*（x-1）*(y-1)个三角形，一个X*Y的矩形可以形成（X-x）*(Y-y)个矩形，所以共可以构成6*(x-1)*(y-1)*(X-x)*(Y-y)个三角形。

有了这样的思路后，就容易多了，枚举就行了，计算过程中注意取余，因为会溢出。

代码：

long long mod = 1000000007;
int n,m;
class PatrolRoute
{
        public:
        int countRoutes(int X, int Y, int minT, int maxT)
        {
            int i,j,k;
            long long total = 0;
            for(int ix = 2;ix < X;ix++)
            {
                for(int iy = 2;iy < Y;iy++)
                {
                    int len = 2*(ix+iy);
                    if(len < minT || len >maxT)
                    {
                        continue;
                    }
                    long long tmp = 6*(ix-1)*(iy-1);
                    long long ans = tmp * (X-ix) * (Y-iy);
                    total += ans;
                    if(total >mod)
                    {
                        total = total % mod;
                    }
                }
            }
            return (int)total;
        }
        //$TESTCODE$
};