当前位置: 首页 > news >正文

《算法竞赛·快冲300题》每日一题:“凑二十四”

算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。

文章目录

  • 题目描述
  • 题解
  • C++代码
  • Java代码
  • Python代码

凑二十四” ,链接: http://oj.ecustacm.cn/problem.php?id=1793

题目描述

【题目描述】 给你n个数字,你需要在n-1个间隔中添加符号+、-、×,按照正常优先级计算结果。请你输出有多少种方案,计算结果等于24。
【输入格式】 第一行为正整数n(2≤n≤10)。第二行n个正整数表示给定的n个数字,数字不超过50。
【输出格式】 输出一个数字表示答案。
【输入样例】

5
2 4 6 8 16

【输出样例】

2

题解

   如果尝试所有可能组合,共有多少种组合?最多n=10个数字时,需要添加9个符号,共 3 9 = 19683 3^9=19683 39=19683种组合,并不多。
  用DFS搜索所有可能组合。由于只有19683种情况,不用剪枝。
  代码用dfs()搜索所有符号组合。对每个组合,用check()检查计算结果是否等于24。先计算乘法,再计算加减。下面的代码用了简单直接的模拟法。先处理表达式中的乘法,对两个数做乘法时,把计算结果存在后面,前面置零,并把符号改为前面的加减,例如3+4×5,先处理乘法,转换为3+0+20。
  check()也有其他写法,例如先把表达式(称为中缀表达式)转为逆波兰表达式,然后用栈来计算逆波兰表达式。因为比较繁琐,这里没有给出代码。
【重点】 DFS 。

C++代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[11];
int op[11];               //第i个间隔的符号 + - * = 0 1 2
int ans;
ll check(){   //先计算*,再计算+-ll t[11] = {0}, t_op[11] = {0};for(int i=1; i<=n; i++)t[i] = a[i], t_op[i] = op[i];//先处理乘号:把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号for(int i = 1; i < n; i++)if(t_op[i] == 2)t[i+1] *= t[i], t[i] = 0, t_op[i] = t_op[i-1];//最后加减ll sum = t[1];for(int i = 1; i < n; i++){if(t_op[i] == 0)  sum += t[i+1]; //加else sum -= t[i+1];              //减}return sum;
}
void dfs(int depth){if(depth == n){if(check() == 24)   ans++;return;}for(int i = 0; i <= 2; i++) {   //继续添加下一个符号op[depth] = i;dfs(depth + 1);}
}
int main(){cin >> n;for(int i = 1; i <= n; i++)    cin >> a[i];dfs(1);cout<<ans<<endl;return 0;
}

Java代码

import java.util.Scanner;
public class Main {static int n, a[] = new int[11], op[] = new int[11]; // 第i个间隔的符号 + - * = 0 1 2static int ans;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();for (int i = 1; i <= n; i++)   a[i] = in.nextInt();dfs(1);System.out.println(ans);in.close();}static long check() { // 先计算*,再计算+-long[] t = new long[11];int[] t_op = new int[11];for (int i = 1; i <= n; i++) {t[i] = a[i];t_op[i] = op[i];}// 先处理乘号:把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号for (int i = 1; i < n; i++) {if (t_op[i] == 2) {t[i + 1] *= t[i];t[i] = 0;t_op[i] = t_op[i - 1];}}// 最后加减long sum = t[1];for (int i = 1; i < n; i++) {if (t_op[i] == 0) sum += t[i + 1]; // 加else              sum -= t[i + 1]; // 减}return sum;}static void dfs(int depth) {if (depth == n) {if (check() == 24)   ans++;return;}for (int i = 0; i <= 2; i++) { // 继续添加下一个符号op[depth] = i;dfs(depth + 1);}}
}

Python代码

n = int(input())
a = [0]+list(map(int, input().split()))     #输入到a[1]-a[10]
op = [0] * 11                               # 第i个间隔的符号 + - * = 0 1 2
ans = 0
def check():# 先计算*,再计算+-t = [0] * 11t_op = [0] * 11for i in range(1, n+1):t[i] = a[i]t_op[i] = op[i]# 先处理乘号:把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号for i in range(1, n):if t_op[i] == 2:t[i+1] *= t[i]t[i] = 0t_op[i] = t_op[i-1]# 最后加减sum = t[1]for i in range(1, n):if t_op[i] == 0: sum += t[i+1]  # 加else:            sum -= t[i+1]  # 减return sum
def dfs(depth):global ansif depth == n:if check() == 24:   ans += 1returnfor i in range(3):                  # 继续添加下一个符号op[depth] = idfs(depth + 1)
dfs(1)
print(ans)

相关文章:

《算法竞赛·快冲300题》每日一题:“凑二十四”

《算法竞赛快冲300题》将于2024年出版&#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码&#xff0c;以中低档题为主&#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 凑…...

git reset --hard HEAD

git reset --hard HEAD 是用于将你的工作目录重置回最后一次提交状态的命令。- git reset 是 git 的一个命令&#xff0c;用于重置你当前的 HEAD 到指定的状态。 --hard 标志告诉 git 要完全重置工作目录和暂存区&#xff0c;去匹配最后一次提交。在这个过程中&#xff0c;所有…...

机器人编程怎么入门?

机器人已经在我们中间存在了二三十年。如今&#xff0c;机器人在我们的文化中比以往任何时候都更加根深蒂固。大多数机器人机器用于各种装配线&#xff0c;或在世界各地的矿山或工业设施中执行密集的物理操作。 还有一些家用机器人&#xff0c;工程师正在对机器人进行编程&…...

广州华锐互动:VR垃圾分类虚拟科普系统让学习过程更加丰富有趣

在我们的日常生活中&#xff0c;垃圾分类已成为一项重要的公民责任。然而&#xff0c;由于缺乏对垃圾分类的深入理解和相关知识&#xff0c;许多人在实践中往往感到困惑和挫败。为了解决这个问题&#xff0c;一种创新的解决方案应运而生&#xff1a;垃圾分类VR虚拟仿真教学系统…...

手机盖板IR油墨透光率检测仪T03

手机盖板作为手机最外层玻璃面板&#xff0c;其加工一般有落料、倒边、抛光、镀膜、丝印等多道加工工序组成&#xff0c;其中任何一个工序出现差错&#xff0c;都有可能导致手机盖板产生缺陷&#xff0c;例如漏油、透光、IR孔不良、视窗划伤、油墨区划伤、內污、边花等&#xf…...

ChatGPT⼊门到精通(6):ChatGPT 提问设计

前⾔ 学会提问就是为了让AI给出⾼质量的答案。 你所学到的技能⼀切为了⽣成⾼质量的答案。 本教程适合&#xff1a;普通ChatGPT的⽤户、专业prompt⼯程师 你将收获&#xff1a;prompt 技巧的全⾯指导 、prompt⼯程师必备技能、prompt技术⼯程⾼质量答 案完全指南 提⽰词 Prom…...

如何使用 Tailwind CSS 设计高级自定义动画

使用Tailwind CSS掌握动画技术&#xff0c;为用户带来难忘的体验 开篇 动画已经成为网页设计的重要组成部分&#xff0c;使开发人员能够创建引人入胜和互动的用户体验。 Tailwind CSS&#xff0c;一款流行的实用型CSS框架&#xff0c;提供了一套强大的工具&#xff0c;可以轻松…...

【C语言】循环语句详解

✨个人主页&#xff1a; Anmia.&#x1f389;所属专栏&#xff1a; C Language &#x1f383;操作环境&#xff1a; Visual Studio 2019 版本 目录 1.什么是循环结构&#xff1f; 2.while循环 while流程图 while语句中的break和continue break continue 3.for循环 for流…...

SpringBoot项目配置文件数据库用户名密码加密

1、需求 在使用SpringBoot开发过程中&#xff0c;会将一些敏感信息配置到SpringBoot项目的配置文件中(不考虑使用配置中心的情况 )&#xff0c;例如数据库的用户名和密码、Redis的密码等。为了保证敏感信息的安全&#xff0c;我们需要将此类数据进行加密配置。 2、操作步骤 …...

5个IT事件管理的最佳实践

什么是IT事件&#xff1f; IT事件是一个影响很大的紧急问题&#xff0c;通常会影响整个组织或其主要部分。重大事件几乎总是导致组织的服务变得不可用&#xff0c;这导致组织的业务受到打击&#xff0c;并最终影响其财务状况。以下是5个重大IT事件管理的最佳实践&#xff1a; …...

双核和双路服务器的区别

服务器术语里&#xff0c;大家经常会听到1U、2U&#xff0c;单路、双路&#xff0c;机架式、塔式及刀片式等常用名词。其中&#xff0c;机架式、塔式及刀片式是 指服务器的外形&#xff0c;U是指服务器的高度&#xff0c;路是指服务器的处理器数量。 部分朋友会问&#xff0c;我…...

学习JAVA打卡第四十七天

日期的格式化 程序可能希望按照某种习惯来输出时间。例如时间的顺序&#xff1a;年/月/日或年/月/日/时/分/秒。可以直接使用String类调用format方法对日期进行格式化。 Format方法 Format方法&#xff1a; format&#xff08;格式化模式,日期列表&#xff09; 按照“格式…...

Exploring Unreal Engine New Free Archviz Explorer Project 视频笔记

链接&#xff1a; https://www.bilibili.com/video/BV1Q34y1Z7he/ 场景中没有太阳&#xff0c;也没有定向光 该蓝图用来控制光线的显示 删除这个蓝图 添加这个蓝图 顶部会出现时间滑块 该项目还有扩展插件&#xff0c;用户可以自由下载 它是由一个8k的卫星图做的地形底图 …...

Python|爬虫和测试|selenium框架的安装和初步使用(一)

前言&#xff1a; Python作为一门胶水语言来说&#xff0c;可以说是十分的优秀&#xff0c;什么事情都可以干&#xff0c;并且在某些领域还能干的非常不错&#xff0c;尤其是在爬虫和测试领域&#xff0c;该语言可以说是没有对手。 这么说的原因是因为如果你要使用爬虫爬取某…...

SAP FI之定义财务年和财务年度变式(Fiscal Year Variants)

目录 前言 一、财务年度/财务年度变式 二、使用步骤 1.配置步骤 前言 本文主要介绍SAP会计年度和SAP会计年度变式。 一、财务年度/财务年度变式 财务年度可以具有与日历年相同的期间&#xff0c;也可以不同。中国财政年度从1月到12月&#xff0c;称为历年制&#xff0c;有…...

关于SAM中decomposed Relative Positional Embeddings的理解

关于SAM中decomposed Relative Positional Embeddings的理解。 relative positional embedding的一种实现方式是&#xff1a;先计算q和k的相对位置坐标&#xff0c;然后依据相对位置坐标从给定的table中取值。以q和k都是77为例&#xff0c;每个相对位置有两个索引对应x和y两个…...

1、Spring是什么?

Spring 是一款主流的 Java EE 轻量级开源框架 。 框架 你可以理解为是一个程序的半成品&#xff0c;它帮我们实现了一部分功能&#xff0c;用这个框架我们可以减少代码的实现和功能的开发。 开源 也就是说&#xff0c;它开放源代码。通过源代码&#xff0c;你可以看到它是如何…...

【华为OD机试python】阿里巴巴找黄金宝箱(IV)【2023 B卷|200分】

题目描述 一贫如洗的樵夫阿里巴巴在去砍柴的路上,无意中发现了强盗集团的藏宝地, 藏宝地有编号从0-N的箱子,每个箱子上面有一个数字,箱子排列成一个环, 编号最大的箱子的下一个是编号为0的箱子。 请输出每个箱子贴的数字之后的第一个比它大的数,如果不存在则输出-1。 输入…...

操作系统复习总结5

操作系统复习总结&#xff0c;仅供笔者复习使用&#xff0c;参考教材&#xff1a; 《操作系统原理》 - 何静媛编著. 西安电子科技大学出版社《操作系统考研复习指导》2024年 - 王道论坛组编. 电子工业出版社 本文主要内容为&#xff1a;输入输出管理&#xff1b; 计算机系统…...

【LeetCode】406.根据身高重建队列

题目 假设有打乱顺序的一群人站成一个队列&#xff0c;数组 people 表示队列中一些人的属性&#xff08;不一定按顺序&#xff09;。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi &#xff0c;前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...