蓝桥杯每日一题2023.9.16

古城微笑少年丶 2024-03-26 23:40 73阅读 0赞

[蓝桥杯2022年第十三届省赛真题-X进制减法 - C语言网 (dotcpp.com)][2022_-X_ - C_ _dotcpp.com]

### 题目描述 ###

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

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

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

请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。

### 分析 ###

![773ddecc5cc34ba0b7f5993ab44db910.jpeg][]

**可知对于A - B取到最小值需要其进制数取到最小**

**（以下为参考文章)**

选取最小进制  
选取其中最大的进制是因为A与B同进制，要保证进制合法  
因此两者数据间只有选最大的那个数据才能保证两者相同  
比如 6与8,我们只有选择8的进制我们才能同步两者的进制.  
是在保证进制合法的情况下选择最小的进制  
而题目意思中的十进制输入只是我们认为输入的数据，但是题设中的意思是我们实际上不知道它是什么进制  
而为了所求相减最小，我们就选最小的进制，也就是保证两者相同时选择最小的进制，也就是加1.  
加1是因为如果仅仅赋值输入的数据不可能的，注意有进位这个东西，不加1数据早就进位了  
如我们看到的9这个数字,那么它最小的进制只可能是10，如果是9进制,是会直接进位的，  
这样我们是看不见这个数字9的，看见的是进位后的结果

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 10, M = 1000000007; 
    ll n, ma, mb, sum, a[N], b[N], jz[N];
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> n;
    	cin >> ma;
    	for(int i = ma; i >= 1; i --)cin >> a[i];
    	cin >> mb;
    	for(int i = mb; i >= 1; i --)cin >> b[i];
    	//以下为找最小进制的过程，由于A >= B 
    	for(int i = ma; i >= 1; i --)
    	{
    		jz[i] = max(max(a[i] + 1, b[i] + 1), 2ll);//最小为二进制 
    	}
    	for(int i = ma; i >= 2;  i--)
    	{
    		sum = ((sum + a[i] - b[i]) * jz[i - 1]) % M; 
    	}
    	sum += (a[1] - b[1]);//最低为直接将结果加起来 
    	sum %= M;
    	cout << sum;
    	return 0;
    }

[2022_-X_ - C_ _dotcpp.com]: https://www.dotcpp.com/oj/problem2658.html
[773ddecc5cc34ba0b7f5993ab44db910.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/0e7cb00643d843449016db7ce8cedaaa.png