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);
}