《算法竞赛·快冲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 x≤109,而 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 2x、2y计算算到 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年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 特…...
在R中比较两个矩阵是否相等
目录 方法一:使用all.equal()比较两个R对象是否近似相等 方法二:使用identical比较两个R对象是否精确相等。 方法一:使用all.equal()比较两个R对象是否近似相等 使用函数:all.equal(x,y) 比较两个R对象x和y是否近似相等 > M1…...
商城-学习整理-基础-商品服务API-属性分组(七)
目录 一、创建系统菜单二、开发商品系统-平台属性-属性分组1、将三级分类功能抽取出来2、编写后端代码3、属性分组新增功能4、属性分组修改回显功能 三、商品系统-平台属性-规则参数1、列表展示页面2、新增规格参数页面 四、商品系统-平台属性-销售属性1、列表展示页面2、新增或…...
什么是响应式设计?列举几种实现响应式设计的方法。
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 什么是响应式设计?⭐ 实现响应式设计的方法⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏…...
Java类和对象(一文读懂)
文章目录 类、对象是什么?创建类构造器 创建对象 类、对象是什么? 类:类是一个模板,它描述一类对象的行为和状态。类可以看成是创建 Java 对象的模板。 对象:对象是类的一个实例(对象不是找个女朋友&#x…...
用友移动管理系统 任意文件上传漏洞复现(HW0day)
0x01 产品简介 用友移动系统管理是用友公司推出的一款移动办公解决方案,旨在帮助企业实现移动办公、提高管理效率和员工工作灵活性。它提供了一系列功能和工具,方便用户在移动设备上管理和处理企业的系统和业务。 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…...
加密和安全
加密和安全 一.安全机制 安全攻击的几种典型方式: STRIDE Spoofing 假冒 Tampering 篡改 Repudiation 否认 Information Disclosure 信息泄漏 Denial of Service 拒绝服务 Elevation of Privilege 提升…...
Maven基础总结
前言 Maven 是一个项目管理工具,可以对 Java 项目进行构建、依赖管理。 基本要求掌握 配置Maven环境直接查。 得会在IDEA创建Maven的java项目吧、会创建Maven的web项目吧、会创建多模块项目吧。 得会配置插件pligin、依赖dependency吧 一、Maven四大特性 1、…...
Java 编程实战:如何用 Java 编写一个简单而强大的 Tomcat
学习完了JavaWeb,为了深入了解tomcat,打算手撕tomcat搭建自己的tomcat,希望对来访小伙伴也有帮助 引言 Tomcat 是一个开源的 Web 服务器和 Servlet 容器,它可以提供动态 Web 内容的处理和交互功能。Tomcat 是用 Java 语言编写的&a…...
【JavaSE】数组的定义与使用
详解数组 数组的基本概念什么是数组数组的创建及初始化数组的使用 数组是引用类型基本类型变量与引用类型变量的区别引用变量认识 null 数组的应用场景数组练习二维数组 数组的基本概念 什么是数组 数组可以看成是相同类型元素的一个集合。在内存中是一段连续的空间。比如现实…...
银河麒麟安装php7.1.33
银河麒麟V10兼容CentOS 8 安装过程与CentOS类似。 TencentOS3.1安装PHPNginxredis测试系统_乐大师的博客-CSDN博客 可以参考之前我写的文章。 不过有2个细节不同,下面说下。 问题1:编译错误提示“error:off_t undefined” 解决方法: 编…...
Kubernetes集群部署上篇(安装部署,但是集群网络未部署)
第四阶段 时 间:2023年8月9日 参加人:全班人员 内 容: Kubernetes集群部署上篇 目录 一、Kubernetes部署方式 (一)minikube (二)二进制包 (三)Kubeadm Kubea…...
跨境电商中的安全挑战与隐擎Fox指纹浏览器的应用
随着全球互联网的蓬勃发展,跨境电商已经成为了国际贸易的重要组成部分。然而,跨境电商的迅速崛起也伴随着一系列安全挑战,其中之一就是恶意活动和隐私泄露。为了应对这些挑战,诸多技术手段被开发出来,其中隐擎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(ibd文件):一个mysql实力可以对应多个表空间,用于存储及记录,索引等数据 这些存储记录,索引等数据中是用段(Segment)来…...
组合求和-矩阵连乘所有加括号方式_2023_08_12
矩阵链加括号方式总数 前言 矩阵链乘积的瓶颈在于其标量运算的次数,不同的结合次序对其时间性能影响远大于矩阵乘积运算本身,可以看到许多教材上把求解矩阵标量运算的最优解作为动态规划的示例,问题隐含动态规划两大特征: 最优子…...
《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代码实现)
案例引入 游戏角色有攻击力和防御力,在大战Boss前保存自身的状态(攻击力和防御力),当大战Boss后攻击力和防御力下降,可以从备忘录对象恢复到大战前的状态 传统设计方案 针对每一种角色,设计一个类来存储该角色的状态 【分析】…...
致谢丨感谢有你,JumpServer开源项目九周年致谢名单
2014年到2023年,JumpServer开源项目已经走过了九年的时间。感谢以下社区贡献者对JumpServer项目的帮助和支持。 因为有你,一切才能成真。 JumpServer开源项目贡献者奖杯将于近日邮寄到以上贡献者手中,同时JumpServer开源项目组还准备了一份小…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
WebRTC调研
WebRTC是什么,为什么,如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
大数据治理的常见方式
大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法,以下是几种常见的治理方式: 1. 数据质量管理 核心方法: 数据校验:建立数据校验规则(格式、范围、一致性等)数据清洗&…...
