蓝桥杯2022年第十三届省赛真题-X进制减法
侧边栏壁纸
  • 累计撰写 37 篇文章
  • 累计收到 11 条评论

蓝桥杯2022年第十三届省赛真题-X进制减法

admin
2023-02-07 / 0 评论 / 526 阅读 / 正在检测是否收录...

题目
进制规定了数字在数位上逢几进一。

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。

对于 30% 的数据,N ≤ 10; Ma, Mb ≤ 8. 对于 100% 的数据,2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B.
分析
最后的数据肯定很大,我们sum采用long long;
输入的时候采用从大索引到小索引,数字从高位到低位,因为需要防止位数不对应
x进制转换成十进制的例子
321 题中给出分别为 8 10 2 进制
310*2+22+1

本题就只需要把高位每一位的差值控制到最小;
根据提示,我们可以找到规律,就是每一位的进制数就是max(a[i],b[i])+1;特别注意,还存在0,1这两种情况,我们采用二进制,所以得到的表达式是max(max(a[i]+1,b[i]+1),2);

设置数组的时候放到static中,这样直接初始化的时候全部元素都是0,如果在int main中就需要设置memset(a,0,sizeof(a));
最主要的算法如下

for(int i=ma;i>1;i--)
{
sum=(sum+a[i]+b[i])*max(max(a[i-1]+1,b[i-1]+1),2)%1000000007;
}

我们拿出示例
10 4 0
1 2 0
带入上面的算法中
我们可以得到sum=((0+10-1)5+4-2)2
简单化简可化为
sum=9*5*2+2*2

这里有个需要注意的,我们只循环了ma-1次,还有一个a[1],b[1]没有用
真正的sum还需要加上(a[1]-b[1]);
代码

#include<iostream>
#include<cmath>
using namespace std;
const int N=100010;
int a[N],b[N];
int main(){
  int ma,mb,n;
  cin>>n;
  cin>>ma;
  for(int i=ma;i>0;i--) cin>>a[i];
  cin>>mb;
  for(int i=mb;i>0;i--) cin>>b[i];
  long long sum=0;
  for(int i=ma;i>1;i--) sum=(sum+a[i]-b[i])*max(max(a[i-1]+1,b[i-1]+1),2)%1000000007;
  sum+=a[1]-b[1]%1000000007;
  cout<<sum<<endl;
  }

有问题,请斧正

0

评论 (0)

取消