【蓝桥杯每日一题】X 进制减法

X 进制减法

2024-12-6 蓝桥杯每日一题 X 进制减法 贪心 进制转换

题目大意

进制规定了数字在数位上逢几进一。

XX 进制是一种很神奇的进制, 因为其每一数位的进制并不固定！例如说某 种 XX 进制数, 最低数位为二进制, 第二数位为十进制, 第三数位为八进制, 则 XX 进制数 321 转换为十进制数为 65 。

现在有两个 XX 进制表示的整数 AA 和 BB, 但是其具体每一数位的进制还不确 定, 只知道 AA 和 BB 是同一进制规则, 且每一数位最高为 NN 进制, 最低为二进 制。请你算出 A−BA−B 的结果最小可能是多少。

请注意, 你需要保证 AA 和 BB 在 XX 进制下都是合法的, 即每一数位上的数 字要小于其进制。

解题思路

刚开始看这道题的时候是没有看懂X 进制数是怎么转换成十进制的。

先来看一个二进制数怎么转换成十进制：

​ $11111=>1\ast 2\ast 2\ast 2\ast 2+1\ast 2\ast 2\ast 2+12\ast 2+1\ast 2+1=31$

注意观察到，因为这个11111的每一位都是作为二进制的数，那么在计算的时候它需要乘上当前位置前后面的所有2 不包括自己。

类比本题的例子来说：

​ $321=>3\ast 10\ast 2+2\ast 2+1=65$

同样是某一位上的数num[i] * 它后面所有的进制

之后就是先判断这个每一位对应的进制，由于想要最小值，那么由以上的计算过程可知，只需让每一个进制取到最小值即可，当然最小是二进制。

代码相关解释都在注释中。

Accepted

#include <iostream>

using namespace std;
typedef long long ll;
const int N = 100010,mod = 1000000007;
int a[N],b[N],n,m;
ll c[N];    // 存储进制前缀积

int main()
{
    cin>>n>>m;
    for(int i = m;i >= 1;i--) {
        cin>>a[i];
    }
    int len = m;
    cin>>m;
    for(int i = m;i >= 1;i--) {
        cin>>b[i];
    }
    c[0] = 1;
    len = len > m ? len : m;    
    for(int i = 1;i <= len;i++) {
        // 确定进制
        int t = max(a[i],b[i]);
        c[i] = max(2,t+1);
        c[i] = c[i-1]*c[i] % mod;   // 计算前缀积
    }
    ll res = 0;
    for(int i = 1;i <=  len;i++) {
        res = (res+(a[i]-b[i])*c[i-1]%mod)%mod;
    }
    // 虽然题目中表明A > B但是取模之后的值不一定是A大，所以最后要做将负数转为正值的操作
    // 那么先加mod就是为了补充A的不足而加的
    // 最后为了防止res的值为负，进行加mod再取模，将其转换为正值4.如果不处理这点会过50%
    cout<<(res + mod) % mod<<endl;
    return 0;
}

想要一起备赛的小伙伴可以私信加我的联系方式！

原文地址：https://blog.csdn.net/2301_76605150/article/details/144292774

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！