[折腾笔记] 洛谷P1149-火柴棒等式 AC记_给你n根火柴棍,你可以拼出多少个形如“a+b=c”的等式?-程序员宅基地

技术标签: 算法  学术  笔记  OI  

原题链接: https://www.luogu.org/problem/P1149

题面简述:

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

img

注意:

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

思路:

等式可能的情况:

x + y = z x + y = z x+y=z

x x + y y = z z xx+yy=zz xx+yy=zz

x x x + y y y = z z z xxx+yyy=zzz xxx+yyy=zzz

x x x x + y y y y = z z z z xxxx+yyyy=zzzz xxxx+yyyy=zzzz

为啥这么说呢?因为计算在极端条件 n = 24 n = 24 n=24,的情况下,最高位数是:

24 ÷ 2 = 12 24\div 2=12 24÷2=12 (如果全部摆 1 1 1的话,可以摆 12 12 12 1 1 1) 12 ÷ 3 = 4 12\div 3=4 12÷3=4 一共有 3 3 3个数,于是最多 4 4 4位。


于是,我们大可枚举,因为枚举的话再加上优化,不会超时所以,就可以写出如下代码:

#include <bits/stdc++.h>
using namespace std; 
int s[] = {
    6,2,5,5,4,5,6,3,7,6};
int t = 4;
int ans = 0;
bool judge(int a,int b,int c,int n) {
    
    int p = 0;
    string d = to_string(a),e = to_string(b),f = to_string(c);
    for(int i = 0;i<d.length();++i) p+=s[d[i]-'0'];
    for(int i = 0;i<e.length();++i) p+=s[e[i]-'0'];
    for(int i = 0;i<f.length();++i) p+=s[f[i]-'0'];
    if(p==n) {
    
        return 1;
    }
    return 0;
}
int main() {
    
	int n;
	cin>>n;
	n-=4;
	for(int i = 0;i<=9999;++i) {
    
        for(int j = 0;j<=9999;++j) {
    
            int k = i+j;
            if(i+j==k&&judge(i,j,k,n)) {
    
                ans++;
            }
        }
    }
	cout<<ans<<endl;
} 

另外之前还犯了个错误:

#include <bits/stdc++.h>
using namespace std; 
int s[] = {
    6,2,5,5,4,5,6,3,7,6};
int t = 4;
int ans = 0;
bool judge(int a,int b,int c,int n) {
    
    int p = 0;
    string d = to_string(a),e = to_string(b),f = to_string(c);
    for(int i = 0;i<d.length();++i) p+=s[d[i]-'0'];
    for(int i = 0;i<e.length();++i) p+=s[e[i]-'0'];
    for(int i = 0;i<f.length();++i) p+=s[f[i]-'0'];
    if(p==n) {
    
        return 1;
    }
    return 0;
}
int main() {
    
	int n;
	cin>>n;
	n-=4;
	for(int i = 0;i<=n;++i) {
    
        for(int j = 0;j<=n;++j) {
    
            int k = i+j;
            if(i+j==k&&judge(i,j,k,n)) {
    
                ans++;
            }
        }
    }
	cout<<ans<<endl;
} 

这里只枚举到n不够。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45489562/article/details/99326255

智能推荐

华为数通HCNP学习历程分享-程序员宅基地

文章浏览阅读1.4k次。作为一名半路出家的网工,基础知识不扎实一直是我最大的缺点。不扎实怎么办呀?学习啊!因为线下学习时间不多,然后就想到网上学习这条路来了。在51CTO之前有看过其他的网络培训机构,试听了几家感觉都不怎样,后面朋友说51不错,那就来了。网站找报名老师要资料一看,直接就报名打款了,接下来就是学习学习再学习了,说到HCNP的学习,那得分为两部分,一是学真东西一是考证书。需要通过学习来提高自己的同学,那就要老..._华为hcip数通怎么学才好

【HarmonyOS】六脉神剑 | 元服务绝技之卡片刷新_元服务 数据刷新-程序员宅基地

文章浏览阅读436次。主动刷新就是应用(卡片提供方)通过updateForm接口去刷新卡片,可以使用的场景也很多,例如在卡片上添加刷新按钮,通过事件触发刷新卡片。3、周期性刷新IPC过程中,提供方是否存活:周期性刷新前卡片提供方是否存活都不会影响卡片周期性刷新,因为卡片周期性刷新是由卡片管理服务控制的,在需要刷新时如果卡片提供方不活动,卡片管理服务将会拉起提供方。例如可以通过监听亮屏广播(FA卡片可以接收鸿蒙侧的广播,无法接收安卓侧的广播),在广播的接收后,主动调用updateform接口进行卡片刷新。_元服务 数据刷新

第4课:PHP循环语句使用方法_<?php ¥sum=0 for{$x=0;$x<=5-程序员宅基地

文章浏览阅读256次。主讲老师:郭盛华PHP While循环:在您编写代码时,经常需要反复运行同一代码块。我们可以使用循环来执行这样的任务,而不是在脚本中添加若干几乎相等的代码行。在 PHP中,我们有以下循环语句:while (条件为真) {要执行的代码;}实例<?php$x=1;while($x<=5) {echo "这个数字是:$x<br&g..._<?php ¥sum=0 for{$x=0;$x<=5</div>

JVM参数OmitStackTraceInFastThrow导致的异常栈信息不见了-程序员宅基地

文章浏览阅读216次。2019独角兽企业重金招聘Python工程师标准>>> ..._omitstacktraceinfastthrow 优化后的异常会在哪里呢

npm init -y nodejs 项目初始化-程序员宅基地

文章浏览阅读1.4w次,点赞12次,收藏32次。npm init -y-y 的含义:yes的意思,在init的时候省去了敲回车的步骤,生成的默认的package.jsonversion版本号,一般从0.1.0开始description描述keywords关键词用逗号隔开author名字加邮箱license UNLICENSE,一般不授权公用使用 npm 命令安装模块npm 安装 Node.js 模...

arm-linux-androideabi-readelf_mac arm-linux-androideabi-readelf-程序员宅基地

文章浏览阅读1.9k次。使用arm-linux-androideabi-readelf读取信息:arm-linux-androideabi-readelfUsage: readelf elf-file(s) Display information about the contents of ELF format files Options are: -a --all Equi_mac arm-linux-androideabi-readelf

随便推点

javaEE003.03 jQuery:基本选择器、层次选择器_选择 class 为 mini 的所有元素-程序员宅基地

文章浏览阅读128次。系列文章目录文章目录系列文章目录一、基本选择器二、层次选择器总结一、基本选择器二、层次选择器总结_选择 class 为 mini 的所有元素

连线到 VirtualBox 中的网站 ( Port Forwarding )_virtualbox port forward-程序员宅基地

文章浏览阅读261次。架设于 VirtualBox 中的网站,透过 「连接埠转送」( Port Forwarding ),透过转送的方式把网页传送出来。_virtualbox port forward

java sqlite 操作,Java操作SQLite实现增删改查-程序员宅基地

文章浏览阅读323次。import java.sql.Connection;import java.sql.DriverManager;import java.sql.ResultSet;import java.sql.SQLException;import java.sql.Statement;public class TestSQLite {public static void main(String[] args..._java如何对sqlite3数据库进行操作

# pip install scipy -- distutils.errors.LinkError: Command-程序员宅基地

文章浏览阅读2.3k次。[root@Dragonwake python]# pip install scipyYou are using pip version 7.1.0, however version 19.0.3 is available.You should consider upgrading via the 'pip install --upgrade pip' command.Collecting...

深度学习——Dual Regression Networks for Single Image Super-Resolution(DRN)_dual attention network for single image super-reso-程序员宅基地

文章浏览阅读959次,点赞2次,收藏3次。CVPR2020原论文:Closed-loop Matters: Dual Regression Networks forSingle Image Super-Resolution1.问题1)低分辨率图像(Low Resulotion)经过非线性映射成高分辨率图像(High Resulotion)本身是个病态问题。因为高分辨率的图像可以任意采样成低分辨率图像,所以其反向变换的非线性映射函数的解空间是非常大的。在这样大的解空间中找到合适的非线性映射函数是十分困难的。2)真实世界无法得到成对的低分辨图像(_dual attention network for single image super-resolution

关于神经网络中的网络训练过程中的验证集validation_data的认识-程序员宅基地

文章浏览阅读3w次,点赞8次,收藏60次。validation_data中包含了 幅数字图像,这些图像和训练数据集中的 幅图像以及测试数据集中的 幅都不相同。我们会使用 validation_data 来防止过匹配。我们会使用和上面应用在 test_data 的策略。我们每个回合都计算在 validation_data 上的分类准确度。一旦分类准确度已经饱和,就停止训练。这个策略被称为 提前停止(Early stopping)。当然,实际..._validation_data