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

UVA-1374 旋转游戏 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

由于书上给了思路,所以做起来并不难。

即使超时,因为数据量不大(1000个), 我们也可以直接打表直接返回结果。

但是如果想不打表完成题目,那么就需要使用思路中给出的各种优化方案,不然很容易超时。

我一开始用set作为存储已存在的数字,但还是超时,后面改成用数组存储AC了。

AC代码

#include<stdio.h>
#include<string.h>
#include<math.h>int n, maxCount;
int setArr[1010];
int maxV;int getMin(int a, int b) {if(a > b) return b;return a;
}// 递归遍历 
bool dfs(int count, int pre, int subCount) {if(pre == n) return true;if(count >= maxCount) return false;if(maxV * (1 << (maxCount - count)) < n) return false;if(subCount > 2) return false;int value, preMaxV, i;if(pre < n) {for(i = getMin(maxV, n); i > 0; --i) {if(!setArr[i]) continue;value = i + pre;if(value > 1000 || (value > n && maxV > n)) continue;if(setArr[value]) continue;setArr[value] = 1;preMaxV = maxV;if(value > maxV) maxV = value;if(dfs(count+1, value, subCount)) return true;setArr[value] = 0;maxV = preMaxV; }}if(subCount == 2) return false;for(i = maxV; i > 0; --i) {if(!setArr[i]) continue;value = abs(i - pre);if(value == 0 || value > n) continue;if(value == n) return true;if(setArr[value]) continue;setArr[value] = 1;if(dfs(count+1, value, subCount + 1)) return true;setArr[value] = 0;}return false;
}// 初始化 
int computed() {if(n == 1) return 0;for(maxCount = 1; maxCount < 20; ++maxCount) {memset(setArr, 0, sizeof(setArr));setArr[1] = 1;maxV = 1;if(dfs(0, 1, 0)) return maxCount;}
}int main() {while(scanf("%d", &n) == 1 && n > 0) {printf("%d\n", computed());}return 0;
}

相关文章:

UVA-1374 旋转游戏 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版 由于书上给了思路&#xff0c;所以做起来并不难。 即使超时&#xff0c;因为数据量不大&#xff08;1000个&#xff09;&#xff0c; 我们也可以直接打表直接返回结果。 但是如果想不打表完…...

logback.xml springboot 项目通用logback配置,粘贴即用,按日期生成

<configuration scan"false" scanPeriod"10 seconds"><!-- 定义日志存放的根目录 --><property name"log.dir" value"./logs" /><!-- 彩色日志依赖的渲染类 --><conversionRule conversionWord"clr&q…...

【AI视野·今日CV 计算机视觉论文速览 第256期】Thu, 28 Sep 2023

AI视野今日CS.CV 计算机视觉论文速览 Thu, 28 Sep 2023 Totally 96 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computer Vision Papers SHACIRA: Scalable HAsh-grid Compression for Implicit Neural Representations Authors Sharath Girish, Abhinav Shriva…...

2023-9-28 JZ26 树的子结构

题目链接&#xff1a;树的子结构 import java.util.*; /** public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;}} */ public class Solution {public boolean HasSubtree(TreeNode root1,TreeNode root2) …...

ElementUI之首页导航+左侧菜单

文章目录 一、Mock.js1.1.什么是Mock.js1.2.安装与配置1.3使用 二、登录注册跳转2.1.在views中添加Register.vue2.2.在Login.vue中的methods中添加gotoRegister方法2.3.在router/index.js中注册路由 三、组件通信&#xff08;总线&#xff09;3.1 在main.js中添加内容3.2.在com…...

【Linux学习】04Linux实用操作

Linux&#xff08;B站黑马&#xff09;学习笔记 01Linux初识与安装 02Linux基础命令 03Linux用户和权限 04Linux实用操作 05-1Linux上安装部署各类软件 文章目录 Linux&#xff08;B站黑马&#xff09;学习笔记前言04Linux实用操作各类小技巧&#xff08;快捷键&#xff09;ct…...

一篇博客学会系列(1) —— C语言中所有字符串函数以及内存函数的使用和注意事项

目录 1、求字符串长度函数 1.1、strlen 2、字符串拷贝(cpy)、拼接(cat)、比较(cmp)函数 2.1、长度不受限制的字符串函数 2.1.1、strcpy 2.1.2、strcat 2.1.3、strcmp 2.2、长度受限制的字符串函数 2.2.1、strncpy 2.2.2、strncat 2.2.3、strncmp 3、字符串查找函数…...

计算机视觉与深度学习-循环神经网络与注意力机制-RNN(Recurrent Neural Network)、LSTM-【北邮鲁鹏】

目录 举例应用槽填充&#xff08;Slot Filling&#xff09;解决思路方案使用前馈神经网络输入1-of-N encoding(One-hot)&#xff08;独热编码&#xff09; 输出 问题 循环神经网络&#xff08;Recurrent Neural Network&#xff0c;RNN&#xff09;定义如何工作学习目标深度Elm…...

brew 安装MySQL 5.7

写在前面&#xff1a;博主是一只经过实战开发历练后投身培训事业的“小山猪”&#xff0c;昵称取自动画片《狮子王》中的“彭彭”&#xff0c;总是以乐观、积极的心态对待周边的事物。本人的技术路线从Java全栈工程师一路奔向大数据开发、数据挖掘领域&#xff0c;如今终有小成…...

【中国知名企业高管团队】系列22:滴滴

大家好&#xff01; 今天华研荟的走进中国知名企业高管团队系列带大家认识滴滴。 滴滴公司是出行领域的先行者&#xff0c;也是一个典型样本。通过滴滴公司的名字变迁我们可以感受到滴滴公司的业务发展&#xff0c;这也是整个出行行业公司的发展路径&#xff1a; 第一阶段&a…...

Unity之Hololens如何实现3D物体交互

一.前言 什么是Hololens? Hololens是由微软开发的一款混合现实头戴式设备,它将虚拟内容与现实世界相结合,为用户提供了沉浸式的AR体验。Hololens通过内置的传感器和摄像头,能够感知用户的环境,并在用户的视野中显示虚拟对象。这使得用户可以与虚拟内容进行互动,将数字信…...

IDEA Debug技巧大全,看完就能提升工作效率

作者简介 目录 1.行断点 2.方法断点 3.异常断点 4.字段断点 5.条件表达式 1.行断点 行断点就是平时我们在代码行旁边单击鼠标打上的断点&#xff0c;这个没有什么好说的。关键点在于很多人不知道的&#xff0c;行断点其实是可以右击选择是对改行的全部调用都生效&#xf…...

蓝桥等考Python组别六级003

第一部分:选择题 1、PythonL6(15分) 运行下面的程序,输出的值最大可能是()。 importrandom print(random.randint(2,4)*5) 10152030正确答案:C 2、PythonL6(15分) 甲、乙、丙三个人赛跑,已知甲不是第一名,乙不是第二名,名次没有并列的。...

机器学习小白理解之一元线性回归

关于机器学习&#xff0c;百度上一搜一大摞&#xff0c;总之各有各的优劣&#xff0c;有的非常专业&#xff0c;有的看的似懂非懂。我作为一名机器学习的门外汉&#xff0c;为了看懂这些公式和名词真的花了不少时间&#xff0c;还因此去着重学了高数。 不过如果不去看公式&…...

目标检测:FROD: Robust Object Detection for Free

论文作者&#xff1a;Muhammad,Awais,Weiming,Zhuang,Lingjuan,Lyu,Sung-Ho,Bae 作者单位&#xff1a;Sony AI; Kyung-Hee University 论文链接&#xff1a;http://arxiv.org/abs/2308.01888v1 内容简介&#xff1a; 1&#xff09;方向&#xff1a;目标检测 2&#xff09;…...

linux 和 windows的換行符不兼容問題

linux 和 windows的換行符&#xff1a; 1.vim 模式下&#xff0c;執行命令&#xff1a; :set ffunix idea中設置code style...

ubuntu 20 安装 CUDA

1. 查看需要安装的cuda版本 nvidia-smi cuda的版本信息如下图所示 2. 去官网下载对应版本的CUDA 官网&#xff1a;CUDA Toolkit Archive | NVIDIA Developer 弹出以下界面&#xff0c;依次点击以下按钮 得到以下内容&#xff1a; 复制下载链接&#xff0c;下载cuda11到本…...

C++友元函数和友元类

友元介绍 类的友元函数是定义在类外部&#xff0c;但有权访问类的所有私有&#xff08;private&#xff09;成员和保护&#xff08;protected&#xff09;成员。尽管友元函数的原型有在类的定义中出现过&#xff0c;但是友元函数并不是成员函数。 友元可以是一个函数&#xf…...

特斯拉——使用人工智能制造智能汽车

特斯拉(Tesla)是电动汽车开发和推广的先驱。特斯拉对自动驾驶汽车的未来寄予厚望--实际上&#xff0c;每一辆特斯拉汽车都有可能通过软件升级成为自动驾驶汽车。该公司还生产和销售高级电池和太阳能电池板。 汽车的自动驾驶是按从1~5的等级划分的。自适应巡航控制和自动停车系…...

如何删除gitlab上多余的文件夹

无意间在提交代码时&#xff0c;包含了多余的 .idea 或者 __pychche__ 缓存文件夹等等&#xff0c;如何一次性删除呢&#xff1f; 实际上没有更好的办法&#xff0c;如果还没有合并&#xff0c;close 掉 MR就行了&#xff0c;重新提交。 如果已经合并了&#xff0c;就会留下记…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...