HDU多校第六场 1006 Faraway —— 分割空间 + 数学

本文主要是介绍HDU多校第六场 1006 Faraway —— 分割空间 + 数学，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    二维平面上有 $n$ 个点，且都满足
    $(|x_i-x_e|+|y_i-y_e|)$ $mod$ $k_i=t_i$
    求 $(x_e,y_e)$ 的个数

解题思路：

    枚举 $n^2$ 个区域时
    对于每个区域，只需要枚举 $60\ast 60$ 的大小即可
    然后计算该区域内的合法点数

核心：枚举区域，思维数学

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
int T, n, m, tx[15], ty[15];
struct node{int x, y, k, t;
} a[15];bool check(int x, int y){for(int i=1; i<=n; i++)if((abs(a[i].x-x) + abs(a[i].y-y)) % a[i].k != a[i].t)return false;return true;
}ll cal(int l, int r){ll cnt = r - l - 1;if(cnt < 0) return 0;return cnt / 60 + 1;
}int main() {scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);for(int i=1; i<=n; i++){scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].k, &a[i].t);tx[i] = a[i].x, ty[i] = a[i].y;}tx[n+1] = ty[n+1] = m + 1;sort(tx+1, tx+2+n);sort(ty+1, ty+2+n);int cnt1 = unique(tx+1, tx+2+n) - tx - 1;int cnt2 = unique(ty+1, ty+2+n) - ty - 1;ll ans = 0;for(int nx=0; nx<cnt1; nx++)for(int ny=0; ny<cnt2; ny++)for(int i=0; i<60; i++)for(int j=0; j<60; j++)if(check(tx[nx]+i, ty[ny]+j))ans += cal(tx[nx]+i, tx[nx+1]) * cal(ty[ny]+j, ty[ny+1]);printf("%lld\n", ans);}
}

这篇关于HDU多校第六场 1006 Faraway —— 分割空间 + 数学的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---