题目描述

blablabla

样例

blablabla

算法1： 贪心

由题可知：对于 $X$ 进制数 $321$，进制分别为 $8~10~2$，转化为十进制数为 $65$。
算式：$3·10·2~+~2·2~+~1~=~65$

假设, $A$ 和 $B$ 都是 $n$ 位数，分别是 $a_na_{n-1}···a_1$ 和 $b_nb_{n-1}···b_1$，对应的进制数 $X$ 分别是 $p_np_{n-1}···p_1$

由此可知：
$A$ 的十进制应为：$a_n·(p_{n-1}···p_1)~+~a_{n-1}·(p_{n-2}···p_1)~+···+~a_1$，
$B$ 的十进制应为：$b_n·(p_{n-1}···p_1)~+~b_{n-1}·(p_{n-2}···p_1)~+···+~b_1$，

所以，$A - B = (a_n-b_n)·(p_{n-1}···p_1)~+~(a_{n-1}-b_{n-1})·(p_{n-2}···p_1)~+···+~(a_1 - b_1)$

判断当 $a_n~≥~b_n$ 时，对应的进制数 $x_n$ 都尽可能的取小（最小为 $2$ ），就可以得出 $A−B$ 的最小值。

不过如果 $a_n~＜~b_n$ 时，$x_n$是否依然是尽可能取小呢，答案是肯定的。

如果 $a_n~＜~b_n$，我们让 $x_{n-1}$ 变大来使得最终值变小，假设在原 $x_{n-1}$ 的基础上增加 $x$ 那么在此位的值将减小 $(b_n-a_n)·(x·x_{n-2}···x_1)$，

注意到，题目在最后数据范围中给出 $A ≥ B$ 条件，说明如果存在 $a_n < b_n$ 的情况，那么在更高位一定存在 $a_m > b_m$，相应的，因为比 $n$ 更高位的每个数都要乘上这个$x_{n-1}$, 所以，想要使更高位的增值最小的情况是 $m = n + 1$，增值为 $(a_{n+1}-b_{n+1})·(x_n·x·x_{n-2}···x_1)$

将两次变化值相加得：$[~(a_{n+1}-b_{n+1})·x_n-(b_n-a_n)~]·(x·x_{n-2}···x_1)$

显然，$(x·x_{n-2}···x_1)~＞~0$，只需要判断 $(a_{n+1}-b_{n+1})·x_n-(b_n-a_n)$ 的正负。

因为，$a_{n+1}~＞~b_{n+1}$ 并且都为正整数，所以，$(a_{n+1}-b_{n+1})~≥~1$

又因为, $n$ 进制一定大于 $n$ 进制每一位的数，所以，$x_n>b_n>b_n-a_n$

所以，$(a_{n+1}-b_{n+1})·x_n-(b_n-a_n)~＞~0$

由此可知，最终值一定变大，故当$a_n~＜~b_n$ 时，$x_n$依然是要尽可能取小

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define N 100010

int n, ma, mb;
int a[N], b[N];
ll ans = 0, xn = 1;

int main() {
    cin >> n >> ma;
    for (int i = 1; i <= ma; i++) cin >> a[i];
    cin >> mb;
    for (int i = 1; i <= mb; i++) cin >> b[i];
    int i = ma, j = mb;
    while (i > 0) {
        ans += (a[i] - b[j]) * xn;
        ans %= mod;
        ll x = max(a[i], b[j]) + 1;
        xn *= max(x, 2ll);
        xn %= mod;
        i--;
        if (j) j--;
    }
    cout << ans;
    return 0;
}