个人博客内更好的阅读体验 请点击
题意费了好大劲才搞明白 这里x进制的计算方法不像传统那样 第几位乘以对应进制的几次方
也就是说传统的某一位n的权重是其进制$X^n$ 例如八进制第3位的权重是$8^2$
但本题不同 X进制某一位的权重是其后面几位进制的乘积
因为每一位的进制不同 那进到当前位的条件就不同
进位进到当前位的条件取决于低位的进制 而低位的进位取决于更低位的进制 这么讲非常抽象
例如321 第三位的权重就取决于其后面两位的进制 因为你要想进到第三位 你就必须要通过第1位的考验和第2位的考验 最终才能进到第3位
举个例子这和你闯关打boss一样 你想打到第三关 那么你就要通过第一关和第二关
假设第一关进制为$j$ 第二关进制为$i$
通过第一关的条件就是你比他的进制j大 这样你可以顺利进位到第二关
通过第二关的条件就是你比第二关的进制i大 这样你可以顺利进位到第三关
由于是不断递进的关系 所以我们第三关的权重就是 $i*j$
这个问题解决后 我们来处理怎么才能得到相减后的最小值
因为题目要求两个数的每一位的进制都是相同的 现在每一位上的数字都是已知的
那我们只需要让每一位的进制在符合条件的情况下最小 就能让A和B尽可能的小 他们的差也就会更小
那什么是符合条件的进制呢?
就是当前位上的数字小于当前位的进制 例如当前位数字是8 我们最小可以取9进制 程序中利用max()实现
本题需要注意的点就是数据范围很大 每一个运算语句最好都加上取余mod
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e5 + 10, mod = 1000000007;
typedef long long LL;
int a[M], b[M], w[M]; //a[]存储A各位的数字,b[]存储B各位的数字,w[]存储A和B各位的进制
int n, ma, mb;
LL mul[M]; //存储各位的实际权重 由于权重是当前位后面所有进制之积 M上限1e5 N上限1000 可能会溢出我们开longlong
LL A, B; //存一下数A和B的实际大小 以十进制表示
int main()
{
scanf("%d", &n);
scanf("%d", &ma);
for (int i = ma; i > 0; i -- ) scanf("%d", &a[i]); //倒序存储 最高位是第ma位
scanf("%d", &mb);
for (int i = mb; i > 0; i -- ) scanf("%d", &b[i]);
//确定各位的最小进制 进制最小是A和B当前位上的最大值+1
int mm = max(ma, mb); //先找到A和B中位数更大的那个数 的 最高位数
for (int i = 1; i <= mm; i ++ )
{
int tmax = max(a[i], b[i]);
w[i] = max(2, tmax + 1); //题目要求的最小进制是二进制 选出满足条件的当前位最小进制
}
//确定各位的权重 第i位的权重就是 第i-1位的权重*第i-1位的进制
mul[1] = 1; //最低位的权重是1
for (int i = 2; i <= mm; i ++ ) //从倒数第二位开始确定权重
{
mul[i] = (w[i - 1] * mul[i - 1]) % mod; //当前位的权重等于上一位的进制*上一位的权重 这也是i从小到大循环的原因 确保计算本位时 上一位的权重已经算过了 数据很大 取余mod
}
//分别计算A和B 第i位的值和第i位的权重相乘 最后累加 就能得到 A和B的十进制表示
for (int i = 1; i <= ma; i ++ )
{
A = (A + a[i] * mul[i]) % mod; //每一步都取余mod防止溢出
}
for (int i = 1; i <= mb; i ++ )
{
B = (B + b[i] * mul[i]) % mod;
}
printf("%lld\n", (A - B + mod) % mod); //这里在A-B后一定要+mod 否则可能本来A比B大 但由于多次取模后 A比B小了导致运算出现负值 所以我们在运算内再加上mod
return 0;
}
小坑
for (int i = 1; i <= mb; i ++ )
{
B = (B + b[i] * mul[i]) % mod;
}
不要写成B += (b[i] * mul[i]) % mod;
这样只能每次取余b[i] * mul[i]
的运算结果
但B还是会溢出
讲得很不错
hh谢谢🍻🍻