服務(wù)型網(wǎng)站的營(yíng)銷特點(diǎn)域名免費(fèi)注冊(cè)
X 進(jìn)制減法
2024-12-6 藍(lán)橋杯每日一題 X 進(jìn)制減法 貪心 進(jìn)制轉(zhuǎn)換
題目大意
進(jìn)制規(guī)定了數(shù)字在數(shù)位上逢幾進(jìn)一。
XX 進(jìn)制是一種很神奇的進(jìn)制, 因?yàn)槠涿恳粩?shù)位的進(jìn)制并不固定!例如說某 種 XX 進(jìn)制數(shù), 最低數(shù)位為二進(jìn)制, 第二數(shù)位為十進(jìn)制, 第三數(shù)位為八進(jìn)制, 則 XX 進(jìn)制數(shù) 321 轉(zhuǎn)換為十進(jìn)制數(shù)為 65 。
現(xiàn)在有兩個(gè) XX 進(jìn)制表示的整數(shù) AA 和 BB, 但是其具體每一數(shù)位的進(jìn)制還不確 定, 只知道 AA 和 BB 是同一進(jìn)制規(guī)則, 且每一數(shù)位最高為 NN 進(jìn)制, 最低為二進(jìn) 制。請(qǐng)你算出 A?BA?B 的結(jié)果最小可能是多少。
請(qǐng)注意, 你需要保證 AA 和 BB 在 XX 進(jìn)制下都是合法的, 即每一數(shù)位上的數(shù) 字要小于其進(jìn)制。
解題思路
剛開始看這道題的時(shí)候是沒有看懂X 進(jìn)制數(shù)是怎么轉(zhuǎn)換成十進(jìn)制的。
先來看一個(gè)二進(jìn)制數(shù)怎么轉(zhuǎn)換成十進(jìn)制:
? 11111 = > 1 ? 2 ? 2 ? 2 ? 2 + 1 ? 2 ? 2 ? 2 + 12 ? 2 + 1 ? 2 + 1 = 31 11111 => 1 * 2 * 2 * 2 * 2 + 1 * 2 * 2 * 2 + 1 2 * 2 + 1 * 2 + 1 = 31 11111=>1?2?2?2?2+1?2?2?2+12?2+1?2+1=31
注意觀察到,因?yàn)檫@個(gè)11111的每一位都是作為二進(jìn)制的數(shù),那么在計(jì)算的時(shí)候它需要乘上當(dāng)前位置前后面的所有2 不包括自己。
類比本題的例子來說:
? 321 = > 3 ? 10 ? 2 + 2 ? 2 + 1 = 65 321 => 3*10*2 + 2*2 + 1 = 65 321=>3?10?2+2?2+1=65
同樣是某一位上的數(shù)num[i] * 它后面所有的進(jìn)制
之后就是先判斷這個(gè)每一位對(duì)應(yīng)的進(jìn)制,由于想要最小值,那么由以上的計(jì)算過程可知,只需讓每一個(gè)進(jìn)制取到最小值即可,當(dāng)然最小是二進(jìn)制。
代碼相關(guān)解釋都在注釋中。
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]; // 存儲(chǔ)進(jì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++) {// 確定進(jìn)制int t = max(a[i],b[i]);c[i] = max(2,t+1);c[i] = c[i-1]*c[i] % mod; // 計(jì)算前綴積}ll res = 0;for(int i = 1;i <= len;i++) {res = (res+(a[i]-b[i])*c[i-1]%mod)%mod;}// 雖然題目中表明A > B但是取模之后的值不一定是A大,所以最后要做將負(fù)數(shù)轉(zhuǎn)為正值的操作// 那么先加mod就是為了補(bǔ)充A的不足而加的// 最后為了防止res的值為負(fù),進(jìn)行加mod再取模,將其轉(zhuǎn)換為正值4.如果不處理這點(diǎn)會(huì)過50%cout<<(res + mod) % mod<<endl;return 0;
}
備注
想要一起備賽的小伙伴添加一下 !