[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$ 需要从 $2$ 开始枚举，因为 $c<a$ 需要给 $c$ 留位置。
为了满足题意，一定有 $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$ 的最小值。
最后，一定要记得在每一层循环中及时跳过不满足要求的数，以减少执行下一层循环的次数。

代码实现

CPP

#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证明

警示

如果你像这样只有少量分数，说明优化时把正确答案剪枝掉了，导致少答案。
如果你像这样拿到五十一分，将流同步关闭，即可多拿一分。

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

文章操作

[ROIR 2020]区域规划-题解

前言

思路

优化细节

代码实现

警示

相关推荐

评论

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