12508 - Triangles in the Grid

题目链接

题意：给定一个n?m格子的矩阵，然后给定A，B，问能找到几个面积在A到B之间的三角形。

思路：枚举每一个子矩阵，然后求[0,A]的个数减去[0,B]的个数就是答案，然后对于每个子矩阵个数很好求为(n?r+1)?(m?c+1)。关键在于怎么求每个子矩阵的符合个数。

想了好久，参考别人题解才想出来，分3种情况讨论：
1、一个点在矩形顶点，另外两点对应在顶点的另外两边上。
2、两个点在顶点上，另外一点在对边上。
3、三个点都在顶点上
然后分别去计算求和，具体的过程比较麻烦，在纸上多画画一边就能得到一个o(N)的方法，大概是枚举一个在竖直边上的位置，横的位置利用公式运算一步求解，这样时间复杂度是可以接受的

代码：

#include 
   
     #include 
    
      #include 
     
       using namespace std; int t; long long n, m, a, b; long long solve(long long limit) { long long ans = 0; for (long long r = 1; r <= n; r++) { for (long long c = 1; c <= m; c++) { long long count = 0; long long up, down; if (r * c <= limit) count += 2 * (r - 1 + c - 1); for (long long x = 0; x <= r; x++) { up = min(c, (x * c + limit) / r); long long tmp = x * c - limit; if (tmp <= 0) down = 0; else down = (tmp - 1) / r + 1; if (down <= up) count += 2 * (up - down + 1); } for (long long x = 1; x < r; x++) { long long s = (r * c - x); if (s <= limit) count += 4 * (c - 1); else count += 4 * ((c - 1) - min((s - limit) / x + ((s - limit) % x != 0), c - 1)); } ans += count * (n - r + 1) * (m - c + 1); } } return ans; } int main() { scanf("%d", &t); while (t--) { scanf("%lld%lld%lld%lld", &n, &m, &a, &b); a <<= 1; b <<= 1; if (a == 0) a = 1; printf("%lld\n", solve(b) - solve(a - 1)); } return 0; }