【2022年省赛B组】试题E:X进制减法

题解

数字$A$的第$i$位记为$a_i$，$A=[a_1, a_2, \cdots, a_{M_a}]$。

数字$B$的第$i$位记为$b_i$，$B=[b_1, b_2, \cdots, b_{M_b}]$。

由于$A \geqslant B$, 可以推出$M_a \geqslant M_b$。

对于数字$B$而言，将$B$的高位补上$M_a - M_b$个0，

即$B=[b_1, b_2, \cdots, b_{M_{b}}, 0, \cdots, 0]$, 这样可以保证两个数字长度相同，便于后面做减法。

根据题目$X$进制的定义，记第$i$位的进制为$k_i$。以题面$X$进制数$C=321$为例，第一、二、三进制分别为$k_1=2, k_2=10, k_3 = 8。C=[c_1=1, c_2=2, c_3=3]$，转换成10进制时：对于$c_1$而言，需要乘上1，对于$c_2$而言，需要乘上2，对于$c_3$而而言，需要乘上$2 \times 10$,即：

$$c_1 \times 1 + c_2 \times k_1 + c_3 \times k_1 \times k_2 = 65 $$$$3 \times 2 \times 10 + 2 \times 2 + 1 \times 1 = 65 $$

上述展示了$X$进制转换成10进制的算法，以$A$为例，对于$A$的第$i$为而言，每增加1相当于十进制增加$k_1 \times k_2 \times \cdots \times k_{i - 1}$。那么数字$A$的十进制等于$\sum\limits_{i = 1} ^{M_a} a_i (\prod\limits_{j = 0} ^ {i - 1} k_j)$。其中$k_1, k_2, \cdots, k_{M_a}$表示每一位单独的进制，特殊地，$k_0 = 1$。

同理，$B也可以类似求解。题目要求$$A-B$的最小值，利用上式可以得到：

$$A-B=\sum\limits_{i = 1}^{M_a} (a_i - b_i) \times (\prod\limits_{j = 0} ^ {i - 1} k_j) $$

🚀️ 如果$a_i > b_i$， 利用贪心思想，要保持差最小，只需要让每一位的进制最小即可，这样就可以保证连乘的进制最小化。

🚀️ 如果$a_i < b_i$, 也等价于上述做法。因为整体数字$A>B$， 一定可以把$A$的某些高位借到低位(借位不会改变$A$， 也不会改变$A-B$的结果)，从而保证所有的$a_i > b_i$。此时只要让每一位的进制尽可能小即可。

每一位进制最小化，相当于对于第$i$位，进制$k_i=\max{(\max{(a[i] + 1, b[i] + 1)}, 2)}$, 此时才能保证该进制下可以出现数字$a_i, b_i$。 实现时注意取余，避免运算溢出。

提交代码

• 数组版本

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 10;
 
ll a[maxn], b[maxn];
 
int main(){
    int N;
    cin >> N;
    int Ma, Mb;
    cin >> Ma;
    for(int i = 1; i <= Ma; i++)//输入顺序是从高位到低位
        cin >> a[Ma + 1 - i];
    cin >> Mb;
    for(int i = 1; i <= Mb; i++)
        cin >> b[Mb + 1 - i];
    
    //ans表示差值，c表示进制
    ll ans = 0, c = 1;
    for(int i = 1; i <= max(Ma, Mb); i++){
        //对于第i位，计算最低进制
        ll now = max(max(a[i], b[i]) + 1, 2LL);
        //计算差值
        ans = (ans + (a[i] - b[i]) * c % MOD + MOD) % MOD;
        c = c * now % MOD;
    }
    cout<<ans<<endl;
    return 0;
}

• vector版本

#include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
void solve()
{
    int n; std::cin >> n;
    int m; std::cin >> m;
    
    std::vector<int> a(m);
    for(auto &x : a) std::cin >> x;
    std::reverse(a.begin(), a.end());
    
    int mb; std::cin >> mb;
    std::vector<int> b(mb);
    for(auto &x : b) std::cin >> x;
    std::reverse(b.begin(), b .end());
    
    int ans = 0;
    int prob = 1;
    for(int i = 0; i < m; i++)
    {
    	int scale = 2;
        if(i < mb) 
        {
        	ans = (ans + ((a[i] - b[i]) * prob % mod + mod) % mod) % mod;
        	scale = std::max(2LL, std::max(a[i], b[i]) + 1);
        }
        else 
        {
        	ans = (ans + prob * a[i]) % mod;
        	scale = std::max(2LL, a[i] + 1);
        }
        prob = prob * scale % mod;
    }
    std::cout << ans << "\n";
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1; 
    while(t--) solve();
    return 0;
}

// 11 5 2
// 0*1 + 4*2 + 10*5*2 = 108

// 1 2 0
// 11 5 2
// 0*1 + 2*2 + 1*5*2 = 14
//可以观察到对于每一位数字 当前位置的权重是之前的所有数位的权重之积
//我们只需最小化这个积 显然对于每一位只需取max(a[i], b[i]) + 1
//简单来说就是尽可能的最小化每一位的进制
#include<iostream>
#include<algorithm>
using namespace std;
int n, m1, m2;
const int N = 1e5 + 10, mod = 1e9 + 7;
int a[N], b[N];

int main()
{
    cin>>n;
    cin>>m1;
    for(int i = m1 - 1; i >= 0; i --)
        cin>>a[i];
    cin>>m2;
    for(int i = m2 - 1; i >= 0; i --)
        cin>>b[i];
    int m = max(m1, m2);//因为A和B的位数不一定相同
    int res = 0;
    for(int i = m - 1; i >= 0; i --)
        res = (res * (long long)max({2, a[i] + 1, b[i] + 1}) + a[i] - b[i]) % mod;
    cout<<res<<endl;
}

水个现代化C++20写法（什么时候gcc能上C++23啊）

#include <bits/stdc++.h>

using namespace std;

using i64 [[maybe_unused]] = long long;
template<typename T, class comparer = greater<T>>
using heap [[maybe_unused]] = priority_queue<T, vector<T>, comparer>;
const char &ln = '\n';

template<typename T>
T as [[maybe_unused]](const T &v) { return static_cast<T>(v); }

template<typename T, class Begin, class End>
void println [[maybe_unused]](Begin begin, End end, const char *c = " ") {
    copy(begin, end, ostream_iterator<T>(cout, c));
    cout.put('\n');
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int &mod = 1000000007;
    int n, len_a, len_b, len;
    cin >> n;
    // 逗号表达式，输入一个数，将该数作为表达式的结果返回，vector自动推断为 i64 类型
    vector a((cin >> len_a, len_a), 0ll);
    // C++11 基于范围的循环，C++20 views::reverse的功能是倒转范围（range）
    for (auto &&i: a | views::reverse)
        cin >> i;   // 倒转输入是为了方便计算
    vector b((cin >> len_b, len_b), 0ll);
    for (auto &&i: b | views::reverse)
        cin >> i;
    // a和b的位数不一定相同，取最值并高位补0
    len = max(len_a, len_b);
    a.resize(len, 0);
    b.resize(len, 0);
    // 模拟，计算
    i64 ans{}, power{1};
    // 相当于 for (int &&i = 0; i < len; ++i)
    for (auto &&i: views::iota(0, len)) {
        ans = (ans + (a[i] - b[i]) * power) % mod;
        power = power * max({2ll, a[i] + 1, b[i] + 1}) % mod;
    }
    cout << ans;
    return 0;
}