本文主要是介绍关于PAT A1010 上界的理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A1010的其余代码我这里就不贴了,网上一大堆.
其中
long long high = max(low, t) + 1;
看了一圈就是搞不明白为啥上界就是这样算的.于是我决定冷静下来,自己好好想想.
思路如下:
N1,N2为字符串.
首先假定N1的转换为十进制后的数值为t.
倘若N2不止有一位
则其最小为"10", 故
当radix为t时N2最小为t,当radix大于t时,可易知N2不管怎样必不可能等于t.
倘若N2只有一位
要使其与t相等,则这唯一的一位必为t.radix可取t+1至无穷的任意一个数,都是一样的.而题目要求取最小的,故取t+1.
综上,上界取为t+1即可,倘若找不到那就是impossible.
上述讨论是t>low的情况,以下讨论t<=low的情况.
所谓low下届,即N2串中最大数字+1.不妨假设这个最大数字为x.则
1.low == t, 即 x == t-1.
这种情况下,N2只有一位是不可能与t相等的.那不止一位呢?又回到了之前说的,最小情况就是之前只有一个'1'.而此时radix由于下界的要求,至少为x+1,即为t, 这最小情况即让radix为t,得N2最小为t+x,若想其等于t,只能t为1,可是radix又不能为1呀!可知,第一种情况为impossible.
2.low > t, 即x >= t.
只有当x==t时且N2只有一位时才有可能相等,radix取x+1;当x>t时,二者必不相等.
不知不觉发现这些分析已经渐渐偏离我的本意了.那我就贴一下稍微有点新意的AC代码吧.大部分代码来自晴神的<算法笔记>.那些丑陋的代码就是我自己写的......
#include<stdio.h>
#include<string.h>
#define MAX_LEN (20)long long map[256] = {0};long long deci(char a[], int radix)
{long long result = 0;for(int i=0; a[i]; i++){result *= radix;result += map[a[i]];}return result;
}int cmp(char a[], long long radix, long long t)
{long long num = deci(a, radix);if(num < 0)return 1;else if(num > t)return 1;else if(num < t)return -1;elsereturn 0;
}long long binarysearch(char N2[], long long left, long long right, long long t)
{while(left <= right){long long mid = (left + right) / 2;switch(cmp(N2, mid, t)){case 0:return mid;case 1:right = mid - 1;break;case -1:left = mid + 1;break;default:break;}}return -1;
}int maxdigit(char a[])
{int max_digit = -1;for(int i=0; a[i]; i++)if(map[a[i]] > max_digit)max_digit = map[a[i]];return max_digit;
}int main()
{for(char c='0'; c<='9'; c++){map[c] = c-'0';}for(char c='a'; c<='z'; c++){map[c] = c-'a'+10;}char N1[MAX_LEN+1] = {0};char N2[MAX_LEN+1] = {0};int tag, radix1;scanf("%s %s %d %d", N1, N2, &tag, &radix1);if(tag == 2){char temp[MAX_LEN+1] = {0};strcpy(temp, N1);strcpy(N1, N2);strcpy(N2, temp);}long long t = deci(N1, radix1);long long low = maxdigit(N2) + 1;int N2_len = strlen(N2);long long radix2 = 0;if(t > low){if(N2_len == 1)if(map[N2[0]] == t)radix2 = t+1;elseradix2 = -1;elseradix2 = binarysearch(N2, low, t, t);}else if(t == low){radix2 = -1;}else if(t == low-1){if(N2_len == 1)radix2 = low;elseradix2 = -1;}else{radix2 = -1;}if(radix2 == -1)printf("Impossible");elseprintf("%lld", radix2);return 0;
}
这篇关于关于PAT A1010 上界的理解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
