c200 - 車牌等級(License Plate)-TOI練習賽y7m5-2

🔗 前往 ZeroJudge 原題

題目描述

題目要求將天龍國的車牌號碼，視為三十六進位數轉換為十進位數，並計算轉換後的數除以 1688 的餘數，最後根據餘數計算車牌等級。如果餘數為 k，則車牌等級為 k+1。

解題思路

這題的核心在於將三十六進位數轉換為十進位數。由於車牌號碼可能較長，直接轉換可能會導致整數溢位。因此，在轉換過程中，我們使用模運算來避免溢位。具體來說，我們從車牌號碼的最低位開始，逐位計算其對應的十進位值，並將其乘以當前的權重（36 的冪），然後加到總和中。在每次加法後，我們都對總和進行模 1688 運算，以保持總和在可控範圍內。權重也需要進行模 1688 運算，以防止權重溢位。最後，將得到的餘數加 1 即可得到車牌等級。

複雜度分析

• 時間複雜度: O(n)，其中 n 是車牌號碼的長度。因為需要遍歷車牌號碼的每一位。
• 空間複雜度: O(1)，因為只使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
int main(){
	string a;
	int t;
	cin >> t;
	while(t--){
		cin >> a;
		int al=a.length(),ans=0;
		for(int i=al-1,k=1;i>=0;--i,k*=36){
			if(a[i]>'9')
				ans+=(a[i]-'A'+10)*k;
			else
				ans+=(a[i]-'0')*k;
			ans%=1688;
			k%=1688;
		}
		cout << ans+1 << '\n';
	}
}