4 条题解

  • 0
    @ 2025-3-30 10:42:36

    /* 本题求最小边长,使得最小边长围成的正方形能容纳指定数量的三叶草,首先三叶草的数量不多,但是数据范围很大, 因此第一步可以进行离散化。然后为了方便知道某一个矩形中的三叶草数量,可以采用前缀和的思想,然后要求边长的最小值,求最小值启发我们用二分来做。因此每次二分一个边长 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
      @ 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
        @ 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
          @ 2022-7-20 20:26:47
          /*
          本题求最小边长,使得最小边长围成的正方形能容纳指定数量的三叶草,首先三叶草的数量不多,但是数据范围很大, 因此第一步可以进行离散化。然后为了方便知道某一个矩形中的三叶草数量,可以采用前缀和的思想,然后要求边长的最小值,求最小值启发我们用二分来做。因此每次二分一个边长 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;
          }
          
          
        • 1

        信息

        ID
        32
        时间
        1000ms
        内存
        512MiB
        难度
        5
        标签
        递交数
        241
        已通过
        90
        上传者