程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 471C MUH and House of Cards

CodeForces 471C MUH and House of Cards

編輯:C++入門知識

CodeForces 471C MUH and House of Cards


看題目的Hint 圖形就知道題意了,對著圖形,稍微觀察一下就會發現,每一層需要的卡牌數目為 2 * n + (n - 1)個,然後大致就有個思路,暴力枚舉,但是僅僅這樣沒法子枚舉,這個公式 只代表其中一層,不可能對每一層都枚舉吧,可以化簡一下 公式就是 3 * n - 1,這樣就會發現 每次差1就是3的倍數了,然後每一層都差1,如果有i層的話,那麼其實就是差了i,這樣就很容易想到了,假設共有卡牌 x張,其實 就是枚舉 i ,有多少個i 使得 (x + i)%3 == 0,這樣就簡單了,但是還有個限制的,因為 搭建i層 至少需要的牌數要知道,布恩那個超過x張,這裡又得多畫畫找找,後來發現 搭建i層 至少需要 (3 * i + 1)* i/2張卡牌,這樣 就很容易確定枚舉范圍了,而且 答案不大,所以直接枚舉答案沒事

 

題目鏈接:戳這裡

 

做完覺得有點取巧,萬一答案很大不就完了,於是乎去看看別人怎麼做的,發現了更好的方法,其實 每一層 差1 就是3的倍數,那麼相當於,每一層減去2就是3的倍數,這樣就不是 枚舉 (x + i)%3 == 0了,可以往下 枚舉 (x - 3 * (j - 1) - 2 * j)%3 == 0;這樣就不用考慮上限了,減少了找公式的時間

 

 

ll n;


void init() {

}

bool input() {
	while(cin>>n) {

		return false;
	}
	return true;
}

void cal() {
	ll ans = 0ll;
	for(ll k = 1;;k++) {
		if(n < (3 * k + 1) * k / 2) break;
		if((n + k)%3 == 0)ans++;
	}
	cout<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved