题解：P9788 [ROIR 2020] 区域规划 (Day2)

Yzh929 · 2025-08-15 16:42:04 · 题解

[ROIR 2020]区域规划-题解

前言

这道题总体思路还是很好想的，但是为了不超时还是有很多剪枝的细节需要注意，非常锻炼对这些关系的理解。

思路

本题关键信息是 a\times b-c\times d=n 以及 a\ne x 和 b\ne x 那我们很直接能想到需要枚举，因为式子需要确定，所以只能有一个未知数被其他表示，因此，就不得不枚举其他 3 个未知数了。
前置推导，根据题意可得 c\times d=a\times b-n 和 n<a\times b\le n^2。

优化细节

• 为了满足题意，一定有 a\times b>n，则 b>n\div a 那么就有了 b 的最小值。
• 因为 d=\frac{a\times b-n}{c}，显然只有当 c>\frac{a\times b-n}{b} 时才有 d>b。这便是 c 的最小值。

• 最后，一定要记得在每一层循环中及时跳过不满足要求的数，以减少执行下一层循环的次数。

  代码实现

  
  #include<iostream>//不推荐用万能头，经常会出现奇奇怪怪的错误 
  #include<cmath>
  using namespace std;
  int n,x,ans;
  int main() {
  ios::sync_with_stdio(false);//关闭流同步，增加读入输出速度
  cin.tie(NULL),cout.tie(NULL);
  cin>>n>>x;
  for(int a=2; a<=n; a++) { //a最小为2因为还要给c留地方
      if(a==x) continue;
      for(int b=(n+2)/a  ; b<=n; b++) { // 又+1是为了不用上取整函数
          if(b==x||a*b<=n) continue;
          int cd=a*b-n;//cd表示c*d应该的积，提前表示方便下面处理
          if(cd<1) continue;
          for(int c=max(1,(cd)/b); c<a; c++) { //c 必须大于 cd / b 才能保证 d < b。因此 c 的理论下限是 cd / b 的下一个整数。
              if(cd%c!=0) continue;
              int d=cd/c;
              if(d>=b) continue;
              ans++;//上面把不满足要求的都跳过了，放心加就行
  
          }
  
      }
  }
  cout<<ans<<'\n';
  return 0;
  }
  //完结撒花~ 

[AC证明](https://www.luogu.com.cn/record/231135181)
## 警示
- 如果你[像这样](https://www.luogu.com.cn/record/231121361)只有少量分数，说明优化时把正确答案剪枝掉了，导致少答案。
- 如果你[像这样](https://www.luogu.com.cn/record/231114474)拿到五十一分，将流同步关闭，即可多拿一分。