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

《算法竞赛·快冲300题》每日一题:“特殊数字”

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

文章目录

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

特殊数字” ,链接: http://oj.ecustacm.cn/problem.php?id=1817

题目描述

【题目描述】 N=2x+2y,并且x≠y,则称N为特殊数字。
   现在给定数字x,每次可以进行两种操作:令x加1、令x减1。
   最少执行多少次操作,可以将x变成特殊数字。
【输入格式】 第一行为正整数T,表示存在T组测试数据,1≤T≤10000。
   每组数据输入一行,包含一个整数x,1≤x≤10^9。
**【输出格式】**每组数据输出一行表示答案。
【输入样例】

3
10
22
4

【输出样例】

0
2
1

题解

   由于直接对x进行加1减1的操作然后判断是否为特殊数字十分耗时,这不是好办法。容易想到的简单的办法是提前算出所有的特殊数字,然后找与x最近的数字。
   有多少特殊数字,计算量大吗?题目给定 x ≤ 1 0 9 x≤10^9 x109,而 1 0 9 < 2 30 10^9 < 2^{30} 109<230,对于 N = 2 x + 2 y N = 2^x + 2^y N=2x+2y,只需分别把 2 x 、 2 y 2^x、2^y 2x2y计算算到 2 30 2^{30} 230,一共30×30次就够了。
   接下来是找距离x最近的数字。先把特殊数字排序,然后用二分法找距离x最近的数即可。
【重点】 二分法、lower_bound() 。

C++代码

   STL有一个二分法函数lower_bound()(lower_bound()的用法见《算法竞赛》,清华大学出版社,罗勇军、郭卫斌著,46页),它的功能是在有序序列中找x或附近的数,正符合本题的要求。

#include<bits/stdc++.h>
using namespace std;
int a[910], tot;
int main(){for(int i = 0; i <= 30; i++)          //预先处理出所有特殊数字for(int j = i + 1; j <= 30; j++)  //i和j不同a[tot++] = (1 << i) + (1 << j);sort(a, a + tot);                     //二分之前先排序int T;   cin >> T;while(T--) {int x; cin >> x;int p = lower_bound(a, a + tot, x) - a;  //查找第一个大于等于x的位置p,即a[p]>=xint ans = 0;if(a[p] == x)  ans = 0;else {ans = a[p] - x;                      //a[p]比x大if(p - 1 > 0)                        ans = min(ans, x - a[p - 1]);    //比x大和比x小的最近2个数}cout<<ans<<endl;}return 0;
}

   作为对照,下面给出手写二分法的代码。

#include<bits/stdc++.h>
using namespace std;
int a[910],tot;
int main(){for (int i = 0;i <= 30;i++)for (int j = i + 1;j <= 30;j++)a[tot++] = (1 << i) + (1 << j);sort(a , a + tot);int T; cin >> T;while (T--)  {int x; cin >> x;int L = 0 , R = tot;while (L < R)     {int mid = L + R >> 1;if (a[mid] >= x)   R = mid;else L = mid + 1;}int ans;if (a[L] == x)  ans = 0;else  {ans = a[L] - x;if (L > 0) ans = min(ans , x - a[L - 1]);}cout << ans << endl;}return 0;
}

Java代码

   Java也有和C++的lower_bound()类似的函数binarySearch()。注意binarySearch()的返回值,如果找不到x,它的返回值是负的。

 import java.util.*;
public class Main {public static void main(String[] args) {int[] a = new int[910];int tot = 0;for(int i = 0; i <= 30; i++)             //预先处理出所有特殊数字for(int j = i + 1; j <= 30; j++)     //i和j不同a[tot++] = (1 << i) + (1 << j);        Arrays.sort(a, 0, tot);                  //二分之前先排序Scanner sc = new Scanner(System.in);int T = sc.nextInt();while(T-- > 0) {int x = sc.nextInt();int p = Arrays.binarySearch(a, 0, tot, x);if(p < 0) {                       //a[]中没有x,返回的p是负的p = -p - 1;int ans = a[p] - x;           //a[p]比x大if(p - 1 >= 0)ans = Math.min(ans, x - a[p - 1]);   //比x大和比x小的最近2个数System.out.println(ans);}else {                           //a[]中有x,返回的p是数组下标 System.out.println(0);}}sc.close();}
}

   作为对照,下面给出手写二分法的Java代码。

 import java.util.Arrays;
import java.util.Scanner;
public class Main {public static void main(String[] args) {int[] a = new int[910];int tot = 0;for (int i = 0; i <= 30; i++)for (int j = i + 1; j <= 30; j++)a[tot++] = (1 << i) + (1 << j);Arrays.sort(a, 0, tot);Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- > 0) {int x = sc.nextInt();int L = 0, R = tot;while (L < R) {int mid = (L + R) >> 1;if (a[mid] >= x)   R = mid;else               L = mid + 1;}int ans;if (a[L] == x)  ans = 0;else {ans = a[L] - x;if (L > 0)  ans = Math.min(ans, x - a[L - 1]);}System.out.println(ans);}}
}

Python代码

   Python也有和C++的lower_bound()类似的函数bisect_left()。

import bisect
a = []
for i in range(31):for j in range(i+1,31):a.append((1 << i) + (1 << j))    
a.sort()
t = int(input())
for _ in range(t):x = int(input())p = bisect.bisect_left(a,x)print(min(abs(a[p]-x),abs(a[p-1]-x)))

   作为对照,下面给出手写二分法的Python代码。

a = []
for i in range(31):for j in range(i+1, 31):a.append((1 << i) + (1 << j)) 
a.sort()
T = int(input())
for _ in range(T):x = int(input())L, R = 0, len(a)while L < R:mid = (L + R) // 2if a[mid] >= x:  R = midelse:            L = mid + 1if a[L] == x:  ans = 0else:ans = a[L] - xif L > 0:  ans = min(ans, x - a[L-1])print(ans)

相关文章:

《算法竞赛·快冲300题》每日一题:“特殊数字”

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

在R中比较两个矩阵是否相等

目录 方法一&#xff1a;使用all.equal()比较两个R对象是否近似相等 方法二&#xff1a;使用identical比较两个R对象是否精确相等。 方法一&#xff1a;使用all.equal()比较两个R对象是否近似相等 使用函数&#xff1a;all.equal(x,y) 比较两个R对象x和y是否近似相等 > M1…...

商城-学习整理-基础-商品服务API-属性分组(七)

目录 一、创建系统菜单二、开发商品系统-平台属性-属性分组1、将三级分类功能抽取出来2、编写后端代码3、属性分组新增功能4、属性分组修改回显功能 三、商品系统-平台属性-规则参数1、列表展示页面2、新增规格参数页面 四、商品系统-平台属性-销售属性1、列表展示页面2、新增或…...

什么是响应式设计?列举几种实现响应式设计的方法。

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 什么是响应式设计&#xff1f;⭐ 实现响应式设计的方法⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏…...

Java类和对象(一文读懂)

文章目录 类、对象是什么&#xff1f;创建类构造器 创建对象 类、对象是什么&#xff1f; 类&#xff1a;类是一个模板&#xff0c;它描述一类对象的行为和状态。类可以看成是创建 Java 对象的模板。 对象&#xff1a;对象是类的一个实例&#xff08;对象不是找个女朋友&#x…...

用友移动管理系统 任意文件上传漏洞复现(HW0day)

0x01 产品简介 用友移动系统管理是用友公司推出的一款移动办公解决方案&#xff0c;旨在帮助企业实现移动办公、提高管理效率和员工工作灵活性。它提供了一系列功能和工具&#xff0c;方便用户在移动设备上管理和处理企业的系统和业务。 0x02 漏洞概述 用友移动管理系统 uploa…...

启动springboot,出现Unable to start embedded Tomcat

报错信息 org.apache.catalina.core.ContainerBase : A child container failed during startjava.util.concurrent.ExecutionException: org.apache.catalina.LifecycleException: Failed to start component [StandardEngine[Tomcat].StandardHost[localhost].TomcatEmbedd…...

加密和安全

加密和安全 一.安全机制 安全攻击的几种典型方式&#xff1a; STRIDE Spoofing 假冒 Tampering 篡改 Repudiation 否认 Information Disclosure 信息泄漏 Denial of Service 拒绝服务 Elevation of Privilege 提升…...

Maven基础总结

前言 Maven 是一个项目管理工具&#xff0c;可以对 Java 项目进行构建、依赖管理。 基本要求掌握 配置Maven环境直接查。 得会在IDEA创建Maven的java项目吧、会创建Maven的web项目吧、会创建多模块项目吧。 得会配置插件pligin、依赖dependency吧 一、Maven四大特性 1、…...

Java 编程实战:如何用 Java 编写一个简单而强大的 Tomcat

学习完了JavaWeb&#xff0c;为了深入了解tomcat&#xff0c;打算手撕tomcat搭建自己的tomcat&#xff0c;希望对来访小伙伴也有帮助 引言 Tomcat 是一个开源的 Web 服务器和 Servlet 容器&#xff0c;它可以提供动态 Web 内容的处理和交互功能。Tomcat 是用 Java 语言编写的&a…...

【JavaSE】数组的定义与使用

详解数组 数组的基本概念什么是数组数组的创建及初始化数组的使用 数组是引用类型基本类型变量与引用类型变量的区别引用变量认识 null 数组的应用场景数组练习二维数组 数组的基本概念 什么是数组 数组可以看成是相同类型元素的一个集合。在内存中是一段连续的空间。比如现实…...

银河麒麟安装php7.1.33

银河麒麟V10兼容CentOS 8 安装过程与CentOS类似。 TencentOS3.1安装PHPNginxredis测试系统_乐大师的博客-CSDN博客 可以参考之前我写的文章。 不过有2个细节不同&#xff0c;下面说下。 问题1&#xff1a;编译错误提示“error:off_t undefined” 解决方法&#xff1a; 编…...

Kubernetes集群部署上篇(安装部署,但是集群网络未部署)

第四阶段 时 间&#xff1a;2023年8月9日 参加人&#xff1a;全班人员 内 容&#xff1a; Kubernetes集群部署上篇 目录 一、Kubernetes部署方式 &#xff08;一&#xff09;minikube &#xff08;二&#xff09;二进制包 &#xff08;三&#xff09;Kubeadm Kubea…...

跨境电商中的安全挑战与隐擎Fox指纹浏览器的应用

随着全球互联网的蓬勃发展&#xff0c;跨境电商已经成为了国际贸易的重要组成部分。然而&#xff0c;跨境电商的迅速崛起也伴随着一系列安全挑战&#xff0c;其中之一就是恶意活动和隐私泄露。为了应对这些挑战&#xff0c;诸多技术手段被开发出来&#xff0c;其中隐擎Fox指纹浏…...

10. Docker Swarm(一)

目录 1、前言 2、Docker Swarm体系架构 2.1、简单介绍 2.2、体系架构 3、简单使用 3.1、环境准备 3.2、初始化master节点 3.3、建立worker节点 3.4、查看集群的节点信息 3.5、部署应用 3.5.1、创建Dockerfile文件 3.5.2、构建镜像 3.5.3、将镜像上传到Docker仓库 …...

【MySQL】InnoDB存储引擎详解

InnoDB引擎是MySQL5.5版本之后默认的存储引擎 逻辑存储结构 首先是表空间Tablespace&#xff08;ibd文件&#xff09;&#xff1a;一个mysql实力可以对应多个表空间&#xff0c;用于存储及记录&#xff0c;索引等数据 这些存储记录&#xff0c;索引等数据中是用段(Segment)来…...

组合求和-矩阵连乘所有加括号方式_2023_08_12

矩阵链加括号方式总数 前言 矩阵链乘积的瓶颈在于其标量运算的次数&#xff0c;不同的结合次序对其时间性能影响远大于矩阵乘积运算本身&#xff0c;可以看到许多教材上把求解矩阵标量运算的最优解作为动态规划的示例&#xff0c;问题隐含动态规划两大特征&#xff1a; 最优子…...

《3D 数学基础》12 几何图元

目录 1 表达图元的方法 1.1 隐式表示法 1.2 参数表示 1.3 直接表示 2. 直线和射线 2.1 射线的不同表示法 2.1.1 两点表示 2.1.2 参数表示 2.1.3 相互转换 2.2 直线的不同表示法 2.2.1 隐式表示法 2.2.2 斜截式 2.2.3 相互转换 3. 球 3.1 隐式表示 1 表达图元的方…...

【设计模式——学习笔记】23种设计模式——备忘录模式Memento(原理讲解+应用场景介绍+案例介绍+Java代码实现)

案例引入 游戏角色有攻击力和防御力&#xff0c;在大战Boss前保存自身的状态(攻击力和防御力)&#xff0c;当大战Boss后攻击力和防御力下降&#xff0c;可以从备忘录对象恢复到大战前的状态 传统设计方案 针对每一种角色&#xff0c;设计一个类来存储该角色的状态 【分析】…...

致谢丨感谢有你,JumpServer开源项目九周年致谢名单

2014年到2023年&#xff0c;JumpServer开源项目已经走过了九年的时间。感谢以下社区贡献者对JumpServer项目的帮助和支持。 因为有你&#xff0c;一切才能成真。 JumpServer开源项目贡献者奖杯将于近日邮寄到以上贡献者手中&#xff0c;同时JumpServer开源项目组还准备了一份小…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...