4 条题解

  • 1
    @ 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
      @ 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;
      

      }

      • -1
        @ 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;
        

        }

        • 1

        信息

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