4 条题解
-
0
/* 本题求最小边长，使得最小边长围成的正方形能容纳指定数量的三叶草，首先三叶草的数量不多，但是数据范围很大， 因此第一步可以进行离散化。然后为了方便知道某一个矩形中的三叶草数量，可以采用前缀和的思想，然后要求边长的最小值，求最小值启发我们用二分来做。因此每次二分一个边长 mid，然后枚举图中所有边长为 mid 的正方形，如果存在一个正方形中的三叶草数量满足要求，可以尝试缩小边长，二分左区间。否则二分右区间。枚举过程中用二维前缀和直接线性求三叶草数量即可。 */
#include #include #include
using namespace std;
const int N = 1010; struct node { int x,y; }nodes[10010]; int n, m, k; int s[N][N]; int cnt = 1; int len; int nums[N]; int find(int x) //离散化 { int l = 1, r = cnt-1; while(l < r) { int mid = l + r + 1 >> 1; if(nums[mid] <= x) l = mid; else r = mid - 1; } return r; } bool check(int mid) //判断边长为 mid 是否能包含 m 个三叶草 { for(int x1 = 1, x2 = 1; x2 < cnt; x2++) //枚举横坐标 { while(nums[x2] + 1 - nums[x1] > mid) x1++; for(int y1 = 1, y2 = 1; y2 < cnt; y2++) //枚举纵坐标 { while(nums[y2] + 1 - nums[y1] > mid) y1++; if(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] >= m) return true; } }
return false;}
int main() { scanf("%d%d", &m, &k); for(int i = 0; i < k; i++) { int x, y; scanf("%d%d", &x, &y); n = max(n, x), n = max(n, y); //记录边界 nums[++len] = x; nums[++len] = y; nodes[i] = (node){x, y}; //存储所有的点 } //坐标离散化 sort(nums + 1, nums + len + 1);
for(int i = 1; i <= len ; i++) if(nums[i] != nums[i-1]) nums[cnt++] = nums[i]; //标记所有位置上的三叶草数量 for(int i = 0; i < k; i++) { int x = find(nodes[i].x), y = find(nodes[i].y); s[x][y]++; } //初始化前缀和 for(int i = 1; i < cnt; i++) for(int j = 1; j < cnt; j++) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; //二分 int l = 1, r = n; int ans; while(l <= r) { int mid = l + r >> 1; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", ans); return 0;}
-
0
huangliheng LV 8 @ 2024-6-22 19:58:45
/* 本题求最小边长，使得最小边长围成的正方形能容纳指定数量的三叶草，首先三叶草的数量不多，但是数据范围很大， 因此第一步可以进行离散化。然后为了方便知道某一个矩形中的三叶草数量，可以采用前缀和的思想，然后要求边长的最小值，求最小值启发我们用二分来做。因此每次二分一个边长 mid，然后枚举图中所有边长为 mid 的正方形，如果存在一个正方形中的三叶草数量满足要求，可以尝试缩小边长，二分左区间。否则二分右区间。枚举过程中用二维前缀和直接线性求三叶草数量即可。 */
#include #include #include
using namespace std;
const int N = 1010; struct node { int x,y; }nodes[10010]; int n, m, k; int s[N][N]; int cnt = 1; int len; int nums[N]; int find(int x) //离散化 { int l = 1, r = cnt-1; while(l < r) { int mid = l + r + 1 >> 1; if(nums[mid] <= x) l = mid; else r = mid - 1; } return r; } bool check(int mid) //判断边长为 mid 是否能包含 m 个三叶草 { for(int x1 = 1, x2 = 1; x2 < cnt; x2++) //枚举横坐标 { while(nums[x2] + 1 - nums[x1] > mid) x1++; for(int y1 = 1, y2 = 1; y2 < cnt; y2++) //枚举纵坐标 { while(nums[y2] + 1 - nums[y1] > mid) y1++; if(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] >= m) return true; } }
return false;}
int main() { scanf("%d%d", &m, &k); for(int i = 0; i < k; i++) { int x, y; scanf("%d%d", &x, &y); n = max(n, x), n = max(n, y); //记录边界 nums[++len] = x; nums[++len] = y; nodes[i] = (node){x, y}; //存储所有的点 } //坐标离散化 sort(nums + 1, nums + len + 1);
for(int i = 1; i <= len ; i++) if(nums[i] != nums[i-1]) nums[cnt++] = nums[i]; //标记所有位置上的三叶草数量 for(int i = 0; i < k; i++) { int x = find(nodes[i].x), y = find(nodes[i].y); s[x][y]++; } //初始化前缀和 for(int i = 1; i < cnt; i++) for(int j = 1; j < cnt; j++) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; //二分 int l = 1, r = n; int ans; while(l <= r) { int mid = l + r >> 1; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", ans); return 0;}
-
0
huangjiasheng LV 9 @ 2022-7-20 20:27:06
/* 本题求最小边长，使得最小边长围成的正方形能容纳指定数量的三叶草，首先三叶草的数量不多，但是数据范围很大， 因此第一步可以进行离散化。然后为了方便知道某一个矩形中的三叶草数量，可以采用前缀和的思想，然后要求边长的最小值，求最小值启发我们用二分来做。因此每次二分一个边长 mid，然后枚举图中所有边长为 mid 的正方形，如果存在一个正方形中的三叶草数量满足要求，可以尝试缩小边长，二分左区间。否则二分右区间。枚举过程中用二维前缀和直接线性求三叶草数量即可。 */ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; struct node { int x,y; }nodes[10010]; int n, m, k; int s[N][N]; int cnt = 1; int len; int nums[N]; int find(int x) //离散化 { int l = 1, r = cnt-1; while(l < r) { int mid = l + r + 1 >> 1; if(nums[mid] <= x) l = mid; else r = mid - 1; } return r; } bool check(int mid) //判断边长为 mid 是否能包含 m 个三叶草 { for(int x1 = 1, x2 = 1; x2 < cnt; x2++) //枚举横坐标 { while(nums[x2] + 1 - nums[x1] > mid) x1++; for(int y1 = 1, y2 = 1; y2 < cnt; y2++) //枚举纵坐标 { while(nums[y2] + 1 - nums[y1] > mid) y1++; if(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] >= m) return true; } } return false; } int main() { scanf("%d%d", &m, &k); for(int i = 0; i < k; i++) { int x, y; scanf("%d%d", &x, &y); n = max(n, x), n = max(n, y); //记录边界 nums[++len] = x; nums[++len] = y; nodes[i] = (node){x, y}; //存储所有的点 } //坐标离散化 sort(nums + 1, nums + len + 1); for(int i = 1; i <= len ; i++) if(nums[i] != nums[i-1]) nums[cnt++] = nums[i]; //标记所有位置上的三叶草数量 for(int i = 0; i < k; i++) { int x = find(nodes[i].x), y = find(nodes[i].y); s[x][y]++; } //初始化前缀和 for(int i = 1; i < cnt; i++) for(int j = 1; j < cnt; j++) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; //二分 int l = 1, r = n; int ans; while(l <= r) { int mid = l + r >> 1; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", ans); return 0; } -
0
/* 本题求最小边长，使得最小边长围成的正方形能容纳指定数量的三叶草，首先三叶草的数量不多，但是数据范围很大， 因此第一步可以进行离散化。然后为了方便知道某一个矩形中的三叶草数量，可以采用前缀和的思想，然后要求边长的最小值，求最小值启发我们用二分来做。因此每次二分一个边长 mid，然后枚举图中所有边长为 mid 的正方形，如果存在一个正方形中的三叶草数量满足要求，可以尝试缩小边长，二分左区间。否则二分右区间。枚举过程中用二维前缀和直接线性求三叶草数量即可。 */ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; struct node { int x,y; }nodes[10010]; int n, m, k; int s[N][N]; int cnt = 1; int len; int nums[N]; int find(int x) //离散化 { int l = 1, r = cnt-1; while(l < r) { int mid = l + r + 1 >> 1; if(nums[mid] <= x) l = mid; else r = mid - 1; } return r; } bool check(int mid) //判断边长为 mid 是否能包含 m 个三叶草 { for(int x1 = 1, x2 = 1; x2 < cnt; x2++) //枚举横坐标 { while(nums[x2] + 1 - nums[x1] > mid) x1++; for(int y1 = 1, y2 = 1; y2 < cnt; y2++) //枚举纵坐标 { while(nums[y2] + 1 - nums[y1] > mid) y1++; if(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] >= m) return true; } } return false; } int main() { scanf("%d%d", &m, &k); for(int i = 0; i < k; i++) { int x, y; scanf("%d%d", &x, &y); n = max(n, x), n = max(n, y); //记录边界 nums[++len] = x; nums[++len] = y; nodes[i] = (node){x, y}; //存储所有的点 } //坐标离散化 sort(nums + 1, nums + len + 1); for(int i = 1; i <= len ; i++) if(nums[i] != nums[i-1]) nums[cnt++] = nums[i]; //标记所有位置上的三叶草数量 for(int i = 0; i < k; i++) { int x = find(nodes[i].x), y = find(nodes[i].y); s[x][y]++; } //初始化前缀和 for(int i = 1; i < cnt; i++) for(int j = 1; j < cnt; j++) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; //二分 int l = 1, r = n; int ans; while(l <= r) { int mid = l + r >> 1; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", ans); return 0; }-
踩踩踩
-
jinhongxian
LV 7
@ 2025-3-30 10:42:36
- 1