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: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版 由于书上给了思路,所以做起来并不难。 即使超时,因为数据量不大(1000个), 我们也可以直接打表直接返回结果。 但是如果想不打表完…...
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 👉上期速览✈更多精彩请移步主页 Daily Computer Vision Papers SHACIRA: Scalable HAsh-grid Compression for Implicit Neural Representations Authors Sharath Girish, Abhinav Shriva…...
2023-9-28 JZ26 树的子结构
题目链接:树的子结构 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中注册路由 三、组件通信(总线)3.1 在main.js中添加内容3.2.在com…...
【Linux学习】04Linux实用操作
Linux(B站黑马)学习笔记 01Linux初识与安装 02Linux基础命令 03Linux用户和权限 04Linux实用操作 05-1Linux上安装部署各类软件 文章目录 Linux(B站黑马)学习笔记前言04Linux实用操作各类小技巧(快捷键)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-【北邮鲁鹏】
目录 举例应用槽填充(Slot Filling)解决思路方案使用前馈神经网络输入1-of-N encoding(One-hot)(独热编码) 输出 问题 循环神经网络(Recurrent Neural Network,RNN)定义如何工作学习目标深度Elm…...
brew 安装MySQL 5.7
写在前面:博主是一只经过实战开发历练后投身培训事业的“小山猪”,昵称取自动画片《狮子王》中的“彭彭”,总是以乐观、积极的心态对待周边的事物。本人的技术路线从Java全栈工程师一路奔向大数据开发、数据挖掘领域,如今终有小成…...
【中国知名企业高管团队】系列22:滴滴
大家好! 今天华研荟的走进中国知名企业高管团队系列带大家认识滴滴。 滴滴公司是出行领域的先行者,也是一个典型样本。通过滴滴公司的名字变迁我们可以感受到滴滴公司的业务发展,这也是整个出行行业公司的发展路径: 第一阶段&a…...
Unity之Hololens如何实现3D物体交互
一.前言 什么是Hololens? Hololens是由微软开发的一款混合现实头戴式设备,它将虚拟内容与现实世界相结合,为用户提供了沉浸式的AR体验。Hololens通过内置的传感器和摄像头,能够感知用户的环境,并在用户的视野中显示虚拟对象。这使得用户可以与虚拟内容进行互动,将数字信…...
IDEA Debug技巧大全,看完就能提升工作效率
作者简介 目录 1.行断点 2.方法断点 3.异常断点 4.字段断点 5.条件表达式 1.行断点 行断点就是平时我们在代码行旁边单击鼠标打上的断点,这个没有什么好说的。关键点在于很多人不知道的,行断点其实是可以右击选择是对改行的全部调用都生效…...
蓝桥等考Python组别六级003
第一部分:选择题 1、PythonL6(15分) 运行下面的程序,输出的值最大可能是()。 importrandom print(random.randint(2,4)*5) 10152030正确答案:C 2、PythonL6(15分) 甲、乙、丙三个人赛跑,已知甲不是第一名,乙不是第二名,名次没有并列的。...
机器学习小白理解之一元线性回归
关于机器学习,百度上一搜一大摞,总之各有各的优劣,有的非常专业,有的看的似懂非懂。我作为一名机器学习的门外汉,为了看懂这些公式和名词真的花了不少时间,还因此去着重学了高数。 不过如果不去看公式&…...
目标检测:FROD: Robust Object Detection for Free
论文作者:Muhammad,Awais,Weiming,Zhuang,Lingjuan,Lyu,Sung-Ho,Bae 作者单位:Sony AI; Kyung-Hee University 论文链接:http://arxiv.org/abs/2308.01888v1 内容简介: 1)方向:目标检测 2)…...
linux 和 windows的換行符不兼容問題
linux 和 windows的換行符: 1.vim 模式下,執行命令: :set ffunix idea中設置code style...
ubuntu 20 安装 CUDA
1. 查看需要安装的cuda版本 nvidia-smi cuda的版本信息如下图所示 2. 去官网下载对应版本的CUDA 官网:CUDA Toolkit Archive | NVIDIA Developer 弹出以下界面,依次点击以下按钮 得到以下内容: 复制下载链接,下载cuda11到本…...
C++友元函数和友元类
友元介绍 类的友元函数是定义在类外部,但有权访问类的所有私有(private)成员和保护(protected)成员。尽管友元函数的原型有在类的定义中出现过,但是友元函数并不是成员函数。 友元可以是一个函数…...
特斯拉——使用人工智能制造智能汽车
特斯拉(Tesla)是电动汽车开发和推广的先驱。特斯拉对自动驾驶汽车的未来寄予厚望--实际上,每一辆特斯拉汽车都有可能通过软件升级成为自动驾驶汽车。该公司还生产和销售高级电池和太阳能电池板。 汽车的自动驾驶是按从1~5的等级划分的。自适应巡航控制和自动停车系…...
如何删除gitlab上多余的文件夹
无意间在提交代码时,包含了多余的 .idea 或者 __pychche__ 缓存文件夹等等,如何一次性删除呢? 实际上没有更好的办法,如果还没有合并,close 掉 MR就行了,重新提交。 如果已经合并了,就会留下记…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
