1010 Radix
目录
总结
解题过程
总结
1. 短小精悍的一道二分算法题，总体思路是，将字符串1(如果tag不是1将两个字符串调换一下即可)转化为10进制，再用二分法看能否找到另一个进制使得两个字符串的10进制数相等。
2. 本题的三个函数关系是binarySearch调用cmp,cmp调用getDec,其中getDec是用来吧已知进制的数转化成十进制，但是转化成十进制中有可能会超过LL的范围(字符串一保证不会，虽然题中没说)，也就是溢出，会得到负数，如果溢出了说明必然是n2>n1，可以把这种情况和n2>n1并列返回一个特殊的数1。那么cmp接收到1也就知道n2>n1。
3. 这道题还给我的一个启发是，二分法虽然要求单调函数的背景，但是这个单调函数未必要一步到位，可以通过嵌套来降低难度，只是要做好单元测试。
一些细节：
1.这道题已经出现了很多long long，不妨将有可能超过int的数据类型全部改成LL，防止运算过程错误。
2.对于二分查找的下界，应该是字符串2当中达到的最高位数加一，上界应该是max(下界，字符串1对应的10进制数)。这个比较难想到。
3.把字符转化成数字的数组LL Map[128]，(1)用字符做下标巧妙利用了系统强制类型转换，(2)另写用来初始化这个数组的函数init()容易忘记调用，(3)对于a-z的赋值，记得加10。
解题过程
第一次的想法是，二分法里面的单调函数放把确定进制的字符串转化为十进制数的函数。也就是下面的getDec()，然后我设想的二分区间是[2,100]，得到如下代码。得分为22/25。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int maxn = 10;
const int INF = 1000000000;//INF:下确界
const int SUP = (1LL<<63)-1;//SUP:上确界
const double eps = 1e-5;LL getDec(char A[],int radix){//随着radix的值增大， 得到的res值也会增大 int len = strlen(A);LL res = 0;for(int i=0;i<len;i++){int temp;if(A[i]>='0'&&A[i]<='9')temp = A[i]-'0';if(A[i]>='a'&&A[i]<='z')temp = A[i]-'a'+10; res = res*radix + temp; }return res;
}int binarySearch(char B[],LL x){int l=2,r=200,mid;while(l<=r){mid = l+(r-l)/2;if(getDec(B,mid)==x)return mid;if(getDec(B,mid)>x){r = mid - 1;}else{l = mid + 1;}}return -1;
}int main(){char n1[20],n2[20];int tag,radix;scanf("%s %s %d %d",n1,n2,&tag,&radix);if(tag == 2){//默认tag等于1，不然就交换 char temp[20];strcpy(temp,n1);strcpy(n1,n2);strcpy(n2,temp);}LL x = getDec(n1,radix);int res = binarySearch(n2,x);if(res == -1)printf("Impossible\n");else printf("%d\n",res);return 0;
}这个想法显然有问题，首先，没有考虑到换算成十进制的过程可能产生溢出，其次，二分区间并非是[2,100]。于是查了参考书，写出如下AC代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int maxn = 10;
const int INF = 1000000000;//INF:下确界
const LL SUP = (1LL<<63)-1;//SUP:上确界
const double eps = 1e-5;LL Map[128];void init(){//初始化字符映射数组，方面用于进制的数字表示 0-9对应0-9 a-z对应10-35 for(char c='0';c<='9';c++){Map[c] = c - '0';}for(char c='a';c<='z';c++){Map[c] = c - 'a'+10;//加10容易漏 }
}LL getDec(char A[],LL radix,LL ceil){//需要判断是否溢出 int len = strlen(A);LL res = 0;for(int i=0;i<len;i++){res = res*radix + Map[A[i]];if(res<0||res>ceil)return -1;//溢出或者是超过N1的十进制 }return res;
}int cmp(char B[],LL radix,LL ceil){int len = strlen(B);LL num = getDec(B,radix,ceil);if(num==-1)return 1;//说明n2>n1if(num<ceil)return -1;//n2<n1else if(num == ceil)return 0;//n2==n1else return 1;//n2>n1
}LL binarySearch(char B[],LL l,LL r,LL x){LL mid;while(l<=r){mid = l+(r-l)/2;if(cmp(B,mid,x)==0)return mid;if(cmp(B,mid,x)>0){r = mid - 1;}else{l = mid + 1;}}return -1;
}LL getLowerbound(char B[]){int len = strlen(B);LL res = 0;for(int i=0;i<len;i++){res = max(res,Map[B[i]]);}return res+1;//res是最大数位，二分区间要从res+1开始
}int main(){char n1[20],n2[20];int tag,radix;scanf("%s %s %d %d",n1,n2,&tag,&radix);if(tag == 2){//默认tag等于1，不然就交换 char temp[20];strcpy(temp,n1);strcpy(n1,n2);strcpy(n2,temp);}init();LL x = getDec(n1,radix,SUP);LL l = getLowerbound(n2);LL r = max(l,x);LL res = binarySearch(n2,l,r,x);if(res == -1)printf("Impossible\n");else printf("%lld\n",res);return 0;
}彩、蛋、(2021/9/10记)
时隔两个月再做，重温了判断LL型溢出的两种可能还有字符哈希，采用了比较函数，加入特判如果L1溢出直接返回L1更大，但是得分16，便对称地加入判断L2是否溢出，于是AC。
找不找得到可以通过二分查找函数BS是否返回-1来判断，自己再想个判断依据很容易出错。
AC代码
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>using namespace std;typedef long long LL;const int maxn = 20;
const LL SUP = (1LL<<63)-1;LL ctl[256];// char to LLvoid init(){for(char c='0';c<='9';c++){ctl[c] = c-'0';}for(char c='a';c<='z';c++){ctl[c] = c-'a'+10;}return;
}LL getDec(string str,LL radix){LL res = 0;for(int i=0;i<str.length();i++){res = res*radix + ctl[str[i]];if(res<0||res>SUP)return -1;}return res;
}LL getMinL(string str){LL minL = -1;for(int i=0;i<str.length();i++){minL = max(minL,ctl[str[i]]);}return minL+1;
}int cmp(LL L1,string N2,LL radix){if(L1==-1)return 1;//L1>L2LL L2 = getDec(N2,radix);if(L2==-1)return -1;if(L1==L2)return 0;//L1==L2else if(L1<L2)return -1;//L1<L2else return 1;//L1>L2
}LL BS(LL l,LL r,LL L1,string N2){LL m;while(l<=r){m = (r-l)/2+l;if(cmp(L1,N2,m)==0)return m;if(cmp(L1,N2,m)==1)l = m+1;else if(cmp(L1,N2,m)==-1)r = m-1;}return -1;
}int main(){ init();string N1,N2;LL tag,radix;cin>>N1>>N2>>tag>>radix;if(N1==N2){cout<<radix;return 0;}if(tag==2)swap(N1,N2);LL L1 = getDec(N1,radix);LL minL = getMinL(N2);LL right = max(L1,minL)+1;LL ans = BS(minL,right,L1,N2);if(ans==-1)printf("Impossible\n");else printf("%lld",ans);return 0;
}相关文章：
喜闻乐见的const int *p、int* const p、const int* const p
不废话直接代码示例： 1 void f(const int *p) {2 3 int b 10;4 5 *p 10; // error6 7 p &b; // fine8 9 } 10 11 void f(int* const p) { 12 13 int b 10; 14 15 *p 10; // fine 16 17 p &b; // error 18 19 } 20 21 v…
Microsoft Visual Studio 2012 添加实体数据模型
Microsoft Visual Studio 2012 添加实体数据模型 1、创建一个web项目 2、添加ADO实体数据模型，如下图： 3、选择 从数据库生成，然后下一步 4、新建连接，如下图： 5、填写服务器名等，如下图： 6、选…
5.1软件升级的小阳春
现在正在去白山的车上，刚睡醒。习惯性的拿出手机上网，UCWEB提醒有最新版本升级，使用尚邮接收邮件的时候同样提醒有信版本升级。 公司产品9.0也正式完成，昨天整个小组的同事开始在领地咖啡馆，进行新需求的确认。 4月末5…
1030 完美数列(二分解法)
1. 将整型序列从小到大排序后，这道题的本质是，对于每一个元素i，找出最后一个满足p*A[i]>A[j]的元素j，可以转化为找出第一个不满足p*A[i]>A[j]也即p*A[i]<A[j]的元素j。再用j-1。 2.LL product (LL)p*A[i];这里后面两个…
javascript变量声明 及作用域
javascript变量声明提升(hoisting) http://openwares.net/js/javascript_declaration_hoisting.html 可能要FQ一下 javascript的变量声明具有hoisting机制，JavaScript引擎在执行的时候，会把所有变量的声明都提升到当前作用域的最前面。 先看一段代码 123…
【转载】全面理解javascript的caller,callee,call,apply概念(修改版)
今天写PPlayer，发现有段代码引起了我的兴趣： var Class { create: function() { return function() { this.initialize.apply(this, arguments); } } } 这是高手写的，实现了创建一个类（其实就是对象，函数对象…
springMVC自定义全局异常
SpringMVC通过HandlerExceptionResolver处理程序异常，包括Handler映射，数据绑定以及目标方法执行时所发生的异常。 SpringMVC中默认是没有加装载HandlerExceptionResolver，我们需要在SpringMVC.xml中配置 <mvc:annotation-driven /> 1、…
1030 完美数列(two pointers解法)
1. 这道题出现在二分法，但是特殊之处在于，双指针是嵌套的，程序看上去有些像暴力枚举，但其实是利用了，如果i<j，a[i]*p>a[j]，那么一定有k在[i,j]范围内，a[i]*p>a[k]ÿ…
alsa声卡切换
环境 ubuntu12.04 因为桌面版的默认装了，而且调声音也很方便，这里说一下server版下的配置，毕竟做开发经常还是用server版的 1.安装 apt-get install alsa-base 它会把alsa-utils也一块装了，这是个工具包，如果没装的话 …
asp.net获取网站路径
网站在服务器磁盘上的物理路径: HttpRuntime.AppDomainAppPath 虚拟程序路径: HttpRuntime.AppDomainAppVirtualPath 任何于Request/HttpContext.Current等相关的方法, 都只能在有请求上下文或者页面时使用. 即在无请求上下文时,HttpContext.Current为null. 而上面提到的方法一…
iOS 绘制圆角
级别： ★☆☆☆☆ 标签：「iOS切圆角」「layer圆角」「CAShapeLayer圆角」 作者： XsH 审校： QiShare团队 项目中会常有圆角（或圆形）显示视图的需求（比如用户头像的显示），也…
(C++)归并排序的递归与非递归实现
递归实现 merge函数利用的是双指针技巧降低复杂度。 mergeSort函数使用了递归，当中先对左右序列各调用一次mergeSort，再对整个序列调用merge。就按照最浅层的归并的思想去理解，不要大脑走到哪就step in。 另外mergeSort进入递归有个left&l…
SnackbarUtilDemo【Snackbar的封装类】
版权声明：本文为HaiyuKing原创文章，转载请注明出处！ 前言 这个工具类参考的是《没时间解释了，快使用Snackbar!——Android Snackbar花式使用指南》，代码几乎一样，所以想要了解具体原理或者更详细信息请阅读…
java通过代理访问网络
使用代理方式连接到网络 Testpublic void t13(){String charset "utf-8" ; String proxyHost "代理地址" ; int proxyPort 1234 ; //代理端口String proxyUrsername "登陆代理服务器的用户名" ; String proxyPassword "登陆代理服务器…
poj2503 Babelfish
跟poj3349很类似的题目，这题还稍简单。用qsort快速排序和二分查找可以很轻松AC。以下是代码： Run IDUserProblemResultMemoryTimeLanguageCode LengthSubmit Time5135234zen_chou2503Accepted2356K547MSC1212B2009-05-11 20:12:26Code1 #include <std…
(C语言)一种简易记法：生成[a,b]范围内的随机整数
1. 添加头文件 #include<stdlib.h> #include<time.h> 2. 初始化随机种子 srand((unsigned)time(NULL)); 3. 确定元素个数b-a1，以及最小元素 printf("%d",rand()%(b-a1)a);//生成[a,b]之间的数 printf("%d",rand()%1001);//生成…
IE和火狐都支持的方法(输入用户名和密码后按下 enter 键)
在Firefox中老报"event is not defined”错误！原因是因为在Firefox中使用了不同的事件对象模型,不同于IE Dom，用的是W3C Dom。 document.οnkeydοwnfunction mykeyDown(e){ //compatible IE and firefox because there is not event in fir…
数据库中存储与读取文件
if exists (select * from dbo.sysobjects where id object_id(N[dbo].[p_binaryIO]) and OBJECTPROPERTY(id, NIsProcedure) 1)drop procedure [dbo].[p_binaryIO]GO /*--bcp 实现二进制文件的导入导出 支持image,text,ntext字段的导入/导出 image适合于二进制文件,包括:Wor…
洛谷P3723 [AH2017/HNOI2017]礼物（FFT）
传送门 首先，两个数同时增加自然数值相当于只有其中一个数增加（此增加量可以小于0） 我们令$x$为当前的增加量，${a},{b}$分别为旋转后的两个数列，那么$$ans\sum_{i1}^n(a_ix-b_i)^2$$ 然后把第$i$项提出来并展开&#x…
1035 插入与归并
1. 这一题，首先要会插入排序和归并排序的写法。对于归并排序，可以用非递归sort最简便。把每一趟的结果存进二维数组。 2. 单独封装一个函数，比较两个一维数组是否完全一样。 3. 由于归并比插入的复杂度低，趟数少，所以…
代码设置LinearLayout的高度
问题描述我想把这个LinearLayout宽度设置成为FILL_PARENT，源码如下LinearLayout checkboxLinearLayout (LinearLayout) getLayoutInflater().inflate(R.layout.checkboxdoitem, null);LayoutParams params (LayoutParams) checkboxLinearLayout.getLayoutParams();…
精通Spring Boot —— 第十五篇：使用@ControllerAdvice处理异常
在Spring 3.2中，新增了ControllerAdvice、RestControllerAdvice 注解，可以用于定义ExceptionHandler、InitBinder、ModelAttribute，并应用到所有RequestMapping、PostMapping， GetMapping注解中。接下来我将通过代码展示如何使用这…
架构设计之分布式文件系统
1：类图 2：数据结构 create table TBCOFILE ( FILEID INTEGER not null, FILETIME DATE, TYPE VARCHAR2(10), USERID INTEGER, IP VARCHAR2(20), APPTYPE INTEGER default 0) 3：开发步骤 1：从数据库申…
1029 Median
1. 开始测试点3和6答案错误，原因是没有考虑到，给的两个数列有可能长度相差很大，某个数列还没到中位数，就结束了。 2. 这题的底子是用two pointers按照非递减的顺序合并两个数列，无非是再确定一下中间那个数的下标&…
理解系统底层的概念是多么重要
理解系统底层的概念是多么重要 ——趋势科技邹飞评《程序员的自我修养》 关于《程序员的自我修养》这本书，最初是在和博文的周筠老师MSN上谈起，当时听周老师提及这本书是一本关于链接和装载等系统软件知识的书籍，当时就很感兴趣，因…
session删除
删除一个session值： session_unset(变量); session_destroy(变量); 删除一个cookie： 注意第二个参数中手册中的说明是： Cookie 必须用和设定时的同样的参数才能删除。如果其值一个空字符串，或者是 FALSE，并且其它的参数…
Android学习路线
Android学习路线 第一阶段：Java面向对象编程 1.Java基本数据类型与表达式，分支循环。 2.String和StringBuffer的使用、正则表达式。 3.面向对象的抽象，封装，继承，多态，类与对象，对象初始化和回…
1048 Find Coins(two pointers解法)
1. 很典型的双指针的应用，将数组按照非降排列，两个指针从一头一尾开始包抄，若等于（等于要放在第一个）则返回结果结束程序，小于则左指针右移，大于则右指针左移。 2. 起初还担心，如果…
TCP/IP 协议理解
TCP/IP 协议（Transmission Control Protocol / internet Protocol），因特网互联协议，又名网络通讯协议。通俗而言：TCP负责发现传输的问题，一有问题就发出信号，要求重新传输，直到所有数…
Webhint开源了一种代码检查工具
Webhint项目提供了一种用于检查代码的可访问性、性能和安全的开源检查（Linting）工具。在创建Web站点和应用中，有越来越多的细节问题亟待完善。为此，Webhint力图帮助开发人员标记这些细节。\\Webhint以命令行接口（CLI&a…