【1010】Radix (25分)

简介: (1)将已确定进制的数放在N1,将未确定进制的数字放在N2,以便后面进行统一计算。(2)题目说给的数N1和N2可能有10个数位,最多为三十六进制,即最大的数为36^10(超过int最大范围),于是将N1转换为十进制,使用long long类型存储。(3)使用二分法:

1.题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536

2.思路

(1)将已确定进制的数放在N1,将未确定进制的数字放在N2,以便后面进行统一计算。

(2)题目说给的数N1和N2可能有10个数位,最多为三十六进制,即最大的数为36^10(超过int最大范围),于是将N1转换为十进制,使用long long类型存储。

(3)使用二分法:

   对于一个确定的数字串,其进制越大,则该数字串转换为十进制的结果越大,所以可以二分N2的进制,将N2从该进制转换为十进制,令其与N1的十进制比较:如果大于N1的十进制,说明N2的当前进制太大——应往左子区间继续二分,小于同理,当二分结束时即可判断解是否存在。

3.代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>  
using namespace std;  
二分查找,进制转换,暴力会超时,确定好上下界
LL inf=(1LL << 63)-1; 注意此处是把LL型的1左移63位
typedef long long LL;
LL Map[256];  //0~9  a~z  与0~35的对应
LL inf=(1LL << 63)-1; //long的最大值2^63-1
void init(){
  for(char c='0';c<='9';c++){
    Map[c]=c-'0';  //将0~9映射到Map的0~9
  }
  for(char c='a';c<='z';c++){
    Map[c]=c-'a'+10; //将a~z映射到Map的10~35
  }
}
LL convertNum10(char a[],LL radix,LL t){ //将a转化为十进制,t为上界
  LL ans=0;
  int len=strlen(a);
  for(int i=0;i<len;i++){
    ans=ans*radix+Map[a[i]]; //进制转换
    if(ans<0 || ans>t) return -1; //溢出或超过N1的十进制
  }
  return ans;
}
int cmp(char N2[],LL radix, LL t){  //N2的十进制与t比较
  int len=strlen(N2); 
  LL num=convertNum10(N2,radix,t); //将N2转换成十进制
  if(num<0)  return 1; //溢出,肯定是N2>t
  if(t>num)  return -1; //t更大则返回-1
  else if(t==num) return 0; //相等则返回0
  else return 1; //num更大,则返回1
}
LL binarySearch(char N2[],LL left ,LL right ,LL t){ //二分求解N2的进制
  LL mid;
  while(left<=right){
    mid=(left+right)/2;
    int flag=cmp(N2,mid,t); //判断N2转换成十进制后与t比较
    if(flag==0) return mid; //找到解,则返回mid
    else if(flag==-1) left=mid+1; //往右子区间继续查找
    else right=mid-1; //往左子区间继续查找
  }
  return -1; //解不存在
}
int findLargestDigit(char N2[]){ //求最大的数位
  int ans=-1,len=strlen(N2);
  for(int i=0;i<len;i++){
    if(Map[N2[i]]>ans){
      ans=Map[N2[i]];
    }
  }
  return ans+1; //最大的数位为ans,说明进制数的底线是ans+1
}
char N1[20],N2[20],temp[20];
int tag,radix;
int main(){   
  init();
  scanf("%s %s %d %d",N1,N2,&tag,&radix);
  if(tag==2){ //交换N1和N2
    strcpy(temp,N1);
    strcpy(N1,N2);
    strcpy(N2,temp);
  }
  LL t=convertNum10(N1,radix,inf);  //将N1从radix进制转换成十进制
  LL low=findLargestDigit(N2); //找到N2中数位最大的位加1,作为二分下界
  LL high=max(low,t)+1; //上界,用更小的进制基数即可
  LL ans=binarySearch(N2,low,high,t);  //二分
  if(ans==-1)  printf("Impossible\n");
  else printf("%lld\n",ans);
    return 0;   
}

4.注意点

(1)使用遍历进制的暴力枚举会超时。

(2)变量尽量使用long long类型;

对未知进制的数在转换成十进制时判断是否溢出(只要在转换过程中某步小于0即为溢出)。

(3)当N1和N2的十进制相同时,输出N2的radix值。

(4)边界处理:N2进制的下界为所有数位中最大的那个加1,上界=max{下界,N2的十进制}+1—假设已知的是N1的进制。

——可以举栗子:N1=6(10进制),N2=110(求是多少进制时和N1的十进制相同),按照上面的上下界则是2~7,2=1+1,7=max{2,6}+1,上界相当于在N1的最大的数位的基础上加1(毕竟题目问的是满足条件的最小进制)。

相关文章
|
人工智能 运维 安全
智能体(Agent)平台介绍
2023年11月9日,比尔盖茨先生发布了《人工智能即将彻底改变你使用计算机的方式》文章,详尽阐明了Agent(智能体)这个新一代智能应用的技术理念。在个人助理、卫生保健、教育、生产率、娱乐购物、科技等领域有着广泛的应用场景,对于开发者而言是个巨大的机会, 本篇文章尝试从系统化的角度解决构建Agent的问题,探讨Agent平台化的方案。
9039 2
智能体(Agent)平台介绍
|
算法
如何获取彩色图像中的主色彩
如何获取彩色图像中的主色彩
101 2
|
1天前
|
云安全 数据采集 人工智能
古茗联名引爆全网,阿里云三层防护助力对抗黑产
阿里云三层校验+风险识别,为古茗每一杯奶茶保驾护航!
古茗联名引爆全网,阿里云三层防护助力对抗黑产
|
5天前
|
人工智能 中间件 API
AutoGen for .NET - 架构学习指南
《AutoGen for .NET 架构学习指南》系统解析微软多智能体框架,涵盖新旧双架构、核心设计、技术栈与实战路径,助你从入门到精通,构建分布式AI协同系统。
296 142
|
5天前
|
Kubernetes 算法 Go
Kubeflow-Katib-架构学习指南
本指南带你深入 Kubeflow 核心组件 Katib,一个 Kubernetes 原生的自动化机器学习系统。从架构解析、代码结构到技能清单与学习路径,助你由浅入深掌握超参数调优与神经架构搜索,实现从使用到贡献的进阶之旅。
278 139
|
1天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
264 0
|
2天前
|
传感器 人工智能 算法
数字孪生智慧水务系统,三维立体平台,沃思智能
智慧水务系统融合物联网、数字孪生与AI技术,实现供水全流程智能监测、预测性维护与动态优化。通过实时数据采集与三维建模,提升漏损控制、节能降耗与应急响应能力,推动水务管理从经验驱动迈向数据驱动,助力城市水资源精细化、可持续化管理。
251 142
|
1天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段四:学术分析 AI 项目 RAG 落地指南:基于 Spring AI 的本地与阿里云知识库实践
本文介绍RAG(检索增强生成)技术,结合Spring AI与本地及云知识库实现学术分析AI应用,利用阿里云Qwen-Plus模型提升回答准确性与可信度。
167 90
AI 超级智能体全栈项目阶段四:学术分析 AI 项目 RAG 落地指南:基于 Spring AI 的本地与阿里云知识库实践
|
16天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!