竹園論壇

標題: 120 - C. Counting Stars [打印本頁]

作者: domen111 時間: 2014-12-5 21:32
標題: 120 - C. Counting Stars
本帖最後由 domen111 於 2014-12-5 21:35 編輯

恩，這題好像很簡單啊! 寫個for迴圈算一算就可以了，然後你就會拿到:

Accepted

Wrong Answer

Time Limit Exceed

這題的測資我可是精心設計過的，有三個問題要注意，用不同的寫法就會拿到不同的分數

問題一:

題目敘述:「代表第q個客戶想要要買下 a[sub]q[/sub] 到 b[sub]q[/sub] 之間（包含那兩棵）所有的星星」，他沒有保證b[sub]q[/sub]一定大a[sub]q[/sub]啊! 一堆人都掉進陷阱去了。

解決方法:

輸入a[sub]q[/sub]和b[sub]q[/sub]時，檢查如果b<a，就交換a,b。交換數字的方法呢?

方法一: 最普通的方法，用個暫存變數做交換

[C++] 純文本查看 復制代碼

if(b<a)

{

        int temp=a;

        a=b;

        b=temp;

}

方法二: 內建的函數，在algorithm這個標頭檔裡面有個swap的function，輕輕鬆鬆把code縮短許多

[C++] 純文本查看 復制代碼

#include<algorithm>

if(b<a)

        swap(a,b);

方法三: 其實沒什麼用，利用位元運算的方法做交換，不用include也能一行程式碼做完交換，不過難理解而且事實上執行速度比較慢，還是比較推薦方法二

[C++] 純文本查看 復制代碼

if(b<a)

        a^=b^=a^=b;

問題二:

每個數字大小不超過10[sup]8[/sup]，恩，那我開int就夠了(?)
int最大值 = 2[sup]31[/sup]-1 = 2*10[sup]9[/sup]
每棵樹上的星星不超過10[sup]8[/sup]個，那不就存得下了嗎?
不! 你又掉進另一個陷阱，最多200000個數字，要求相加，那麼加起來最大值就有200000*10[sup]8[/sup]=2*10[sup]13[/sup]，這樣你還覺得int真的存的下嗎?

問題三:

這才是這題的重點!

這個問題跟演算法的複雜度有關係，詳細的說明請見社課講義: 講義：複雜度分析初步.pdf

最多有20000筆詢問，數量最多有200000顆，所以最壞情況可能要執行20000*200000次，明顯會TLE(電腦每秒執行次數約10[sup]7[/sup]次)

那倒底該怎麼寫呢?

一個簡單的優化方法: 計算前綴和

也就是說，假設原來的陣列叫做a，另外一個陣列b[k]=a[0]+...+a[k]

先預處理算出b，假設要算a[l]+a[l+1]+...+a[r]，就只要算b[r]-b[l-1]一次就算好了

三個問題都解決了，恭喜AC!

歡迎光臨竹園論壇 (http://forum.tfcis.org/)