首页 > 其他分享 >P1149 [NOIP2008 提高组] 火柴棒等式

P1149 [NOIP2008 提高组] 火柴棒等式

时间:2024-04-09 22:34:25浏览次数:22  
标签:11 10 数字 int NOIP2008 等式 火柴 P1149

P1149 [NOIP2008 提高组] 火柴棒等式

题目

给你 \(n\) 根火柴棍,你可以拼出多少个形如 \(A+B=C\) 的等式?等式中的 \(A\)、\(B\)、\(C\) 是用火柴棍拼出的整数(若该数非零,则最高位不能是 \(0\))。用火柴棍拼数字 \(0\sim9\) 的拼法如图所示:

注意:

  1. 加号与等号各自需要两根火柴棍;
  2. 如果 \(A \ne B\),则 \(A+B=C\) 与 \(B+A=C\) 视为不同的等式(\(A,B,C \ge 0\));
  3. \(n\) 根火柴棍必须全部用上。

输入

一个整数 \(n(1 \leq n\leq 24)\)。

输出

一个整数,能拼成的不同等式的数目。

样例 1

输入

14

输出

2

样例 2

输入

18

输出

9

提示

【输入输出样例 1 解释】

\(2\) 个等式为 \(0+1=1\) 和 \(1+0=1\)。

【输入输出样例 2 解释】

\(9\) 个等式为

\(0+4=4\)、\(0+11=11\)、\(1+10=11\)、\(2+2=4\)、\(2+7=9\)、\(4+0=4\)、\(7+2=9\)、\(10+1=11\)、\(11+0=11\)。


思路一

首先,根据题意可知,火柴棒的个数最多为 \(24\) 根,除去“+”和“=”占用的 \(4\) 根火柴棍,那么剩下 \(20\) 根火柴棍。在 \(0\) 到 \(9\) 这 \(10\) 个数字中,可以看到数字 \(1\) 需要用到的火柴棍最少,只需要 \(2\) 根火柴棍。所以 \(20\) 根火柴棍最多能组成 \(10\) 个 \(1\)。在 \(4\) 位数里 \(1111\) 用的火柴棍最少也要 \(8\) 个,所以构造的形如 \(a+b=c\) 的火柴棍等式就转换为“\(1111+x=(1111+x)\)”,在这个等式中 \(a,b,c\) 的任意一个数都不能超过 \(1111\),这里设 \(n=1111\)。假设已知等式的加数,该加数的范围是 \(0\) 到 \(n\),接下来分别枚举 \(a,b\) 的值。\(c\) 可以通过 \(a+b\) 算出来,无须枚举。约束条件是:\(a\) 所使用的火柴棍的根数加上 \(b\) 所使用的火柴棍的根数,再加上 \(c\) 所使用的火柴棍的根数,如果恰好等于 \(m-4\),则成功地找出了一组等式。

代码

#include <bits/stdc++.h>

using namespace std;

int a, b, c, m, sum;

int f(int x) // 用来计算一个数需要用火柴棍的总数
{
	int s = 0, f[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
	while (x / 10 != 0)
	{
		s += f[x % 10];
		x /= 10;
	}
	s += f[x]; // 加上最后的数字对应的根数
	return s; // 返回火柴棍的总跟数
}

int main()
{
	cin >> m;
	for (a = 0; a <= 1111; a ++ )
	{
		for (b = 0; b <= 1111; b ++ )
		{
			c = a + b;
			if (f(a) + f(b) + f(c) == m - 4)
				sum ++;
		}
	}
	cout << sum << '\n';
	return 0;
}

思路二

上述算法的时间复杂度位 \(O(n^2 \times\)数字分离的次数\()\),由于数字最大是 \(1111\),每个数字分离的次数最大是 \(4\),完整算法 \(1s\) 之内可以输出答案。但是由于每个数字都要分离计算数字需要的所有火柴棍数目,这样导致很多数字重复计算,加大了时间复杂度。思考之后可以将 \(0\) 到 \(2222\) 的所有整数需要的火柴棒数目预处理保存在数组中。那么难点是如何更快速地预处理出 \(0\) 到 \(2222\) 中所有数字的火柴棒数目,可以使用递推算法。设 \(s \lbrack i \rbrack\) 数组表示数字 \(i\) 需要的火柴棒数目,那么 \(s \lbrack i \rbrack = s \lbrack i/10 \rbrack + s \lbrack i \% 10 \rbrack\),时间复杂度是 \(O(n)\)。整个算法总时间是 \(O(n^2)+O(n)\),更为优秀。

代码

#include <bits/stdc++.h>

using namespace std;

int f[2500] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}, a, b, c, m, sum;

int main()
{
	cin >> m;
	for (int i = 10; i <= 2222; i ++ )
		f[i] = f[i / 10] + f[i % 10];
	for (a = 0; a <= 1111; a ++ ) // 枚举 a 和 b
	{
		for (b = 0; b <= 1111; b ++ )
		{
			c = a + b;
			if (f[a] + f[b] + f[c] == m - 4)
				sum ++;
		}
	}
	cout << sum << '\n';
	return 0;
}

标签:11,10,数字,int,NOIP2008,等式,火柴,P1149
From: https://www.cnblogs.com/IronMan-PZX/p/18125026

相关文章

  • P1149 [NOIP2008 提高组] 火柴棒等式
    目描述给你 n 根火柴棍,你可以拼出多少个形如A+B=C 的等式?等式中的 A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 00)。用火柴棍拼数字 0∼90∼9 的拼法如图所示:注意:加号与等号各自需要两根火柴棍;如果A=B,则+B=C 与B+A=C 视为不同的等式(≥0A,B,C≥......
  • 均值不等式
    均衡不等式这个名字霸气泄露,但学起来依然霸气泄露。算数平均值:若有正数a,b,则\(\frac{a+b}{2}\)是\(a,b\)的算术平均值。几何平均值:顾名思义,一看就是有关\(ab\)的。若有\(a,b\),则\(\sqrt{ab}\)是\(a,b\)的几何平均值。正题:均衡不等式娱乐上网搜了搜,是哪个闲人......
  • 洛谷 P1006 [NOIP2008 提高组] 传纸条
    题意:传纸条,跟方格取数一样,但是两条路径不能有重复的。思路:还是一样的走,但是x1跟x2不能相等,包括现在跟上一个状态。总结:看了题解,发现题解大多数都是逻辑不正确的,更有离谱的是数组范围都不加特判,数组访问越界但是可以ac的情况,数据太烂了,放个自以为正确的思路吧,发现之前自己提交的......
  • P1149 [NOIP2008 提高组] 火柴棒等式
    题目链接:本题比较重要的点在于判断加数的范围,即枚举的范围大小。由于题目已知\(n\leqslant24\),且用数字\(1\)拼成的数尽可能大。由于\(1111+1=1112\)已经用了\(25\)根小棒,已经超过了题目\(24\)根小棒的数据范围,所以上界为\(1111\)。#include<cstdio>inta[10]=......
  • 数学入门——均值不等式 学习笔记
    数学入门——均值不等式学习笔记简化形式若\(a,b>0\),则:\[\dfrac{2}{\dfrac{1}{a}+\dfrac{1}{b}}\le\sqrt[2]{ab}\le\dfrac{a+b}{2}\le\sqrt[2]{\dfrac{a^2+b^2}{2}}\]理解方式:https://www.bilibili.com/video/BV1Nf4y1G7xV基本形式若\(a,b>0\),则:\[\dfrac{n}{\dfrac{......
  • 【洛谷】 P1006 [NOIP2008提高组]传纸条
    题目描述小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排坐成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,......
  • C++ [NOIP2008 普及组] ISBN 号码
    文章目录一、题目描述[NOIP2008普及组]ISBN号码题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2提示二、参考代码一、题目描述[NOIP2008普及组]ISBN号码题目描述每一本正式出版的图书都有一个ISBN号码与之对应,IS......
  • P1055 [NOIP2008 普及组] ISBN 号码
    P1055[NOIP2008普及组]ISBN号码[NOIP2008普及组]ISBN号码题目描述每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括\(9\)位数字、\(1\)位识别码和\(3\)位分隔符,其规定格式如x-xxx-xxxxx-x,其中符号-就是分隔符(键盘上的减号),最后一位是识别码,例如0-6......
  • 常用不等式题目解法
    问题:已知${ x^{2}+y^{2}-xy=3}$,求${x+y}$的最大值?解法1(万能k法):设${k=x+y}$,则${x=k-y}$,可知:$${\left(k-y\right)^{2}+y^{2}-\left(k-y\right)y=3 }$$化简:$${3y^{2}-3ky+\left(k^{2}-3\right)=0}$$这是已知条件,${y}$必定有解。所以根据一元二次方程根判......
  • lc2426 满足不等式的数对个数
    给定两个大小为n的数组nums1和nums2以及整数diff,统计满足以下条件的数对(i,j)的个数:0<=i<j<=n-1,并且nums1[i]-nums1[j]<=nums2[i]-nums2[j]+diff。2<=n<=1e5;-1e4<=nums1[i],nums2[i]<=1e4;-1e4<=diff<=1e4先对条件做下变形,将下标相同的移到同一侧,得到:nums1[i]-nums2[i]<=nums......