本文主要是介绍UVA 12508 - Triangles in the Grid(计数问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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 <stdio.h>
#include <string.h>
#include <algorithm>
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;
}
这篇关于UVA 12508 - Triangles in the Grid(计数问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!