f709 - 12019 - Doom's Day Algorithm

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 2011 年某個給定日期是星期幾。題目給定了 Doom's Day Algorithm 的概念，但實際上並不需要使用該演算法，只需要計算從年初到給定日期的天數，然後對 7 取模即可得到星期幾。

解題思路

題目給定的日期是 2011 年的，因此可以假設 2011 年 4 月 4 日是星期一。程式碼直接計算從年初到給定日期的天數，利用 arr 陣列儲存每個月份的天數，然後對 7 取模，得到星期幾的索引，最後輸出對應的星期幾。

複雜度分析

• 時間複雜度: O(T * M)，其中 T 是測試案例的數量，M 是月份數（最大為 12）。因為對於每個測試案例，程式碼需要迴圈計算到給定月份的天數。
• 空間複雜度: O(1)，程式碼使用的額外空間是常數級別，主要用於儲存月份的天數陣列 arr 和星期幾的字串陣列 ans，這些陣列的大小是固定的。

程式碼

#include <iostream>
using namespace std;
int arr[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
string ans[7]={"Friday","Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday"};
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int t,m,d;
	cin >> t;
	while(t--){
		cin >> m >> d;
		for(int i=1;i<m;++i)
			d+=arr[i];
		cout << ans[d%7] << "\n";
	}
}