OpenJudgeNOI2.17623:五户共井问题-创新互联

【题目链接】

OpenJudge NOI 2.1 7623:五户共井问题

成都创新互联专注于中大型企业的成都网站设计、成都做网站和网站改版、网站营销服务,追求商业策划与数据分析、创意艺术与技术开发的融合,累计客户上千,服务满意度达97%。帮助广大客户顺利对接上互联网浪潮,准确优选出符合自己需要的互联网运用,我们将一直专注成都品牌网站建设和互联网程序开发,在前进的路上,与客户一起成长!【题目考点】 1. 枚举 【解题思路】

设井深为h,A、B、C、D、E家的绳长分别为a、b、c、d、e。
把输入的k自己乘以100,从以米为单位转为以厘米为单位。
先想最直接的枚举思路

  • 枚举对象:h, a, b, c, d, e
  • 枚举范围:
    1 ≤ h ≤ k 1\le h \le k 1≤h≤k
    1 ≤ a , b , c , d , e ≤ h 1\le a , b, c, d, e \le h 1≤a,b,c,d,e≤h
  • 判断条件:同时满足:
    a ⋅ n 1 + b = h a\cdot n_1 + b = h a⋅n1​+b=h,
    b ⋅ n 2 + c = h b\cdot n_2 + c = h b⋅n2​+c=h
    c ⋅ n 3 + d = h c\cdot n_3 + d = h c⋅n3​+d=h
    d ⋅ n 4 + e = h d\cdot n_4 + e = h d⋅n4​+e=h
    e ⋅ n 5 + a = h e\cdot n_5 + a = h e⋅n5​+a=h
    且a, b, c, d, e互不相等

若以这种方法做枚举,那么h要从1枚举到k(k单位为厘米时,大2000),a~e都要从1枚举到h,大枚举次数为 1 5 + 2 5 + . . . + 200 0 5 1^5+2^5+...+2000^5 15+25+...+20005,该枚举次数显然是不可接受的。

观察该方程组,共有6个未知数5个方程,只要确定其中一个未知数后,就可以解方程。不过那样解方程比较麻烦。比较方便的做法是确定两个未知数。

  • 枚举对象:h, a

  • 枚举范围:
    1 ≤ h ≤ k 1\le h \le k 1≤h≤k
    因为 b > 0 b>0 b>0,且 a ⋅ n 1 + b = h a\cdot n_1 + b = h a⋅n1​+b=h,所以有 a > 0 a >0 a>0且 a ⋅ n 1 < h a\cdot n1< h a⋅n1h与a的值已确定:

    1. 根据 a ⋅ n 1 + b = h a\cdot n_1 + b = h a⋅n1​+b=h就可以确定b的值。
    2. 根据 b ⋅ n 2 + c = h b\cdot n_2 + c = h b⋅n2​+c=h就可以确定c的值。
    3. 根据 c ⋅ n 3 + d = h c\cdot n_3 + d = h c⋅n3​+d=h就可以确定d的值。
    4. 根据 d ⋅ n 4 + e = h d\cdot n_4 + e = h d⋅n4​+e=h就可以确定e的值。
  • 判断条件:
    判断 e ⋅ n 5 + a = h e\cdot n_5 + a = h e⋅n5​+a=h是否成立。且a, b, c, d, e互不相等。

当k为2000, n 1 n_1 n1​为1时,总枚举次数为 1 + 2 + . . . + 2000 = ( 1 + 2000 ) ∗ 2000 / 2 = 2001000 1+2+...+2000 = (1+2000)*2000/2=2001000 1+2+...+2000=(1+2000)∗2000/2=2001000,可以接受。

【题解代码】 解法1:枚举
#includeusing namespace std;
int main()
{int k, n1, n2, n3, n4, n5;
	cin >>k >>n1 >>n2 >>n3 >>n4 >>n5;
	k *= 100;//单位变为厘米 
	for(int h = 1; h<= k; ++h)
		for(int a = 1; a*n1< h; ++a)
		{	int b = h-a*n1, c = h-b*n2, d = h-c*n3, e = h-d*n4;
			if(a != b && a != c && a != d && a != e && b != c && 
			   b != d && b != e && c != d && c != e && d != e && e*n5+a == h)
			{		cout<< h<< ' '<< a<< ' '<< b<< ' '<< c<< ' '<< d<< ' '<< e; 
				return 0;
			}
	}
	cout<< "not found";
	return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享标题:OpenJudgeNOI2.17623:五户共井问题-创新互联
路径分享:http://ybzwz.com/article/ihgjg.html