X进制减法(贪心算法C++实现)
题目
进制规定了数字在数位上逢几进一。
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
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010,MOD = 1000000007;
int q1[N],q2[N],q[N];
int n,a,b;int main(){scanf("%d",&n);scanf("%d",&a);for(int i=a-1;i>=0;i--) scanf("%d",&q1[i]);scanf("%d",&b);for(int i=b-1;i>=0;i--) scanf("%d",&q2[i]);int m = max(a,b);long long res = 0;for(int i=m-1;i>=0;i--){res = (res * (long long)max({2,q1[i]+1,q2[i]+1})+q1[i]-q2[i]) % MOD;}printf("%lld",res);
}