思路
感觉这题很大一个难度在于怎么理解本题的进位方式
进位方式的理解:
最低数位为二进制,第二数位为十进制,第三数位为八进制,则 X 进制数 321 转换为十进制数为 65
1:到2的时候进位,2:到10的时候进位,3到8的时候进位
3(102)+2*2+1=65
怎么确定进制满足A-B最小的目的?
A和B在同一位数时,进制最小。当每一位进制都最小时,得到的A-B就是最小的。
求每一位最小的进制是多少?
A和B在同一位数i时,进制最小应该为在i位数时的数字中最大的那个数+1,即max(ma[i],mb[i])+1。但同时因为最低为二进制,所以得到的进制还需要跟2比较
代码
#include<iostream>
using namespace std;
const int N=100000+10;
typedef long long ll;
int n;//n进制
ll a,b;//a的位数,b的位数
ll ma[N],mb[N];
ll m[N];//进制
ll w[N];//权重
ll A,B;
ll mod=1000000007;
int main(){
cin>>n;
cin>>a;
for(int i=a;i>=1;i--) cin>>ma[i];
cin>>b;
for(int i=b;i>=1;i--) cin>>mb[i];
//求每一位的进制
int mm=max(a,b);
for(int i=mm;i>=1;i--){
m[i]=max(ma[i],mb[i]);
m[i]=max(m[i]+1,(ll)2);
}
w[1]=1;
for(int i=2;i<=mm;i++){
w[i]=w[i-1]*m[i-1]%mod;
}
for(int i=1;i<=a;i++){
A=(A+ma[i]*w[i])%mod;
}
for(int i=1;i<=b;i++){
B=(B+mb[i]*w[i])%mod;
}
cout<<(A-B+mod)%mod;
return 0;
}
tip:
感觉每个取模这里真的是一种好习惯,但凡题目要求说有取模的,最好都在相关的数字取模