X进制减法(蓝桥杯) | 您所在的位置:网站首页 › 二进制是满几进一 › X进制减法(蓝桥杯) |
文章目录
X进制减法题目描述解题思路贪心算法+模拟减法(大数相减)
X进制减法
题目描述
进制规定了数字在数位上逢几进一。 X 进制是一种很神奇的进制,因为其每一数位的进制并不固定!例如说某种 X 进制数,最低数位为二进制,第二数位为十进制,第三数位为八进制,则X 进制数 321 转换为十进制数为 65。 现在有两个 X 进制表示的整数 A 和 B,但是其具体每一数位的进制还不确定,只知道 A 和 B 是同一进制规则,且每一数位最高为 N 进制,最低为二进制。请你算出 A B 的结果最小可能是多少。 请注意,你需要保证 A 和 B 在 X 进制下都是合法的,即每一数位上的数字要小于其进制。 输入格式 第一行一个正整数 N,含义如题面所述。 第二行一个正整数 Ma,表示 X 进制数 A 的位数。 第三行 Ma 个用空格分开的整数,表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。 第四行一个正整数 Mb,表示 X 进制数 B 的位数。 第五行 Mb 个用空格分开的整数,表示 X 进制数 B 按从高位到低位顺序各 个数位上的数字在十进制下的表示。 请注意,输入中的所有数字都是十进制的。 输出格式 输出一行一个整数,表示 X 进制数 A B 的结果的最小可能值转换为十进制后再模 1000000007 的结果。 样例输入 11 3 10 4 0 3 1 2 0样例输出 94样例说明 当进制为:最低位 2 进制,第二数位 5 进制,第三数位 11 进制时,减法得到的差最小。此时 A 在十进制下是 108,B 在十进制下是 14,差值是 94。 X进制数321转换为十进制数为65. 65=3*(2*10)+2*(2)+1*(1)评测用例规模与约定 对于 30% 的数据,N ≤ 10; Ma, Mb ≤ 8. 对于 100% 的数据,2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B. 解题思路对于输入样例,若选取第三数位11进制,第二数位5进制,第一数位2进制 计算规则上所示,每个数位可任意选择一个进制(要求进制数大于当前位数的数值,例如当前位数的数位5,那么最小的进制数只能为6 考虑A-B要求最小,贪心考虑,即要满足每一位数的进制数要最小,因此很容易得出,每一数位的进制数大小是多少(A,B对位后,取数位上的数值最大的一个+1即为当前数位的进制位,如果取最小的,那另一个数就不满足该进制),但注意最低为2进制,因为不存在1进制。 样例 10 4 0 1 2 0最高位分别为10和1,那么该数位取10+1=11进制 次高位分别为4和2,那么该数位取4+1=5进制 最低位分别为0和0,那么该数位取2进制 最后数位对齐,模拟减法即可 重点:贪心、理解进制、模拟减法 贪心算法+模拟减法(大数相减)这段代码的目的是计算两个特定进制(X进制)数A和B之间的差,并将这个差以十进制数表示,最后对结果取模1000000007。这个特定的进制系统比较复杂,因为它允许每一位数的进制不同,从二进制开始,最高可达N进制。下面是对代码各个部分的详细注释和执行流程解释。 // 引入所有标准库 #include // 使用标准命名空间 using namespace std; // 定义模数 const int mod=1000000007; // 数组a,b用于存储两个输入数A和B,数组s用于存储每位的最小可能进制 long long a[100010],b[100010],s[100010]; // n为最高进制,ma和mb分别为A和B的位数 int n,ma,mb; // 函数sub用于执行具体的减法操作并返回结果 vector sub() { // base用于进位处理,初始为1 long long base=1; vector c; // 存储计算结果 long long t=0; // 临时变量t用于处理借位和计算过程中的中间结果 // 遍历所有位进行减法操作 for(int i=0;i // 输入处理 cin>>n>>ma; for(int i=ma-1;i>=0;i--) cin>>a[i]; cin>>mb; for(int i=mb-1;i>=0;i--) cin>>b[i]; // 计算每位的最小可能进制 for(int i=ma-1;i>=0;i--)//因为A>=B,所以得出ma>=mb s[i]=max(max(a[i],b[i])+1,(long long)2); // 调用sub函数计算A-B的结果 auto c=sub(); // 将结果转换为十进制并取模 long long ans=0; for(int i=c.size()-1;i>=0;i--) ans=(ans+c[i])%mod; // 输出结果 cout |
CopyRight 2018-2019 实验室设备网 版权所有 |