题目描述
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;
}