竹園論壇
標題: [編輯][高一排名賽-2015] 賽前測試題解 [打印本頁]
作者: jd3 時間: 2015-5-17 19:30
標題: [編輯][高一排名賽-2015] 賽前測試題解
本帖最後由 jd3 於 2015-5-20 13:06 編輯
前情提要
隨著賽前測試開放
編輯完成前先發了
(這兩天應該會趕完)重整看新內容時請清除chrome的快取
這回賽前測試有三題每題都有部分給分
正式比賽也會有部分給分
儘管撈分數吧~ XD
第1題為基本題
熟悉judge基本操作用的
第2題是互動題
因為正式比賽中也有互動題
想拿好成績要先弄懂喔~OwO
(好像有人偷偷摻了奇怪的時間限制進去)
第3題是「時間複雜度」題
一些題目中需要更快的做法才能拿到全部的分數
大多數時候「快」指的就是比較低的時間複雜度
Judge的使用
各位可對這個系統很陌生
首先登入後左邊有一排標籤
內容大概就字面上的意思
對於每個題目
先到題敘述下載檔案(如果沒裝PDF檢視器,可以用網頁的瀏覽器開)
寫完到評測頁面選擇你的程式碼檔案上傳
之後judge會告訴你結果
不需要一直F5也會顯示
詳細資料中可以看每一筆測資的結果
點開子問題可以看到是為什麼沒拿到分 ( 如果是答案錯誤不會告訴你錯了什麼 )
右側的下載可以載自己的CODE (應該沒必要吧, 除非你手殘刪了)
最後得分是以所有上傳中最高分的
請不要使用system("pause");
你會開心地得到TLE
輸出解答後請確定程式能正常結束
第一題 ： [ 畢氏定理 ] [ 迴圈 ] [ 浮點數 ]
嘛~這和距離平方成反比是從萬有引力獲得靈感的
總之就是先算出距離
距離 R^2 = (H^2 + △X^2 + △Y^2)
溫度 D = E/(R^2)
也就是 溫度 D=(H^2 + △X^2 + △Y^2)
所以我們發現根本不需要開根號什麼的 >w<
然後開開心心的
對每個點加總被每個暖氣加熱的量
迴圈掃過去找到全部最低的就行了
這題很好心的就算你真的開了個2維陣列應該還是能過關
因為我測資產不出太大的拉QAQ
第二題：[ 互動題 ] [ counting ]
題目有點長
耐心看完其實沒有很難
麻煩的是互動題到底是三小
下載給定的code之後
到註解前有一串奇怪的程式碼
不要動它
那是可以幫助你debug的東西
需要小心的是
要記得引入標頭檔 ( iostream也是 )
還有千萬不要把include寫在前面那段裡面
最安全的做法就是都寫在註解以下
另外
你不需要也不應該再寫一個main函式
只要完成指定的函式內容就行了
嗯...希望你知道函式 ( Function ) 是什麼 >w<
進入題目部分
init 函式裡傳入的工作表看起來很詭異
型態是 const char*總之就是個字元陣列
如果直接宣告一個 const char* 設成str
會發現任何修改內容都會造成編譯錯誤
所以我們有兩種做法
第一種想法是：「作者應該沒有吃飽太閒去改它吧」
直接把 const char* 強制轉型成轉成 char*
要是作者看到我這樣寫而把它改了不要打我>w<
此作法已失效
第二種比較中規中矩
把整個 array 複製出來再實作
題目內容就...不用多說了吧
如果沒有通過第2,3筆測資請點開來看看
上面可能寫著「超過時間限制」
沒錯！你的做法太慢了！
如果不會或不想學時間複雜度的話就精神感受一下速度差異吧
關於時間複雜度請見篇末
Change是O(1)毫無疑問
Ask時如果迴圈掃過去是O(N) (( N為字串長度
整體為O(N)
因為char只有0~255
所以可以輕鬆做個記數
開個記數用的 array, 大小256就很夠用了 (記得初始化成0)
Init時先掃過str一次，紀錄每個字出現幾次
每次Change時把舊的數量--，新的數量++
Change依然O(1)
return指定字元的數量只要O(1)
第三題：[ 時間複雜度 ]
因為不想太快講出解法所以中括號先放個時間複雜度
題目敘述中
前綴和後綴的定義翻成白話文就是
前綴第 i 項：從前面加總到第 i 個
後綴第 i 項：從後面加總到倒數第 i 個
Q： 有沒有 某個前綴+某個後綴=T
先講Input吧
EOF是三小?
所有檔案結尾都有個表示「人家只有長到這裡啦><」的符號
那個符號就叫做EOF (End Of File)
judge在輸入的時候會餵一個Input檔案給你的程式
所以最後會跟著一個EOF符號
那我要怎麼判斷EOF符號呢?
cin本身遇到 EOF 會return特殊的東西放在迴圈的條件裡就會結束
所以可以寫
[C++] 純文本查看 復制代碼
int N;
while(cin >> N)
{
// ...
}
其中cin>>N改成cin>>A>>B>>C
這樣連用也是可以的
而輸入A,B,C遇到任一個為EOF就會直接return
這樣就是輸入N後執行迴圈內容
如果輸入了EOF就離開迴圈
如果你用scanf
scanf本身遇到EOF會return EOF
所以可以這樣寫
[C++] 純文本查看 復制代碼
int N;
while(scanf("%d",&N) != EOF)
{
// ...
}
EOF有很高的機會是-1
通常都是負數
所以有另一個比較不安全的寫法
[C++] 純文本查看 復制代碼
int N;
while(~scanf("%d",&N))
{
// ...
}
本次比賽應該可以用
但還是建議學第一個做法
那要怎麼Debug呢?
在 Windows 裡按 Ctrl+Z 就能輸入EOF
如果不行的話...試試Ctrl+D (好像是某企鵝作業系統的設定?)
暴力法：
迴圈掃啊掃~
一個枚舉前綴、一個算出前綴；一個枚舉後綴、一個算出後綴。
4個for輕鬆搞定~
對於一次詢問的時間複雜度：
枚舉 O( N^2 ) x 加總 O(N)
= O(N^3)
乘上詢問次數整個複雜度是
O(N^3 * Q)
輕鬆得到TLE (Time Limit Exceeeeeeeeeeeeeeeeeeeeeed)
預處理前綴後綴：
先把前綴和後綴算出來就不用每次詢問都要加總了~
預處理是O(N)
枚舉還是N^2
算出某個前綴(後綴)的時間變成O(1)
總複雜度 O(N) + O(N^2*Q) = O(N^2 * Q)
恭喜通過小測資~
預處理總和：
看到那些Input的範圍了嗎?
來把前面的作法算一下看看
N^2 * Q = 10^14
好可怕的數字
如果我們預處理所有可能出現的前後綴之和
那麼就會變成：
預處理前後綴 O(N^2)
初始化總和buff O(T)
預處理總和 O(N^2)
詢問一次 O(1)
全部詢問 O(Q)
再算一次看看
因為時間複雜度常數可忽略
所以 O(N^2 + T + N^2 + Q) = O(N^2 + Q)
所以最後是 O(N^2)
估計一下
N^2 = 10^10
這好多了
所以預處理完所有可能狀態後
依然TLE了~
二分搜尋：
仔細觀察會發現奇怪的東西
...
...
...
為什麼Q要比N小
當然一切都是為了讓你TLE
裡面一定有玄機
因為Q比較小
如果能把預處理的時間分到某種跟Q成正比的操作就最好了
前後綴的預處理當然還是少不了
我們希望不用預處理所有可能 ( 討厭的 N^2
在每次查詢的時候又盡可能的快 ( 不然乘上Q就太大
今天已經預處理前後綴
且知道前後綴都是遞增的
知道2分搜的人或許能想的到
不需要2層for枚舉
枚舉前綴 Si
對於每個Si , 都到後綴裡2分搜 T-Si
找得到就成功了！
而2分搜的複雜度 O ( log(N) )
( log 以2為底 )
所以整體變 O(N + N*log(N) ) = O( N*log(N) )
估算一下
N * log(N) * Q = 5*10^9
看起來似乎砍半了?
但就這樣傳上去會發現依然TLE甚至執行時間更長了
問題就出在於
二分搜常數太大了
沒關係
以下有更好的方法
單調優化：
說真的這名詞滿有深度
但是在這題裡作法很簡單
所謂的單調就是...ㄜ...很單調(?
簡單來說就是很有規律
例如說遞增、遞減
還記得剛剛說前後綴怎麼了嗎?
我們枚舉前綴 (( 巴拉巴拉的for迴全掃過去
看到後綴是遞增的很開心的2分搜
或是很暴力的for又巴拉巴拉的掃了一次
OK停在這裡
我們少了個東西
前綴也是遞增的
前綴的單調性我們沒有用到啊
再仔細想想
2分搜(或暴力搜)的時候，因為前綴遞增，所以搜到的後綴和遞減
所以我們蒐的答案就是從右邊往左邊跑
經過一翻觀察
我們完全可以排除重複搜尋到的部分(也就是不可能出現答案的部分)
原本可能這樣寫
[C++] 純文本查看 復制代碼
for(int i = 0 ; i < n ; i++)
if(binary_search(sp, sp+n, T-s[ i ]))
//...
或是這樣
[C++] 純文本查看 復制代碼
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
if(s[ i ]+sp[j] == T)
//...
改造一下變類似這樣
[C++] 純文本查看 復制代碼
int j = n;
for(int i = 0 ; i < n ; i++)
{
while(s[ i ] + sp[j] < T)
j--;
if(s[ i ]+sp[j] == T)
//...
}
這樣看起來還是2個迴圈
有差嗎?
事實上，因為第2層迴圈執行的總次數最多就是N次 (因為 j 只會往左移動)
所以詢問的整體複雜度是O ( N*Q )
再估算一下
N * Q = 10^9
而且從頭到尾都只有簡單的迴圈掃過來掃過去所以常數很小
終於 AC 囉~
CODE：
還是希望各位可以自己寫
這裡的code參考就好
賽前測試參考解答.rar
(1.71 KB, 下載次數: 4)
關於時間複雜度
通常我們用時間複雜度來評估一個演算法的效率，以及適合使用的時機
這裡介紹最常見的「最差複雜度」
最差複雜度的表示方式是
O ( F )
前面這個符號念作 BIG-O 表示最差複雜度
F 則是花費時間的函式
也就是執行所花費的時間大致和 F 成正比
嚴格定義就不說了
舉些例子
O(1) ：不管怎麼變化時間都是常數
O(N) ：花費時間和N成正比
O(N*M) ：和 N 成正比, 也和 M 成正比。也就是和(N*M)成正比。
O(N + M) ：可能某部分和N成正比，某部分和M成正比，但兩個沒有直接關係。例如預處理時間花N, 計算花費M, 如果N比較大則最差時間取決於N, 反之則是M。
還不太會評估複雜度時
可以用迴圈數量來看
包1層就是N
包2層就是N^2
包k層就是N^k
...
遇到二分搜就有個log出現 ( 資訊領域中如果沒特別說, log 都用2為底)
諸如此類
======================================
//終於打完可以收工了 >口<
作者: visitorIKC 時間: 2015-5-20 20:59
本帖最後由 visitorIKC 於 2015-5-20 21:48 編輯
第三題另解
直接hash所有後綴
就可以O(1) 得知某個後綴有無出現
對每個Query
枚舉前綴
直接查詢後綴存不存在
複雜度 O(TcNQ)
實作直接用lookup Table
MLE - 10/100
若改用std::map(複雜度退化)
TLE - 10/100
用Array,再快樂的作一些優化
AC - 100/100
成功AC ^_^
到目前為止還沒有被Challenge掉 : )
XXXXXXD
作者: 林宇翔 時間: 2015-5-29 10:40
[C++] 純文本查看 復制代碼
int j = n;
for(int i = 0 ; i < n ; i++)
{
while(s[ i ] + sp[j] < T)
j--;
if(s[ i ]+sp[j] == T)
//...
}
這有點問題!
這樣做的話，後綴得由大到小排列才行吧?
作者: 林宇翔 時間: 2015-5-29 22:00
我有報阿!
| 歡迎光臨 竹園論壇 (http://forum.tfcis.org/) |
Powered by Discuz! X3.2 |